Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Impossibility of a Quantum Speed-up with a Faulty Oracle

Beverly Sackler

Published Jan 1, 2008• 0 citations
OpenAlex

Related papers

Impossibility of a Quantum Speed-Up with a Faulty Oracle

Oded Regev, Liron Schiff

Lecture notes in computer science•Jan 1, 2008•49 citations

The mechanism of the quantum speed-up in oracle computing

Giuseppe Castagnoli

•Jul 5, 2011•0 citations

Impossibility of a Quantum Speed-up with a Faulty Oracle

Oded Regev, Liron Schiff

We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this case.

arXiv:1202.1027•Feb 6, 2012•13 citations

Runtime of unstructured search with a faulty Hamiltonian oracle

Kristan Temme

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.

arXiv:1404.1977•Physical Review A•Aug 11, 2014•15 citations

Quantum Biased Oracles

亮周 河内, Akinori Kawachi

•Jan 1, 2005•0 citations

Foundations of the quantum speedup

Giuseppe Castagnoli

•Aug 23, 2013•0 citations
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 TTT has to be at least in the order of NNN, 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.