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:2508.21020

QIP $ \subseteq $ AM(2QCFA)

Abuzer Yakaryılmaz

Published Aug 28, 2025• 1 citation
arXivHTMLPDF

Abstract

The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).

DOI
10.48550/arxiv.2508.21020

Related papers

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems

Zeyu Chen, Junde Wu

Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur--Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in $\mathbf{ATIME}(2^{O(n)})$, and perfect-completeness strong verification for every language in $\mathbf{PSPACE}$. These results establish that the remarkable verification power of affine finite-state automata is structural.

arXiv:2509.07857•Sep 9, 2025•1 citation

Generalized Quantum Arthur--Merlin Games

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

This paper investigates the role of interaction and coins in quantum Arthur--Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur--Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs (to share with the prover). This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur--Merlin games where both of the two messages are quantum (denoted qq-QAM in this paper) does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class ${qq-QAM}_1$, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur--Merlin games: it is proved that, for any constant $m\geq2$, the class of problems having $m$-turn quantum Arthur--Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur--Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.

arXiv:1312.4673•SIAM Journal on Computing•Jan 1, 2019•12 citations

Quantum Information and Variants of Interactive Proof Systems

Sarvagya Upadhyay

For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.

•Aug 24, 2011•1 citation

Quantum Multiprover Interactive Proofs with Communicating Provers

Michael Ben-Or, Avinatan Hassidim, Haran Pilpel

We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.

SIAM Journal on Computing•Jan 1, 2014•5 citations

STATE SUCCINCTNESS OF TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES

Shenggen Zheng, Daowen Qiu, Lvzhou Li

Two-way quantum automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any fix m ∈ ℤ + , we show that (1) there is a promise problem A meq which can be solved by 2QCFA in polynomial expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m + 2, and ; (2) there exists a language L mtwin which can be recognized by 2QCFA in exponential expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2 m , and ; where b is a constant number.

International Conference on Quantitative Logic and Soft Computing (QLSC)•Apr 1, 2012•5 citations

Generalized Quantum Arthur-Merlin Games

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

This paper investigates the role of interaction and coins in quantum Arthur-Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur-Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs. This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur-Merlin games where both of the two messages are quantum, denoted qq-QAM in this paper, does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus, qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class qq-QAM_1, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur-Merlin games: it is proved that, for any constant m >= 2, the class of problems having $m$-turn quantum Arthur-Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur-Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.

Leibniz international proceedings in informatics•Jan 1, 2015•4 citations
The class of languages having polynomial-time classical or quantum interactive proof systems (IP\mathsf{IP}IP or QIP\mathsf{QIP}QIP, respectively) is identical to PSPACE\mathsf{PSPACE}PSPACE. We show that PSPACE\mathsf{PSPACE}PSPACE (and so QIP\mathsf{QIP}QIP) is subset of AM(2QCFA)\mathsf{AM(2QCFA)}AM(2QCFA), the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness).
Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur--Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in ATIME(2O(n))\mathbf{ATIME}(2^{O(n)})ATIME(2O(n)), and perfect-completeness strong verification for every language in PSPACE\mathbf{PSPACE}PSPACE. These results establish that the remarkable verification power of affine finite-state automata is structural.
This paper investigates the role of interaction and coins in quantum Arthur--Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur--Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs (to share with the prover). This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur--Merlin games where both of the two messages are quantum (denoted qq-QAM in this paper) does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class qq−QAM1{qq-QAM}_1qq−QAM1​, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur--Merlin games: it is proved that, for any constant m≥2m\geq2m≥2, the class of problems having mmm-turn quantum Arthur--Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur--Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.
For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.
We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.
Two-way quantum automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any fix m ∈ ℤ + , we show that (1) there is a promise problem A meq which can be solved by 2QCFA in polynomial expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m + 2, and ; (2) there exists a language L mtwin which can be recognized by 2QCFA in exponential expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2 m , and ; where b is a constant number.
This paper investigates the role of interaction and coins in quantum Arthur-Merlin games (also called public-coin quantum interactive proof systems). While the existing model restricts the messages from the verifier to be classical even in the quantum setting, the present work introduces a generalized version of quantum Arthur-Merlin games where the messages from the verifier can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs. This generalization turns out to provide several novel characterizations of quantum interactive proof systems with a constant number of turns. First, it is proved that the complexity class corresponding to two-turn quantum Arthur-Merlin games where both of the two messages are quantum, denoted qq-QAM in this paper, does not change by adding a constant number of turns of classical interaction prior to the communications of qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this paper presents a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking properties related to quantum circuits, and thus, qq-QAM may provide a good measure in computational complexity theory. It is further proved that the class qq-QAM_1, the perfect-completeness variant of qq-QAM, gives new bounds for standard well-studied classes of two-turn quantum interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of classical and quantum interactions in quantum Arthur-Merlin games: it is proved that, for any constant m >= 2, the class of problems having mmm-turn quantum Arthur-Merlin proof systems is either equal to PSPACE or equal to the class of problems having two-turn quantum Arthur-Merlin proof systems of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem.