Quantum information and the PCP theorem

DOI10.1007/s00453-007-9033-6zbMath1192.68280arXivquant-ph/0504075OpenAlexW2109833455MaRDI QIDQ835644

Ran Raz

Publication date: 31 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0504075

zbMATH Keywords

quantum computationprobabilistically checkable proofsquantum informationquantum advicelow degree testquantum interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items

A broader view on the limitations of information processing and communication by nature ⋮ One-way reversible and quantum finite automata with advice ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Verifiable Stream Computation and Arthur--Merlin Communication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• PCP characterizations of NP: toward a polynomially-small error-probability
• Non-deterministic exponential time has two-prover interactive protocols
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• PSPACE has constant-round quantum interactive proof systems
• Polynomial time quantum computation with advice
• Improved low-degree testing and its applications
• Sub-constant error low degree test of almost-linear size
• Limitations of Quantum Advice and One-Way Communication
• Proof verification and the hardness of approximation problems
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Dense quantum coding and quantum finite automata
• The Knowledge Complexity of Interactive Proof Systems
• Probabilistic checking of proofs
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• Robust Characterizations of Polynomials with Applications to Program Testing

This page was built for publication: Quantum information and the PCP theorem