Commutative version of the local Hamiltonian problem and common
eigenspace problem
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:
- all operators Ha
are k-local;
- 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.)