Oracle Quantum Computing

Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.

# Quantum Computing Algorithms and Architecture # Computer Science # Complexity and Algorithms in Graphs # Quantum Information and Cryptography # Physics and Astronomy

André Berthiaume, Gilles Brassard (1994). "Oracle Quantum Computing". Journal of Modern Optics. https://doi.org/10.1080/09500349414552351