dorsal/arxiv
View SchemaQuantum NP - A Survey
| Authors | Dorit Aharonov, Tomer Naveh |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0210077 |
| URL | https://arxiv.org/abs/quant-ph/0210077 |
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.
{
"annotation_id": "f4719cbf-f496-4400-b2ce-44622b880a94",
"date_created": "2026-03-02T18:01:53.173000Z",
"date_modified": "2026-03-02T18:01:53.173000Z",
"file_hash": "7e43ab4e25bfe2cf373c1041ea04063236e6fb3471a487c2c04d2721a8ac3040",
"private": false,
"record": {
"abstract": "We describe Kitaev\u0027s result from 1999, in which he defines the complexity\nclass QMA, the quantum analog of the class NP, and shows that a natural\nextension of 3-SAT, namely local Hamiltonians, is QMA complete. The result\nbuilds upon the classical Cook-Levin proof of the NP completeness of SAT, but\ndiffers from it in several fundamental ways, which we highlight. This result\nraises a rich array of open problems related to quantum complexity, algorithms\nand entanglement, which we state at the end of this survey. This survey is the\nextension of lecture notes taken by Naveh for Aharonov\u0027s quantum computation\ncourse, held in Tel Aviv University, 2001.",
"arxiv_id": "quant-ph/0210077",
"authors": [
"Dorit Aharonov",
"Tomer Naveh"
],
"categories": [
"quant-ph"
],
"title": "Quantum NP - A Survey",
"url": "https://arxiv.org/abs/quant-ph/0210077"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c41320a4-7e4e-4ca7-95cf-0fabc066ac9a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}