Quantum information and the PCP theorem
From MaRDI portal
Publication:835644
DOI10.1007/s00453-007-9033-6zbMath1192.68280arXivquant-ph/0504075OpenAlexW2109833455MaRDI QIDQ835644
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
quantum computationprobabilistically checkable proofsquantum informationquantum advicelow degree testquantum interactive proofs
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
