Consistency of Local Density Matrices is QMA-complete
| dc.creator | Liu, Yi-Kai | |
| dc.date | 2006-04-21 | |
| dc.date | 2007-12-10 | |
| dc.date.accessioned | 2026-07-07T08:48:02Z | |
| dc.date.available | 2026-07-07T08:48:02Z | |
| dc.description | 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. | |
| dc.description | 13 pages; v2 has a better section on numerical precision, and various other improvements; will appear in RANDOM 2006; v3 fixes some long-neglected and possibly confusing typos in the proof of thm. 3 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0604166 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0604166 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143808 | |
| dc.subject | Quantum Physics | |
| dc.title | Consistency of Local Density Matrices is QMA-complete | |
| dc.type | text |