Consistency of Local Density Matrices is QMA-complete

Details Consistency of Local Density Matrices is QMA-complete Consistency of Local Density Matrices is QMA-complete

2006-04-21

arxiv.org/abs/quant-ph/0604166v3

Physics

Quantum Physics

13 pages; v2 has a better section on numerical precision, and various other improvements; will appear in RANDOM 2006; v3 fixes

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Consistency of Local Density Matrices is QMA-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Consistency of Local Density Matrices is QMA-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consistency of Local Density Matrices is QMA-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-33921