Stronger methods of making quantum interactive proofs perfectly complete
From MaRDI portal
Abstract: This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP_1(2) of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an -message quantum interactive proof system necessarily has an -message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires messages if not using the parallelization result.
Recommendations
- Stronger methods of making quantum interactive proofs perfectly complete
- scientific article; zbMATH DE number 5899305
- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- PSPACE has constant-round quantum interactive proof systems
- Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 5899305 (Why is no real title available?)
- scientific article; zbMATH DE number 4057011 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- A de Finetti representation for finite symmetric quantum states
- Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Coding theorem and strong converse for quantum channels
- Completely positive linear maps on complex matrices
- Conditional hardness for satisfiable 3-CSPs
- Efficient algorithm for a quantum analogue of 2-SAT
- Fast amplification of QMA
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- How hard is it to approximate the Jones polynomial?
- Linear transformations which preserve trace and positive semidefiniteness of operators
- On perfect completeness for QMA
- On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
- One-and-a-half quantum de Finetti theorems
- PSPACE has constant-round quantum interactive proof systems
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Properties of local quantum operations with shared entanglement
- QIP = PSPACE
- Quantum Arthur-Merlin games
- Quantum information theory
- Query efficient PCPs with perfect completeness
- The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach
- The complexity of promise problems with applications to public-key cryptography
- The detectability lemma and quantum gap amplification
- Using entanglement in quantum multi-prover interactive proofs
Cited in
(6)- Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
- Distributed quantum proofs for replicated data
- On perfect completeness for QMA
- Generalized quantum Arthur-Merlin games
- Stronger methods of making quantum interactive proofs perfectly complete
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
This page was built for publication: Stronger methods of making quantum interactive proofs perfectly complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954372)
