2003/01/17 by Paweł Wocjan, Pawel Wocjan, Wocjan, Pawel +2
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0301087
7 pages
arxiv created 2003/01/17 · openalex publication_date 2003/01/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the NP complete problems MAX CUT and INDEPENDENT SET can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. He introduced the quantum complexity class BQNP as the quantum analog of NP, and showed that the 5-local Hamiltonian problem is BQNP-complete. It is not known whether the s-local Hamiltonian problem is BQNP-complete for s smaller than 5. Therefore it is interesting to determine what problems can be reduced to the s-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a 3-local Hamiltonian problem. We extend his result by showing that 2-locality is sufficient in order to encompass NP.