CS 269S, Spring 2012: Theory Seminar
Bren Hall, Room 1420
May 4, 2012:

Commutative version of the local Hamiltonian problem and common eigenspace problem

Jenny Lam

We study the complexity of a problem "Common Eigenspace": verifying consistency of eigenvalue equations for composite quantum systems. The input of the problem is a family of pairwise commuting Hermitian operators H1, ..., Hr on a Hilbert space (Cd)⊗n and a string of real numbers λ1, ..., λr. The problem is to determine whether the common eigenspace specified by equalities Ha |ψ> = λa |ψ> for a = 1, ..., r has a positive dimension. We consider two cases:

  1. all operators Ha are k-local;
  2. all operators Ha are factorized.
It can be easily shown that both problems belong to the class QMA, a quantum analogue of NP, and that some NP-complete problems can be reduced to either (i) or (ii). A non-trivial question is whether the problems (i) or (ii) belong to NP? We show that the answer is positive for some special values of k and d. Also we prove that the problem (ii) can be reduced to its special case, such that all operators Ha are factorized projectors and all λa = 0.

(Based on a paper by Sergey Bravyi and Mikhail Vyalyi in Quantum Inf. and Comp. 2005.)