#
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
*H*_{1}, ..., *H*_{r} on a
Hilbert space (*C*^{d})^{⊗n} and a
string of real numbers λ_{1}, ...,
λ_{r}. The problem is to determine whether
the common eigenspace specified by equalities *H*_{a}
|ψ> = λ_{a} |ψ> for *a* = 1,
..., *r* has a positive dimension. We consider two cases:

- all operators
*H*_{a}
are *k*-local;
- all operators
*H*_{a} 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
*H*_{a} are factorized projectors and
all λ_{a} = 0.
(Based on a paper
by Sergey Bravyi and Mikhail Vyalyi in *Quantum Inf. and Comp.* 2005.)