On Quantum Versions of the Yao Principle
<|reference_start|>On Quantum Versions of the Yao Principle: The classical Yao principle states that the complexity R_epsilon(f) of an optimal randomized algorithm for a function f with success probability 1-epsilon equals the complexity max_mu D_epsilon^mu(f) of an optimal deterministic algorithm for f that is correct on a fraction 1-epsilon of the inputs, weighed according to the hardest distribution mu over the inputs. In this paper we investigate to what extent such a principle holds for quantum algorithms. We propose two natural candidate quantum Yao principles, a ``weak'' and a ``strong'' one. For both principles, we prove that the quantum bounded-error complexity is a lower bound on the quantum analogues of max mu D_epsilon^mu(f). We then prove that equality cannot be obtained for the ``strong'' version, by exhibiting an exponential gap. On the other hand, as a positive result we prove that the ``weak'' version holds up to a constant factor for the query complexity of all symmetric Boolean functions<|reference_end|>
@article{de graaf2001on,
    title={On Quantum Versions of the Yao Principle},
    author={Mart de Graaf and Ronald de Wolf (CWI Amsterdam)},
    journal={arXiv preprint arXiv:quant-ph/0109070},
    year={2001},
    archivePrefix={arXiv},
    eprint={quant-ph/0109070},
    primaryClass={quant-ph cs.CC}
}