The Complexity of the Consistency and N-representability Problems for Quantum States

Understand

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.