Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Quadratic Simulations of Merlin–Arthur Games

Thomas W. Watson

Published Jan 1, 2018• 1 citation
Publisher
DOI
10.1007/978-3-319-77404-6_62

Related papers

Classical and quantum Merlin–Arthur automata

Abuzer Yakaryılmaz

arXiv:2212.13801•Quantum Information Processing•Dec 5, 2025•1 citation

Quadratic Simulations of Merlin–Arthur Games

Thomas W. Watson

The known proofs of MA ⊆ PP incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which MA-TIME ( t ) ⊈ P-TIME ( o ( t 2 )). We also show that 2-sided-error Merlin–Arthur games can be simulated by 1-sided-error Arthur–Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika Göös) that there is an oracle relative to which MA ⊈ NP BPP (which was previously known to hold by a proof using generics).

ACM Transactions on Computation Theory•May 3, 2020•1 citation

Simulation of the quantum Bertrand–Edgeworth game

Juan Grau-Climent, Luis García-Pérez, Juan Carlos Losada +1 more

Quantum Information Processing•Nov 16, 2023•3 citations

Quantum games

J.M.A Figueiredo

Physica A Statistical Mechanics and its Applications•Jan 27, 2004•1 citation

Quantum Arthur–Merlin games

Chris Marriott, John Watrous

This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that $$ {\text{QMA}} \subseteq {\text{PP}}. $$ Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

arXiv:cs/0506068•Computational Complexity•Jun 1, 2005•306 citations

Quantum games

Παναγιώτης Αποστολίδης, Εύαγγελος Κ. Κοντονικολάου

•Jan 1, 2025•0 citations
The known proofs of MA ⊆ PP incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which MA-TIME ( t ) ⊈ P-TIME ( o ( t 2 )). We also show that 2-sided-error Merlin–Arthur games can be simulated by 1-sided-error Arthur–Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika Göös) that there is an oracle relative to which MA ⊈ NP BPP (which was previously known to hold by a proof using generics).
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA⊆PP. {\text{QMA}} \subseteq {\text{PP}}. QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.