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