|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
|
Average-Case Quantum Query Complexity
Andris Ambainis, Ronald de Wolf
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. 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.
- oai_identifier:
- oai:arXiv.org:quant-ph/9904079
- categories:
- quant-ph cs.CC
- comments:
- 14 pages, LaTeX. Some parts rewritten. This version to appear in the
Journal of Physics A
- arxiv_id:
- quant-ph/9904079
- created:
- 1999-04-23
- updated:
- 2001-07-02
Full article ▸
|
|
| related documents |
| 0510230v3 |
| 0408119v1 |
| 9910033v4 |
| 0703231v2 |
| 0603135v1 |
| 0510185v1 |
| 0504083v2 |
| 0408150v2 |
| 0008059v3 |
| 9907020v2 |
| 0612089v3 |
| 0410042v1 |
| 0607148v3 |
| 0403140v2 |
| 0304131v1 |
| 0010034v1 |
| 0206023v2 |
| 0210077v1 |
| 0207131v1 |
| 0511272v1 |
| 0504067v3 |
| 0505007v3 |
| 0201152v1 |
| 9905026v1 |
| 0206089v2 |
|