The mechanism of the quantum speed-up in oracle computing

Beverly Sackler

Oded Regev, Liron Schiff

Antoni Wojcik Ravindra W. Chhajlany

The oracle model of computation is believed to allow a rigorous proof of quantum over classical computational superiority. Since quantum and classical oracles are essentially different, a correspondence principle is commonly implicitly used as a platform for comparison of oracle complexity. Here, we question the grounds on which this correspondence is based. Obviously, results on quantum speed-up depend on the chosen correspondence. So, we introduce the notion of genuine quantum speed-up which can serve as a tool for reliable comparison of quantum vs classical complexity, independently of the chosen correspondence principle.

Antoni Wójcik, Ravindra W. Chhajlany

The oracle model of computation is believed to allow a rigorous proof of quantum over classical computational superiority. Since quantum and classical oracles are essentially different, a correspondence principle is commonly implicitly used as a platform for comparison of oracle complexity. Here, we question the grounds on which this correspondence is based. Obviously, results on quantum speed-up depend on the chosen correspondence. So, we introduce the notion of genuine quantum speed-up which can serve as a tool for reliable comparison of quantum versus classical complexity, independent of the chosen correspondence principle.

Antoni Wójcik, Ravindra W. Chhajlany

Quantum computers are believed to surpass the classical ones. Moreover, it is claimed that this belief reaches the level of a mathematically proven fact within the oracle model of computation. Here we impair the whole class of the so-called rigorist proofs of quantum speed-up obtained within this model.

Christino Tamon, Tomoyuki Yamakami