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
Efficient classical simulation of the Deutsch-Jozsa and Simons algorithms
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
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. Vol. 16, no 9, article id UNSP 233
National Category
Condensed Matter Physics
Identifiers
URN: urn:nbn:se:liu:diva-140503DOI: 10.1007/s11128-017-1679-7ISI: 000408080500009OAI: oai:DiVA.org:liu-140503DiVA, id: diva2:1140144
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
In thesis
1. On the Power of Quantum Computation: Oracles
Open this publication in new window or tab >>On the Power of Quantum Computation: Oracles
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:nbn:se:liu:diva-152493 (URN)9789176851784 (ISBN)
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

Open Access in DiVA

fulltext(526 kB)83 downloads
File information
File name FULLTEXT01.pdfFile size 526 kBChecksum SHA-512
c21e91861c42e6a88d8c915244ed2579eb6f55797e73cad4bc0eb8c025a34661de8fabe961cf0ff831341290ee768c814bb7baa5d5afb135700cd9cfcec9878c
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Johansson, NiklasLarsson, Jan-Åke
By organisation
Information CodingFaculty of Science & Engineering
In the same journal
Quantum Information Processing
Condensed Matter Physics

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 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: 515 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