@article {1424, title = {The Complexity of the Consistency and N-representability Problems for Quantum States}, year = {2007}, month = {2007/12/18}, type = {PhD Thesis, Univ. of California, San Diego}, abstract = { QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the {\textquoteleft}{\textquoteleft}Local Hamiltonian{\textquoteright}{\textquoteright} problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is {\textquoteleft}{\textquoteleft}Consistency of Local Density Matrices{\textquoteright}{\textquoteright}: given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, {\textquoteleft}{\textquoteleft}Fermionic Local Hamiltonian{\textquoteright}{\textquoteright} and {\textquoteleft}{\textquoteleft}N-representability,{\textquoteright}{\textquoteright} are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960{\textquoteright}s, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and {\textquoteleft}{\textquoteleft}stoquastic{\textquoteright}{\textquoteright} systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state. }, url = {http://arxiv.org/abs/0712.3041v1}, author = {Yi-Kai Liu} }