Commutative version of the k-local Hamiltonian problem and common eigenspace problem
| dc.creator | Bravyi, S. | |
| dc.creator | Vyalyi, M. | |
| dc.date | 2003-08-04 | |
| dc.date | 2004-12-16 | |
| dc.date.accessioned | 2026-07-07T06:07:32Z | |
| dc.date.available | 2026-07-07T06:07:32Z | |
| dc.description | 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)|ψ>=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. | |
| dc.description | 30 pages (more detailed version) | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0308021 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0308021 | |
| dc.identifier | Quantum Inf. and Comp., Vol. 5, No. 3 (2005) pp.187-215 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91326 | |
| dc.subject | Quantum Physics | |
| dc.title | Commutative version of the k-local Hamiltonian problem and common eigenspace problem | |
| dc.type | text |