@inproceedings{98139425ab284c429446585c3172fda0,
title = "Average-case quantum query complexity",
abstract = "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 [3]. 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.",
author = "Andris Ambainis and \{de Wolf\}, Ronald",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 ; Conference date: 17-02-2000 Through 19-02-2000",
year = "2000",
doi = "10.1007/3-540-46541-3\_11",
language = "English",
isbn = "9783540671411",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "133--144",
editor = "Horst Reichel and Sophie Tison",
booktitle = "STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings",
address = "Germany",
}