|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
| {operator, operators, space} |
| {vol, operators, histories} |
| {information, entropy, channel} |
|
Lower Bounds on Quantum Query Complexity
Peter Hoyer, Robert Spalek
abstract: Shor's and Grover's famous quantum algorithms for factoring and searching
show that quantum computers can solve certain computational problems
significantly faster than any classical computer. We discuss here what quantum
computers_cannot_ do, and specifically how to prove limits on their
computational power. We cover the main known techniques for proving lower
bounds, and exemplify and compare the methods.
- oai_identifier:
- oai:arXiv.org:quant-ph/0509153
- categories:
- quant-ph
- comments:
- survey, 23 pages
- arxiv_id:
- quant-ph/0509153
- journal_ref:
- Bulletin of the European Association for Theoretical Computer
Science, Volume 87, 2005
- created:
- 2005-09-21
Full article ▸
|
|
| related documents |
| 9909012v4 |
| 0510230v3 |
| 0603135v1 |
| 0703231v2 |
| 0510185v1 |
| 0612089v3 |
| 0607148v3 |
| 0511272v1 |
| 0610235v2 |
| 0609220v1 |
| 0609166v1 |
| 0702007v2 |
| 0512241v1 |
| 0609160v1 |
| 0610105v1 |
| 0610214v3 |
| 0606077v1 |
| 0612052v2 |
| 0608156v1 |
| 0609125v1 |
| 0609052v3 |
| 0510179v1 |
| 0702155v3 |
| 0608039v4 |
| 0608147v2 |
|