QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There

are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem

introduced by Kitaev. In this dissertation we show some new QMA-complete

problems.

The first one is ``Consistency of Local Density Matrices'': 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, ``Fermionic Local

Hamiltonian'' and ``N-representability,'' 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'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 ``stoquastic'' 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.