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. doi:10.1103/PhysRevA.90.022310.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
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:Institute for Quantum Information and Matter
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
Gordon and Betty Moore FoundationUNSPECIFIED
Issue or Number:2
Classification Code:PACS: 03.67.Ac; 03.67.Lx; 42.50.Lc
Record Number:CaltechAUTHORS:20140925-110837575
Persistent URL:
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
Deposited On:25 Sep 2014 20:21
Last Modified:10 Nov 2021 18:51

Repository Staff Only: item control page