CaltechAUTHORS
  A Caltech Library Service

Runtime of unstructured search with a faulty Hamiltonian oracle

Temme, Kristan (2014) Runtime of unstructured search with a faulty Hamiltonian oracle. Physical Review A, 90 (2). Art. No. 022310. ISSN 1050-2947. http://resolver.caltech.edu/CaltechAUTHORS:20140925-110837575

[img]
Preview
PDF - Published Version
See Usage Policy.

86Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140925-110837575

Abstract

We show that it is impossible to obtain a quantum speedup for a faulty Hamiltonian oracle. The effect of dephasing noise to this continuous-time oracle model has first been investigated by Shenvi, Brown, and Whaley [Phys. Rev. A 68, 052313 (2003).]. The authors consider a faulty oracle described by a continuous-time master equation that acts as dephasing noise in the basis determined by the marked item. The analysis focuses on the implementation with a particular driving Hamiltonian. A universal lower bound for this oracle model, which rules out a better performance with a different driving Hamiltonian, has so far been lacking. Here, we derive an adversary-type lower bound which shows that the evolution time T has to be at least in the order of N , i.e., the size of the search space, when the error rate of the oracle is constant. This means that quadratic quantum speedup vanishes and the runtime assumes again the classical scaling. For the standard quantum oracle model this result was first proven by Regev and Schiff [in Automata, Languages and Programming, Lecture Notes in Computer Science Vol. 5125 (Springer, Berlin, 2008), pp. 773–781]. Here, we extend this result to the continuous-time setting.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1103/PhysRevA.90.022310DOIArticle
http://journals.aps.org/pra/abstract/10.1103/PhysRevA.90.022310PublisherArticle
Additional Information:© 2014 American Physical Society. Received 28 May 2014; Published 11 August 2014. I would like to thank Edward Farhi for suggesting this research project to me. Moreover, I would like to thank Shelby Kimmel and Fernando Pastawski for insightful discussions. The author gratefully acknowledges support from the Erwin Schrödinger fellowship, Austrian Science Fund (FWF): J3219-N16. This work was supported by the Institute for Quantum Information and Matter, a NSF Physics Frontiers Center with support of the Gordon and Betty Moore Foundation(Grants No. PHY-0803371 and No. PHY-1125565).
Group:IQIM, Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Erwin Schrödinger FellowshipUNSPECIFIED
Austrian Science Fund (FWF)J3219-N16
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterUNSPECIFIED
NSFPHY-0803371
NSFPHY-1125565
Gordon and Betty Moore FoundationUNSPECIFIED
Classification Code:PACS: 03.67.Ac; 03.67.Lx; 42.50.Lc
Record Number:CaltechAUTHORS:20140925-110837575
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140925-110837575
Official Citation:Temme, K. (2014). Runtime of unstructured search with a faulty Hamiltonian oracle. Physical Review A, 90(2), 022310.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:50030
Collection:CaltechAUTHORS
Deposited By: Joanne McCole
Deposited On:25 Sep 2014 20:21
Last Modified:25 Sep 2014 20:21

Repository Staff Only: item control page