2005/06/29 by Antoni Wojcik Ravindra W. Chhajlany, Chhajlany, Antoni Wojcik Ravindra W.
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0506248
arxiv created 2005/06/29 · arxiv updated 2009/12/01
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.