Two Classical Queries versus One Quantum Query
<|reference_start|>Two Classical Queries versus One Quantum Query: In this note we study the power of so called query-limited computers. We compare the strength of a classical computer that is allowed to ask two questions to an NP-oracle with the strength of a quantum computer that is allowed only one such query. It is shown that any decision problem that requires two parallel (non-adaptive) SAT-queries on a classical computer can also be solved exactly by a quantum computer using only one SAT-oracle call, where both computations have polynomial time-complexity. Such a simulation is generally believed to be impossible for a one-query classical computer. The reduction also does not hold if we replace the SAT-oracle by a general black-box. This result gives therefore an example of how a quantum computer is probably more powerful than a classical computer. It also highlights the potential differences between quantum complexity results for general oracles when compared to results for more structured tasks like the SAT-problem.<|reference_end|>
@article{van dam1998two,
    title={Two Classical Queries versus One Quantum Query},
    author={Wim van Dam (U of Oxford, CWI)},
    journal={arXiv preprint arXiv:quant-ph/9806090},
    year={1998},
    number={CQC-2CQ:1QQ},
    archivePrefix={arXiv},
    eprint={quant-ph/9806090},
    primaryClass={quant-ph cs.CC}
}