dorsal/arxiv
View SchemaCommutative version of the k-local Hamiltonian problem and common eigenspace problem
| Authors | S. Bravyi, M. Vyalyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0308021 |
| URL | https://arxiv.org/abs/quant-ph/0308021 |
| Journal | Quantum Inf. and Comp., Vol. 5, No. 3 (2005) pp.187-215 |
Abstract
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)^{\otimes n} and a string of real numbers h_1,...,h_r. The problem is to determine whether a common eigenspace specified by equalities (H_a - h_a)|\psi>=0, a=1,...,r, has a positive dimension. We consider two cases: (i) all operators H_a are k-local; (ii) all operators H_a are factorized. It can be easily shown that both problems belong to the class QMA - the 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 h_a=0.
{
"annotation_id": "b3b5b4a9-619f-4538-98d6-38c0db066712",
"date_created": "2026-03-02T18:01:59.757000Z",
"date_modified": "2026-03-02T18:01:59.757000Z",
"file_hash": "c3d0932b876451db9faedfa65a2b9ea81ca41336b1960b4c9fe5016301ef36b6",
"private": false,
"record": {
"abstract": "We study the complexity of a problem \"Common Eigenspace\" -- verifying\nconsistency of eigenvalue equations for composite quantum systems. The input of\nthe problem is a family of pairwise commuting Hermitian operators H_1,...,H_r\non a Hilbert space (C^d)^{\\otimes n} and a string of real numbers h_1,...,h_r.\nThe problem is to determine whether a common eigenspace specified by equalities\n(H_a - h_a)|\\psi\u003e=0, a=1,...,r, has a positive dimension. We consider two\ncases: (i) all operators H_a are k-local; (ii) all operators H_a are\nfactorized. It can be easily shown that both problems belong to the class QMA -\nthe quantum analogue of NP, and that some NP-complete problems can be reduced\nto either (i) or (ii). A non-trivial question is whether the problems (i) or\n(ii) belong to NP? We show that the answer is positive for some special values\nof k and d. Also we prove that the problem (ii) can be reduced to its special\ncase, such that all operators H_a are factorized projectors and all h_a=0.",
"arxiv_id": "quant-ph/0308021",
"authors": [
"S. Bravyi",
"M. Vyalyi"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Inf. and Comp., Vol. 5, No. 3 (2005) pp.187-215",
"title": "Commutative version of the k-local Hamiltonian problem and common eigenspace problem",
"url": "https://arxiv.org/abs/quant-ph/0308021"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ce12c853-5ab2-4715-bd57-6fab2131c12e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}