liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Quantum Simulation Logic, Oracles, and the Quantum Advantage
Linköping University, Department of Electrical Engineering, Information Coding. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Electrical Engineering, Information Coding. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-1082-8325
2019 (English)In: Entropy, ISSN 1099-4300, E-ISSN 1099-4300, Vol. 21, no 8, article id 800Article in journal (Refereed) Published
Abstract [en]

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simons algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shors algorithm for integer factorization.

Place, publisher, year, edition, pages
MDPI , 2019. Vol. 21, no 8, article id 800
Keywords [en]
simulation framework; quantum query complexity; quantum algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-160433DOI: 10.3390/e21080800ISI: 000483732700033OAI: oai:DiVA.org:liu-160433DiVA, id: diva2:1353454
Available from: 2019-09-23 Created: 2019-09-23 Last updated: 2019-09-25Bibliographically approved

Open Access in DiVA

Quantum Simulation Logic, Oracles, and the Quantum Advantage(5020 kB)68 downloads
File information
File name FULLTEXT01.pdfFile size 5020 kBChecksum SHA-512
2107b76a7010c4aa9c88d5c01e4b21abf23625b2150b68789fd2ca469243c6e8a5c6153cbaeaa6ac9358cbd1b6e6a84ce15cddf4d5fa4814890a0bf387cf7299
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Johansson, NiklasLarsson, Jan-Åke

Search in DiVA

By author/editor
Johansson, NiklasLarsson, Jan-Åke
By organisation
Information CodingFaculty of Science & Engineering
In the same journal
Entropy
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 68 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 126 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf