A quantum characterization of NP

DOI10.1007/S00037-011-0016-2zbMATH Open1288.68079arXiv0709.0738OpenAlexW2006872837MaRDI QIDQ445251FDOQ445251

Alain Tapp, Hugue Blier

Publication date: 24 August 2012

Published in: Computational Complexity (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0709.0738

zbMATH Keywords

quantum complexityinteractive proof

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Semidefinite Programming
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Quantum Arthur-Merlin games
• Quantum entanglement and communication complexity
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• A quantum characterization of NP
• Title not available (Why is that?)

Cited In (6)

• Shorter unentangled proofs for ground state connectivity
• Title not available (Why is that?)
• A quantum characterization of NP
• Title not available (Why is that?)
• Quantum free games
• The power of unentangled quantum proofs with non-negative amplitudes

This page was built for publication: A quantum characterization of NP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445251)