Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 11, 2014 | Published
Journal Article Open

Runtime of unstructured search with a faulty Hamiltonian oracle

Temme, Kristan

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.

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).

Attached Files

Published - PhysRevA.90.022310.pdf

Files

PhysRevA.90.022310.pdf
Files (88.5 kB)
Name Size Download all
md5:f11ace79072899eb27fbf13fb09efa0a
88.5 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 17, 2023