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:2212.13801 · Quantum Information Processing

Classical and quantum Merlin–Arthur automata

Abuzer Yakaryılmaz

Published Dec 5, 2025• 1 citation
arXivHTMLPDF
DOI
10.1007/s11128-025-05005-z

Related papers

Quantum Automata: An Overview

Stanley Gudder

International Journal of Theoretical Physics•Sep 1, 1999•20 citations

Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?

Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami

This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.

arXiv:quant-ph/0306051•Chicago Journal of Theoretical Computer Science•Jun 6, 2003•63 citations

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

François Le Gall, Miyamoto, Masayuki, Harumichi Nishimura

The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [FOCS 2023] under the term \emph{state synthesis}. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state $U\ketψ$ at the rightmost node of the line, where $\ketψ$ is a quantum state given at the leftmost node and $U$ is a unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.

arXiv:2210.01389•Leibniz international proceedings in informatics•Oct 4, 2022•9 citations

On quantum-mechanical automata

Asher Peres

Physics Letters A•Apr 1, 1984•23 citations

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

On quantum-mechanical automata

David Z. Albert

Physics Letters A•Oct 1, 1983•90 citations
This paper introduces quantum ``multiple-Merlin''-Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.
The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [FOCS 2023] under the term \emph{state synthesis}. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state U∣ψ⟩U\ketψU∣ψ⟩ at the rightmost node of the line, where ∣ψ⟩\ketψ∣ψ⟩ is a quantum state given at the leftmost node and UUU is a unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.
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.