Generalized Quantum Arthur--Merlin Games

DOI10.1137/17M1160173zbMath1421.68052MaRDI QIDQ4634057

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

entanglementquantum computinginteractive proof systemscomplete problemsArthur-Merlin games

Mathematics Subject Classification ID

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

Related Items (1)

QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum Arthur-Merlin games
• BPP and the polynomial hierarchy
• Games against nature
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The transition probability in the state space of a \(^*\)-algebra
• PSPACE has constant-round quantum interactive proof systems
• Zero-knowledge against quantum attacks
• Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• New Limits to Classical and Quantum Instance Compression
• Testing Quantum Circuits and Detecting Insecure Encryption
• The Knowledge Complexity of Interactive Proof Systems
• Quantum computations: algorithms and error correction
• Algebraic methods for interactive proof systems
• IP = PSPACE
• IP = SPACE
• The Theory of Quantum Information
• Cryptographic distinguishability measures for quantum-mechanical states
• Two-Message Quantum Interactive Proofs Are in PSPACE
• Algorithms and Computation
• QIP = PSPACE
• Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
• Entanglement in Interactive Proof Systems with Binary Answers
• Additivity and distinguishability of random unitary channels
• Note on discrimination information and variation (Corresp.)
• Quantum Information Theory

This page was built for publication: Generalized Quantum Arthur--Merlin Games