|
| related topics |
| {algorithm, log, probability} |
| {entanglement, phys, rev} |
| {qubit, qubits, gate} |
| {cos, sin, state} |
| {state, states, entangled} |
| {key, protocol, security} |
| {state, phys, rev} |
| {phase, path, phys} |
| {bell, inequality, local} |
| {let, theorem, proof} |
|
Quantum Advantage without Entanglement
Dan Kenigsberg, Tal Mor, Gil Ratsaby
abstract: We study the advantage of pure-state quantum computation without entanglement
over classical computation. For the Deutsch-Jozsa algorithm we present the
maximal subproblem that can be solved without entanglement, and show that the
algorithm still has an advantage over the classical ones. We further show that
this subproblem is of greater significance, by proving that it contains all the
Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and
Grover's algorithms we provide simple proofs that no non-trivial subproblems
can be solved by these algorithms without entanglement.
- oai_identifier:
- oai:arXiv.org:quant-ph/0511272
- categories:
- quant-ph cs.CC
- comments:
- 10 pages
- doi:
- 10.1117/12.617175
- arxiv_id:
- quant-ph/0511272
- journal_ref:
- Quantum Information and Computation 6(7), 606--615 (2006)
- created:
- 2005-11-30
Full article ▸
|
|
| related documents |
| 0505007v3 |
| 9905026v1 |
| 0201152v1 |
| 9706003v4 |
| 9903071v1 |
| 0207131v1 |
| 0302022v1 |
| 0010034v1 |
| 0011052v2 |
| 0304131v1 |
| 0206089v2 |
| 0504067v3 |
| 0403140v2 |
| 0410042v1 |
| 0106152v1 |
| 9907020v2 |
| 0010021v1 |
| 0607148v3 |
| 0609220v1 |
| 0303175v1 |
| 0609166v1 |
| 0210077v1 |
| 0609160v1 |
| 0612052v2 |
| 0606077v1 |
|