1998/05/07 by Jonathan Machta, J. Machta, Machta, J.
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9805022
3 pages, latex
arxiv created 1998/05/07 · openalex publication_date 1998/05/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computational devices may be supplied with external sources of information (oracles). Quantum oracles may transmit phase information which is available to a quantum computer but not a classical computer. One consequence of this observation is that there is an oracle which is of no assistance to a classical computer but which allows a quantum computer to solve undecidable problems. Thus useful relativized separations between quantum and classical complexity classes must exclude the transmission of phase information from oracle to computer.