{
  "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
}