|
| related topics |
| {algorithm, log, probability} |
| {state, algorithm, problem} |
| {let, theorem, proof} |
| {time, systems, information} |
| {operator, operators, space} |
| {state, states, entangled} |
| {qubit, qubits, gate} |
| {vol, operators, histories} |
| {cos, sin, state} |
| {states, state, optimal} |
| {error, code, errors} |
|
Quantum NP - A Survey
Dorit Aharonov, Tomer Naveh
abstract: We describe Kitaev's result from 1999, in which he defines the complexity
class QMA, the quantum analog of the class NP, and shows that a natural
extension of 3-SAT, namely local Hamiltonians, is QMA complete. The result
builds upon the classical Cook-Levin proof of the NP completeness of SAT, but
differs from it in several fundamental ways, which we highlight. This result
raises a rich array of open problems related to quantum complexity, algorithms
and entanglement, which we state at the end of this survey. This survey is the
extension of lecture notes taken by Naveh for Aharonov's quantum computation
course, held in Tel Aviv University, 2001.
- oai_identifier:
- oai:arXiv.org:quant-ph/0210077
- categories:
- quant-ph
- comments:
- 23 pages
- arxiv_id:
- quant-ph/0210077
- created:
- 2002-10-11
Full article ▸
|
|
| related documents |
| 0010021v1 |
| 0010034v1 |
| 0207131v1 |
| 0304131v1 |
| 0403140v2 |
| 0410042v1 |
| 0505007v3 |
| 0607148v3 |
| 9907020v2 |
| 9903071v1 |
| 0511272v1 |
| 0201152v1 |
| 0302022v1 |
| 0504067v3 |
| 0206089v2 |
| 9802040v2 |
| 0702007v2 |
| 0303175v1 |
| 0210141v2 |
| 0306042v1 |
| 0610235v2 |
| 0008059v3 |
| 0401053v1 |
| 0609220v1 |
| 0612089v3 |
|