Consistency of Local Density Matrices is QMA-complete
arXiv: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.
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
References in corpus (4)
Cited by in corpus (10)
- Merlin-Arthur Games and Stoquastic Complexity
- Several natural BQP-Complete problems
- A Quantum Lovasz Local Lemma
- Quantum Earth mover's distance, No-go Quantum Kantorovich-Rubinstein theorem, and Quantum Marginal Problem
- Constraints on Multipartite Quantum Entropies
- On the complexity of approximating the diamond norm
- Testing quantum circuits and detecting insecure encryption
- A multiprover interactive proof system for the local Hamiltonian problem
- Testing non-isometry is QMA-complete
- Increasing the power of the verifier in Quantum Zero Knowledge