|
| related topics |
| {algorithm, log, probability} |
| {states, state, optimal} |
| {operator, operators, space} |
| {state, algorithm, problem} |
|
A Limit on the Speed of Quantum Computation for Insertion into an
Ordered List
E. Farhi, J. Goldstone, S. Gutmann, M. Sipser
abstract: We consider the problem of inserting a new item into an ordered list of N-1
items. The length of an algorithm is measured by the number of comparisons it
makes between the new item and items already on the list. Classically,
determining the insertion point requires log N comparisons. We show that, for N
large, no quantum algorithm can reduce the number of comparisons below log N/(2
loglog N).
- oai_identifier:
- oai:arXiv.org:quant-ph/9812057
- categories:
- quant-ph
- comments:
- 5 pages
- arxiv_id:
- quant-ph/9812057
- report_no:
- MIT-CTP-2811
- created:
- 1998-12-18
Full article ▸
|
|
| related documents |
| 0303074v1 |
| 0508156v3 |
| 0207108v1 |
| 0609166v1 |
| 0609160v1 |
| 0208112v1 |
| 0403071v1 |
| 0206066v1 |
| 0308016v1 |
| 0209148v1 |
| 9901068v1 |
| 0612052v2 |
| 0608156v1 |
| 0012088v1 |
| 0406104v1 |
| 0005036v1 |
| 0401067v2 |
| 0010081v1 |
| 0107085v1 |
| 0507194v1 |
| 0612033v1 |
| 0606242v3 |
| 0507024v1 |
| 0005087v2 |
| 0502144v1 |
|