PSPACE has constant-round quantum interactive proof systems
From MaRDI portal
Publication:1870552
DOI10.1016/S0304-3975(01)00375-9zbMATH Open1026.68121MaRDI QIDQ1870552FDOQ1870552
Authors: John Watrous 
Publication date: 14 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Computability
- Quantum cryptography: public key distribution and coin tossing
- Quantum computational networks
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Probabilistic checking of proofs
- Exponential separation of quantum and classical communication complexity
- A proof of the security of quantum key distribution (extended abstract)
- Non-deterministic exponential time has two-prover interactive protocols
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- The Knowledge Complexity of Interactive Proof Systems
- A universal two-bit gate for quantum computation
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Title not available (Why is that?)
- On the power of multi-prover interactive protocols
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Finite state verifiers I
- Title not available (Why is that?)
- Interactive proof systems with polynomially bounded strategies
- IP = SPACE
- PSPACE is provable by two provers in one round
Cited In (20)
- New Limits to Classical and Quantum Instance Compression
- Constant-space quantum interactive proofs against multiple provers
- Interactive proofs with quantum finite automata
- Quantum commitments from complexity assumptions
- Bidirectional controlled teleportation by using nine-qubit entangled state in noisy environments
- Generalized Quantum Arthur--Merlin Games
- Bidirectional controlled quantum teleportation and secure direct communication using five-qubit entangled state
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
- Quantum commitments from complexity assumptions
- Rank-one quantum games
- Quantum entanglement as a new information processing resource
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- How to Verify a Quantum Computation
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Quantum information and the PCP theorem
- PSPACE is provable by two provers in one round
- An application of quantum finite automata to interactive proof systems
- STACS 2005
- Zero-knowledge proof systems for QMA
- General Properties of Quantum Zero-Knowledge Proofs
This page was built for publication: PSPACE has constant-round quantum interactive proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1870552)
