@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}
}