Complexity limitations on one-turn quantum refereed games

DOI10.1007/s00224-022-10105-9arXiv2002.01509OpenAlexW3005431088MaRDI QIDQ6038714

Soumik Ghosh, John Watrous

Publication date: 2 May 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.01509

zbMATH Keywords

game theoryquantum computingcomplexity theory

Mathematics Subject Classification ID

Game theory (91Axx) Theory of computing (68Qxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel approximation of min-max problems
• User-friendly tail bounds for sums of random matrices
• Quantum Arthur-Merlin games
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• On the complexity of succinct zero-sum games
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The complexity of two-person zero-sum games in extensive form
• Symmetric alternation captures BPP
• On sparse approximations to randomized strategies and convex combinations
• More on BPP and the polynomial-time hierarchy
• PP is closed under intersection
• Fast Monte Carlo algorithms for permutation groups
• PP is closed under truth-table reductions
• Complexity limitations on quantum computation
• Simple strategies for large zero-sum games with applications to complexity theory
• Zero-knowledge against quantum attacks
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• The Knowledge Complexity of Interactive Proof Systems
• Alternation
• Random Debaters and the Hardness of Approximating Stochastic Functions
• The knowledge complexity of interactive proof-systems
• The Theory of Quantum Information
• STACS 2005
• A basic course in probability theory
• Quantum Information Theory

This page was built for publication: Complexity limitations on one-turn quantum refereed games