dorsal/arxiv
View SchemaA new construction for a QMA complete 3-local Hamiltonian
| Authors | Daniel Nagaj, Shay Mozes |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0612113 |
| URL | https://arxiv.org/abs/quant-ph/0612113 |
| DOI | 10.1063/1.2748377 |
| Journal | J. Math. Phys. 48, 072104 (2007) |
Abstract
We present a new way of encoding a quantum computation into a 3-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions. Therefore, the weights of the terms in the Hamiltonian do not scale with the size of the problem as in previous constructions. This improves the construction by Kempe and Regev, who were the first to prove that 3-local Hamiltonian is complete for the complexity class QMA, the quantum analogue of NP. Quantum k-SAT, a restricted version of the local Hamiltonian problem using only projector terms, was introduced by Bravyi as an analogue of the classical k-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA with one-sided error (QMA_1) and that quantum 2-SAT is in P. We give an encoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only 3-local terms. As an intermediate step to this 3-local construction, we show that quantum 3-SAT for particles with dimensions 3x2x2 (a qutrit and two qubits) is QMA_1 complete. The complexity of quantum 3-SAT with qubits remains an open question.
{
"annotation_id": "212036c0-3393-4076-a6f8-ed77a4f0151b",
"date_created": "2026-03-02T18:02:33.505000Z",
"date_modified": "2026-03-02T18:02:33.505000Z",
"file_hash": "a6eeab065aa5c1afa3e8b4f58c47b6ba16b848069b66ded0d58dc57b7c7b0dec",
"private": false,
"record": {
"abstract": "We present a new way of encoding a quantum computation into a 3-local\nHamiltonian. Our construction is novel in that it does not include any terms\nthat induce legal-illegal clock transitions. Therefore, the weights of the\nterms in the Hamiltonian do not scale with the size of the problem as in\nprevious constructions. This improves the construction by Kempe and Regev, who\nwere the first to prove that 3-local Hamiltonian is complete for the complexity\nclass QMA, the quantum analogue of NP.\n Quantum k-SAT, a restricted version of the local Hamiltonian problem using\nonly projector terms, was introduced by Bravyi as an analogue of the classical\nk-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA\nwith one-sided error (QMA_1) and that quantum 2-SAT is in P. We give an\nencoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only\n3-local terms. As an intermediate step to this 3-local construction, we show\nthat quantum 3-SAT for particles with dimensions 3x2x2 (a qutrit and two\nqubits) is QMA_1 complete. The complexity of quantum 3-SAT with qubits remains\nan open question.",
"arxiv_id": "quant-ph/0612113",
"authors": [
"Daniel Nagaj",
"Shay Mozes"
],
"categories": [
"quant-ph"
],
"doi": "10.1063/1.2748377",
"journal_ref": "J. Math. Phys. 48, 072104 (2007)",
"title": "A new construction for a QMA complete 3-local Hamiltonian",
"url": "https://arxiv.org/abs/quant-ph/0612113"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f121b00e-17f0-4bfb-af7b-8b76d630d967",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}