A quantum characterization of NP

2007/09/05 by Hugue Blier, Alain Tapp, Blier, Hugue +1 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.0709.0738

openalex publication_date 2007/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.

Cited by

• Computational aspects of the trace norm contraction coefficient
• Entanglement Theory and the Quantum Simulation of Many-Body Physics

Related

• Quantum NP and a Quantum Hierarchy
• Quantum NP - A Survey
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
• Complexity limitations on quantum computation
• Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy