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:2403.14108 · ACM Symposium on Principles of Distributed Computing (PODC)

On the Power of Quantum Distributed Proofs

Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura

Published Jun 5, 2024• 10 citations
arXivHTMLPDF

Abstract

Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In dQMA protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al. showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical. In this paper, we further investigate and characterize the power of the dQMA protocols for various decision problems.

DOI
10.1145/3662158.3662788

Related papers

Reducing Provers in Distributed Quantum Verification

Alex Della Schiava, Atsuya Hasegawa, François Le Gall +1 more

In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.

arXiv:2611.12600•Nov 9, 2026•0 citations

Brief Announcement: Distributed Quantum Proofs for Replicated Data

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura +1 more

The paper tackles the issue of $\textit{checking}$ that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign $\textit{certificates}$ to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the data set is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed $\textit{quantum}$ Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.

arXiv:2002.10018•Leibniz international proceedings in informatics•Jan 1, 2020•9 citations

Quantum Advantage in Local Certification of Graph Properties

Benjamin Jauregui, Masayuki Miyamoto

Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the maximum certificate size at any vertex. Fraigniaud et al. (ITCS 2021) introduced the distributed quantum Merlin-Arthur (dQMA) model and proved an exponential quantum advantage for distributed equality, measured in input-string length. We resolve a question of Hasegawa, Kundu, and Nishimura (PODC 2024) by establishing unconditional exponential and polynomial quantum advantages for graph properties, which depend only on network topology, with complexity measured in the number $n$ of vertices. For every fixed integer $μ\ge 1$, we construct a graph property admitting a one-round dQMA protocol with $O(μ\log n)$-qubit certificates and messages, whereas every $μ$-round distributed Merlin-Arthur (dMA) protocol requires $Ω(n/(μ\log^2 n))$-bit certificates. We also give a one-round dQMA protocol for graph symmetry, the existence of a nontrivial automorphism, with $\widetilde{O}(n^{5/3})$-qubit certificates. This yields a polynomial advantage over one-round dMA protocols, for which an $Ω(n^2)$-bit certificate lower bound is known.

arXiv:2611.08076•Nov 5, 2026•0 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 the power of quantum proofs

Ran Raz, Amir Shpilka

We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.

Conference on Computational Complexity•Jun 21, 2004•31 citations

Brief Announcement: Distributed Quantum Interactive Proofs

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

The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an $n$-node network $G$ can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including $G$ itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The first result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our result shows that for any constant~$k$, the class of languages that can be decided by a $k$-turn classical (i.e., non-quantum) distributed interactive protocol with $f(n)$-bit certificate size is contained in the class of languages that can be decided by a $5$-turn distributed quantum interactive protocol with $O(f(n))$-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction \emph{classical} technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well.

arXiv:2210.01390•Leibniz international proceedings in informatics•Jan 1, 2022•10 citations
Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In dQMA protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al. showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical. In this paper, we further investigate and characterize the power of the dQMA protocols for various decision problems.
In the distributed quantum Merlin-Arthur (dQMA\mathsf{dQMA}dQMA) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to kkk unentangled provers, denoted by dQMAS(k)\mathsf{dQMAS}(k)dQMAS(k). In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from kkk to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from kkk to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding dQMAS=dQMAS(k)\mathsf{dQMAS} = \mathsf{dQMAS}(k)dQMAS=dQMAS(k).
The paper tackles the issue of checking\textit{checking}checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates\textit{certificates}certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the data set is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum\textit{quantum}quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms.
Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the maximum certificate size at any vertex. Fraigniaud et al. (ITCS 2021) introduced the distributed quantum Merlin-Arthur (dQMA) model and proved an exponential quantum advantage for distributed equality, measured in input-string length. We resolve a question of Hasegawa, Kundu, and Nishimura (PODC 2024) by establishing unconditional exponential and polynomial quantum advantages for graph properties, which depend only on network topology, with complexity measured in the number nnn of vertices. For every fixed integer μ≥1μ\ge 1μ≥1, we construct a graph property admitting a one-round dQMA protocol with O(μlog⁡n)O(μ\log n)O(μlogn)-qubit certificates and messages, whereas every μμμ-round distributed Merlin-Arthur (dMA) protocol requires Ω(n/(μlog⁡2n))Ω(n/(μ\log^2 n))Ω(n/(μlog2n))-bit certificates. We also give a one-round dQMA protocol for graph symmetry, the existence of a nontrivial automorphism, with O~(n5/3)\widetilde{O}(n^{5/3})O(n5/3)-qubit certificates. This yields a polynomial advantage over one-round dMA protocols, for which an Ω(n2)Ω(n^2)Ω(n2)-bit certificate lower bound is known.
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.
We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an nnn-node network GGG can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including GGG itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The first result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our result shows that for any constant~kkk, the class of languages that can be decided by a kkk-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)f(n)f(n)-bit certificate size is contained in the class of languages that can be decided by a 555-turn distributed quantum interactive protocol with O(f(n))O(f(n))O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction \emph{classical} technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well.