Quantum Arthur–Merlin games

By Chris Marriott, John Watrous. Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., 2004

297 citations recorded by the source corpus.

Abstract.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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/db5e4a46def6dc05b47e594767c86e9cefe8d2df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Shadow tomography of quantum states (2017, methodology): “The ﬁrst way is by adapting the in-place ampliﬁcation procedure of Marriott and Watrous [23].”
Adiabatic Quantum Computing (2016, methodology): “(Marriott and Watrous, 2005).”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “□ The improved version of the Marriott-Watrous [46] QMA amplification procedure due Nagaj et al. [47] can also be seen as a direct corollary of our singular value discrimination result.”
The Complexity of the Local Hamiltonian Problem (2004, background): “In a related result, Marriott and Watrous [14] showed that exponentially small ε can be achieved without amplification with a polynomial overhead in the verifier’s computation.”
Exponential improvement in precision for simulating sparse Hamiltonians (2013, methodology): “The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [25] (see also related work using amplitude amplification to obtain a quadratic improvement [27]).”
Quantum Computational Complexity (2008, methodology): “For instance, only the trivial lower bounds PSPACE ⊆ MIP∗ and QIP ⊆ QMIP, and no good upper bounds, are known.”
Faithful Squashed Entanglement (2010, background): “[60]). It is natural to ask how robust this definition is. A few results are known in this direction: For example, it is possible to amplify the soundness and completeness parameters to exponential accuracy, even without enlarging the proof size [ 61 ].”