Quantum information and the PCP theorem
From MaRDI portal
Publication:835644
DOI10.1007/s00453-007-9033-6zbMath1192.68280arXivquant-ph/0504075MaRDI 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 computation; probabilistically checkable proofs; quantum information; quantum advice; low degree test; quantum interactive proofs
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
81P68: Quantum computation
Related Items
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
