



@article {1422,
	title = {Consistency of Local Density Matrices is QMA-complete},
	journal = {Proc. RANDOM },
	year = {2006},
	month = {2006/04/21},
	pages = {438-449},
	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 {\textquoteleft}{\textquoteleft}consistent{\textquoteright}{\textquoteright} 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.
},
	url = {http://arxiv.org/abs/quant-ph/0604166v3},
	author = {Yi-Kai Liu}
}
