dorsal/arxiv
View SchemaConsistency of Local Density Matrices is QMA-complete
| Authors | Yi-Kai Liu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0604166 |
| URL | https://arxiv.org/abs/quant-ph/0604166 |
Abstract
Suppose we have an n-qubit system, and we are given a collection of local density matrices rho_1,...,rho_m, where each rho_i describes a subset C_i of the qubits. We say that the rho_i are ``consistent'' if there exists some global state sigma (on all n qubits) that matches each of the rho_i on the subsets C_i. This generalizes the classical notion of the consistency of marginal probability distributions. We show that deciding the consistency of local density matrices is QMA-complete (where QMA is the quantum analogue of NP). This gives an interesting example of a hard problem in QMA. Our proof is somewhat unusual: we give a Turing reduction from Local Hamiltonian, using a convex optimization algorithm by Bertsimas and Vempala, which is based on random sampling. Unlike in the classical case, simple mapping reductions do not seem to work here.
{
"annotation_id": "e46532e5-85ab-462b-8302-25f9617fff46",
"date_created": "2026-03-02T18:02:27.717000Z",
"date_modified": "2026-03-02T18:02:27.717000Z",
"file_hash": "ea9e7c7155c208316b981a61ae0c5828cd21c2fe733b0765665c4c3e0fbeee02",
"private": false,
"record": {
"abstract": "Suppose we have an n-qubit system, and we are given a collection of local\ndensity matrices rho_1,...,rho_m, where each rho_i describes a subset C_i of\nthe qubits. We say that the rho_i are ``consistent\u0027\u0027 if there exists some\nglobal state sigma (on all n qubits) that matches each of the rho_i on the\nsubsets C_i. This generalizes the classical notion of the consistency of\nmarginal probability distributions.\n We show that deciding the consistency of local density matrices is\nQMA-complete (where QMA is the quantum analogue of NP). This gives an\ninteresting example of a hard problem in QMA. Our proof is somewhat unusual: we\ngive a Turing reduction from Local Hamiltonian, using a convex optimization\nalgorithm by Bertsimas and Vempala, which is based on random sampling. Unlike\nin the classical case, simple mapping reductions do not seem to work here.",
"arxiv_id": "quant-ph/0604166",
"authors": [
"Yi-Kai Liu"
],
"categories": [
"quant-ph"
],
"title": "Consistency of Local Density Matrices is QMA-complete",
"url": "https://arxiv.org/abs/quant-ph/0604166"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "17793385-01c1-439f-8f87-5a87caa357de",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}