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

arXiv:1506.06447 · Quantum Information and Computation

Quantum Merlin-Arthur with Clifford Arthur

Tomoyuki Morimae, Masahito Hayashi, Harumichi Nishimura, Keisuke Fujii

Published Nov 1, 2015• 4 citations
arXivHTMLPDF

Abstract

We show that the class QMA does not change even if we restrict Arthur’s computing ability to only Clifford gate operations (plus classical XOR gate). The idea is to use the fact that the preparation of certain single-qubit states, so called magic states, plus any Clifford gate operations are universal for quantum computing. If Merlin is honest, he sends the witness plus magic states to Arthur. If Merlin is malicious, he might send other states to Arthur, but Arthur can verify the correctness of magic states by himself. We also generalize the result to QIP(3): we show that the class QIP(3) does not change even if the computational power of the verifier is restricted to only Clifford gate operations (plus classical XOR gate).

DOI
10.26421/qic15.15-16-10

Related papers

Two-message quantum-Arthur-Merlin game with single-qubit measurements

Tomoyuki Morimae

We show that the class quantum-Arthur-Merlin (QAM) does not change even if the verifier's ability is restricted to only single-qubit measurements. To show the result, we use the idea of measurement-based quantum computing: the verifier, who can do only single-qubit measurements, can test the graph state sent from the prover and use it for his measurement-based quantum computing. Inspired by this construction, we also introduce a problem which we call stabilizer state optimization, and show that it is QMA-complete.

arXiv:1602.08656•Physical Review A•Jun 23, 2016•4 citations

Quantum Merlin-Arthur with noisy channel

Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura

What happens if in QMA the quantum channel between Merlin and Arthur is noisy? It is not difficult to show that such a modification does not change the computational power as long as the noise is not too strong so that errors are correctable with high probability, since if Merlin encodes the witness state in a quantum error-correction code and sends it to Arthur, Arthur can correct the error caused by the noisy channel. If we further assume that Arthur can do only single-qubit measurements, however, the problem becomes nontrivial, since in this case Arthur cannot do the universal quantum computation by himself. In this paper, we show that such a restricted complexity class is still equivalent to QMA. To show it, we use measurement-based quantum computing: honest Merlin sends the graph state to Arthur, and Arthur does fault-tolerant measurement-based quantum computing on the noisy graph state with only single-qubit measurements. By measuring stabilizer operators, Arthur also checks the correctness of the graph state. Although this idea itself was already used in several previous papers, these results cannot be directly used to the present case, since the test that checks the graph state used in these papers is so strict that even honest Merlin is rejected with high probability if the channel is noisy. We therefore introduce a more relaxed test that can accept not only the ideal graph state but also noisy graph states that are error-correctable.

arXiv:1608.04829•Aug 17, 2016•5 citations

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.

Computational Complexity•Jun 1, 2005•240 citations

Quantum proofs can be verified using only single-qubit measurements

Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch

Quantum Merlin Arthur (QMA) is the class of problems which, though potentially hard to solve, have a quantum solution that can be verified efficiently using a quantum computer. It thus forms a natural quantum version of the classical complexity class NP (and its probabilistic variant MA, Merlin-Arthur games), where the verifier has only classical computational resources. In this paper, we study what happens when we restrict the quantum resources of the verifier to the bare minimum: individual measurements on single qubits received as they come, one by one. We find that despite this grave restriction, it is still possible to soundly verify any problem in QMA for the verifier with the minimum quantum resources possible, without using any quantum memory or multiqubit operations. We provide two independent proofs of this fact, based on measurement-based quantum computation and the local Hamiltonian problem. The former construction also applies to ${\mathrm{QMA}}_{1}$, i.e., QMA with one-sided error.

arXiv:1510.06789•Physical Review A•Feb 22, 2016•32 citations

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 QMA is contained in 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•Jun 15, 2005•5 citations

PDQMA = DQMA = NEXP: QMA with Hidden Variables and Non-Collapsing Measurements

Scott Aaronson, Grewal, Sabee, Iyer, Vishnu +2 more

We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin’s witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.

•Jan 1, 2025•0 citations
We show that the class QMA does not change even if we restrict Arthur’s computing ability to only Clifford gate operations (plus classical XOR gate). The idea is to use the fact that the preparation of certain single-qubit states, so called magic states, plus any Clifford gate operations are universal for quantum computing. If Merlin is honest, he sends the witness plus magic states to Arthur. If Merlin is malicious, he might send other states to Arthur, but Arthur can verify the correctness of magic states by himself. We also generalize the result to QIP(3): we show that the class QIP(3) does not change even if the computational power of the verifier is restricted to only Clifford gate operations (plus classical XOR gate).
We show that the class quantum-Arthur-Merlin (QAM) does not change even if the verifier's ability is restricted to only single-qubit measurements. To show the result, we use the idea of measurement-based quantum computing: the verifier, who can do only single-qubit measurements, can test the graph state sent from the prover and use it for his measurement-based quantum computing. Inspired by this construction, we also introduce a problem which we call stabilizer state optimization, and show that it is QMA-complete.
What happens if in QMA the quantum channel between Merlin and Arthur is noisy? It is not difficult to show that such a modification does not change the computational power as long as the noise is not too strong so that errors are correctable with high probability, since if Merlin encodes the witness state in a quantum error-correction code and sends it to Arthur, Arthur can correct the error caused by the noisy channel. If we further assume that Arthur can do only single-qubit measurements, however, the problem becomes nontrivial, since in this case Arthur cannot do the universal quantum computation by himself. In this paper, we show that such a restricted complexity class is still equivalent to QMA. To show it, we use measurement-based quantum computing: honest Merlin sends the graph state to Arthur, and Arthur does fault-tolerant measurement-based quantum computing on the noisy graph state with only single-qubit measurements. By measuring stabilizer operators, Arthur also checks the correctness of the graph state. Although this idea itself was already used in several previous papers, these results cannot be directly used to the present case, since the test that checks the graph state used in these papers is so strict that even honest Merlin is rejected with high probability if the channel is noisy. We therefore introduce a more relaxed test that can accept not only the ideal graph state but also noisy graph states that are error-correctable.
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.
Quantum Merlin Arthur (QMA) is the class of problems which, though potentially hard to solve, have a quantum solution that can be verified efficiently using a quantum computer. It thus forms a natural quantum version of the classical complexity class NP (and its probabilistic variant MA, Merlin-Arthur games), where the verifier has only classical computational resources. In this paper, we study what happens when we restrict the quantum resources of the verifier to the bare minimum: individual measurements on single qubits received as they come, one by one. We find that despite this grave restriction, it is still possible to soundly verify any problem in QMA for the verifier with the minimum quantum resources possible, without using any quantum memory or multiqubit operations. We provide two independent proofs of this fact, based on measurement-based quantum computation and the local Hamiltonian problem. The former construction also applies to QMA1{\mathrm{QMA}}_{1}QMA1​, i.e., QMA with one-sided error.
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 is contained in 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.
We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin’s witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.