dorsal/arxiv
View SchemaEfficient algorithm for a quantum analogue of 2-SAT
| Authors | Sergey Bravyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0602108 |
| URL | https://arxiv.org/abs/quant-ph/0602108 |
Abstract
Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density matrices have support on prescribed subspaces. We present a classical algorithm solving quantum 2-SAT in a polynomial time. It generalizes the well-known algorithm for the classical 2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the complexity class QMA with one-sided error.
{
"annotation_id": "0b554a89-33b3-4234-a615-549cdf9f359b",
"date_created": "2026-03-02T18:02:23.829000Z",
"date_modified": "2026-03-02T18:02:23.829000Z",
"file_hash": "5943af76786910cbc5ec9a5b95997307bab79f47b287f78344b97c74d14473aa",
"private": false,
"record": {
"abstract": "Complexity of a quantum analogue of the satisfiability problem is studied.\nQuantum k-SAT is a problem of verifying whether there exists n-qubit pure state\nsuch that its k-qubit reduced density matrices have support on prescribed\nsubspaces. We present a classical algorithm solving quantum 2-SAT in a\npolynomial time. It generalizes the well-known algorithm for the classical\n2-SAT. Besides, we show that for any k\u003e=4 quantum k-SAT is complete in the\ncomplexity class QMA with one-sided error.",
"arxiv_id": "quant-ph/0602108",
"authors": [
"Sergey Bravyi"
],
"categories": [
"quant-ph"
],
"title": "Efficient algorithm for a quantum analogue of 2-SAT",
"url": "https://arxiv.org/abs/quant-ph/0602108"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "daba9cf5-902f-4133-946d-35b893fc7099",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}