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

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

2007-12-18

arxiv.org/abs/0712.3041v1

Physics

Quantum Physics

PhD thesis. Yay, no more grad school!! (Finished in August, but did not get around to posting it until now.) 91 pages, a few f

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of the Consistency and N-representability Problems for Quantum States does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of the Consistency and N-representability Problems for Quantum States, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of the Consistency and N-representability Problems for Quantum States will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-145667