Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

DOI10.1137/140971944zbMath1357.68071arXiv1210.1290OpenAlexW2027440986WikidataQ113779153 ScholiaQ113779153MaRDI QIDQ2954372

Hirotada Kobayashi, Harumichi Nishimura, François Le Gall

Publication date: 13 January 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

entanglementquantum computinginteractive proof systemsperfect completeness

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (2)

Generalized Quantum Arthur--Merlin Games ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)

Cites Work

• Using entanglement in quantum multi-prover interactive proofs
• Quantum Arthur-Merlin games
• Completely positive linear maps on complex matrices
• PSPACE has constant-round quantum interactive proof systems
• One-and-a-half quantum de Finetti theorems
• Linear transformations which preserve trace and positive semidefiniteness of operators
• Zero-knowledge against quantum attacks
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
• Proof verification and the hardness of approximation problems
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• A de Finetti representation for finite symmetric quantum states
• The complexity of promise problems with applications to public-key cryptography
• Probabilistic checking of proofs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Coding theorem and strong converse for quantum channels
• The detectability lemma and quantum gap amplification
• Conditional hardness for satisfiable 3-CSPs
• QIP = PSPACE
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
• The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach
• Quantum Information Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete