|
| related topics |
| {algorithm, log, probability} |
| {theory, mechanics, state} |
| {let, theorem, proof} |
| {qubit, qubits, gate} |
| {particle, mechanics, theory} |
| {vol, operators, histories} |
| {measurement, state, measurements} |
| {bell, inequality, local} |
| {state, algorithm, problem} |
| {key, protocol, security} |
| {observables, space, algebra} |
|
Quantum Computing and Hidden Variables II: The Complexity of Sampling
Histories
Scott Aaronson
abstract: This paper shows that, if we could examine the entire history of a hidden
variable, then we could efficiently solve problems that are believed to be
intractable even for quantum computers. In particular, under any
hidden-variable theory satisfying a reasonable axiom called "indifference to
the identity," we could solve the Graph Isomorphism and Approximate Shortest
Vector problems in polynomial time, as well as an oracle problem that is known
to require quantum exponential time. We could also search an N-item database
using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search
algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we
could probably not solve NP-complete problems in polynomial time. We thus
obtain the first good example of a model of computation that appears slightly
more powerful than the quantum computing model.
- oai_identifier:
- oai:arXiv.org:quant-ph/0408119
- categories:
- quant-ph
- comments:
- 14 pages. Together with Part I (quant-ph/0408035), subsumes the
earlier paper quant-ph/0205059. Can be read independently of Part I
- arxiv_id:
- quant-ph/0408119
- created:
- 2004-08-19
Full article ▸
|
|
| related documents |
| 9910033v4 |
| 0703231v2 |
| 9904079v3 |
| 0510230v3 |
| 0603135v1 |
| 0510185v1 |
| 0504083v2 |
| 0408150v2 |
| 9802040v2 |
| 0008059v3 |
| 0410042v1 |
| 0612089v3 |
| 0607148v3 |
| 0206023v2 |
| 0511272v1 |
| 0505007v3 |
| 0504067v3 |
| 0610235v2 |
| 0609220v1 |
| 0609166v1 |
| 0609160v1 |
| 0508156v3 |
| 0702007v2 |
| 0610105v1 |
| 0606077v1 |
|