Average-Case Quantum Query Complexity
<|reference_start|>Average-Case Quantum Query Complexity: We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.<|reference_end|>
@article{ambainis1999average-case,
    title={Average-Case Quantum Query Complexity},
    author={Andris Ambainis (UC Berkeley) and Ronald de Wolf (CWI and U of
  Amsterdam)},
    journal={arXiv preprint arXiv:quant-ph/9904079},
    year={1999},
    archivePrefix={arXiv},
    eprint={quant-ph/9904079},
    primaryClass={quant-ph cs.CC}
}