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
On the Power of Quantum Computation: Oracles
Linköping University, Department of Electrical Engineering, Information Coding. Linköping University, Faculty of Science & Engineering.
2018 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperforms the best-known classical algorithm. A large body of these examples relies on oracle query complexity, where the performance (complexity) of the algorithms is measured by the number of times they need to access an oracle. Here, an oracle is usually considered to be a black box that computes a specific function at unit cost.

However, the quantum algorithm is given access to an oracle with more structure than the classical algorithm. This thesis argues that the two oracles are so vastly different that comparing quantum and classical query complexity should not be considered evidence, but merely hints for a quantum advantage.

The approach used is based on a model that can be seen as an approximation of quantum theory, but can be efficiently simulated on a classical computer. This model solves several oracular problems with the same performance as their quantum counterparts, showing that there is no genuine quantum advantage for these problems. This approach also clarifies the assumptions made in quantum computation, and which properties that can be seen as resources in these algorithms.

Abstract [sv]

Med en kvantdator antas vi kunna lösa vissa beräkningsproblem snabbare än dom bästa lösningarna tillgängliga för en vanlig klassisk dator. Bevisen för detta bygger på flertalet exempel där man har en kvantalgoritm som överträffar den bästa kända klassiska algoritmen. En stor andel av dessa exempel bygger på vad man kallar anrops-komplexitet, där man låter antalet anrop till ett orakel vara måttet på hur bra algoritmerna presterar. Här anses ett orakel vara en svart låda som beräknar en funktion under endast ett tidssteg.

Kvantalgoritmen ges emellertid tillgång till ett orakel med mer struktur än det orakel som den klassiska algoritmen får tillgång till. Denna avhandling argumenterar för att dessa två orakel är så pass olika att en jämförelse mellan kvantalgoritmen och den klassiska algoritmen inte kan ses som bevis för kvantdatorns fördelar.

Metoden vi använt är att konstruera en modell som kan anses vara en approximation av kvantteori, men kan simuleras effektivt på en klassisk dator. Denna modell löser flera orakelproblem med samma prestanda som motsvarande kvantalgoritmer, vilket visar att det inte finns någon äkta kvantfördel för dessa problem. Metoden klargör också vilka villkoren är för en kvantdator och vilka egenskaper som kan anses vara resurser i dessa algoritmer.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2018. , p. 36
Series
Linköping Studies in Science and Technology. Licentiate Thesis, ISSN 0280-7971 ; 1823
National Category
Computer Sciences Computer and Information Sciences
Identifiers
URN: urn:nbn:se:liu:diva-152493ISBN: 9789176851784 (print)OAI: oai:DiVA.org:liu-152493DiVA, id: diva2:1260724
Presentation
2018-12-03, Ada Lovelace, B-huset, Campus Valla, Linköping, 13:15 (Swedish)
Opponent
Supervisors
Available from: 2018-11-05 Created: 2018-11-05 Last updated: 2018-11-06Bibliographically approved
List of papers
1. Efficient classical simulation of the Deutsch-Jozsa and Simons algorithms
Open this publication in new window or tab >>Efficient classical simulation of the Deutsch-Jozsa and Simons algorithms
2017 (English)In: Quantum Information Processing, ISSN 1570-0755, E-ISSN 1573-1332, Vol. 16, no 9, article id UNSP 233Article in journal (Refereed) Published
Abstract [en]

Along-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch-Jozsa and Simons problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch-Jozsa problem with probability 1 using only one oracle query, and Simons problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch-Jozsa and Simons problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.

Place, publisher, year, edition, pages
SPRINGER, 2017
National Category
Condensed Matter Physics
Identifiers
urn:nbn:se:liu:diva-140503 (URN)10.1007/s11128-017-1679-7 (DOI)000408080500009 ()
Note

Funding Agencies|Foundational Questions Institute (FQXi) through the Silicon Valley Community Foundation

Available from: 2017-09-11 Created: 2017-09-11 Last updated: 2018-11-05

Open Access in DiVA

omslag(2749 kB)20 downloads
File information
File name COVER01.pdfFile size 2749 kBChecksum SHA-512
701386ae90ead4b587b68b8f9e81a34269f16d3511861c0cf231c7077e01cd43b4d7b67ab6ec2f6a06161cbf790331f299793ecde98a62bf45970c47e882d281
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Johansson, Niklas
By organisation
Information CodingFaculty of Science & Engineering
Computer SciencesComputer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 231 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