Parallelization, amplification, and exponential time simulation of quantum interactive proof systems

DOI10.1145/335305.335387zbMath1296.68057OpenAlexW1989051052MaRDI QIDQ3192033

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335387

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (28)

Complete Problem for Perfect Zero-Knowledge Quantum Proof ⋮ Quantum information and the PCP theorem ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Parallel approximation of min-max problems ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ Complexity limitations on one-turn quantum refereed games ⋮ Some geometric interpretations of quantum fidelity ⋮ Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ Quantum multi-prover interactive proof systems with limited prior entanglement. ⋮ General properties of quantum bit commitments (extended abstract) ⋮ Unnamed Item ⋮ Classical binding for quantum commitments ⋮ A quantum characterization of NP ⋮ Generalized Quantum Arthur--Merlin Games ⋮ Quantum Commitments from Complexity Assumptions ⋮ Constant-space quantum interactive proofs against multiple provers ⋮ Uniformity of quantum circuit families for error-free algorithms ⋮ General Properties of Quantum Zero-Knowledge Proofs ⋮ Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families ⋮ An application of quantum finite automata to interactive proof systems ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\) ⋮ Optimal quantum networks and one-shot entropies ⋮ Unnamed Item ⋮ QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge ⋮ Rank-one quantum games ⋮ PSPACE has constant-round quantum interactive proof systems ⋮ One complexity theorist's view of quantum computing ⋮ Quantum commitments from complexity assumptions

This page was built for publication: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems