Reducing Provers in Distributed Quantum Verification

Reducing Provers in Distributed Quantum Verification Alex Della Schiava1 , Atsuya Hasegawa1 , François Le Gall1 , and Harumichi Nishimura2 1

Graduate School of Mathematics, Nagoya University, Japan Graduate School of Informatics, Nagoya University, Japan

arXiv:2611.12600v1 [quant-ph] 9 Nov 2026

2

Abstract In the distributed quantum Merlin–Arthur (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 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 dQMAS = dQMAS(k).

1

Introduction

Distributed verification asks how nodes can verify a global property of a network or its inputs despite having only local information. In proof-labeling schemes, introduced by Korman, Kutten, and Peleg [KKP10], and locally checkable proofs, studied by Göös and Suomela [GS16], an untrusted prover assists the nodes by supplying a proof, which they check through local computation and communication. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. Fraigniaud, Le Gall, Nishimura, and Paz [FLGNP21] introduced a quantum counterpart of this setting: distributed quantum Merlin–Arthur protocols, or dQMA. The proof is now a quantum state, and verification proceeds in synchronous rounds. In each round, the nodes perform local quantum operations and exchange quantum messages with their neighbors. The protocol accepts if and only if all nodes accept. On a yes-instance, some witness is accepted with high probability; on a no-instance, every witness must lead to rejection by at least one node with high probability. The quantum setting can substantially reduce the resources required for distributed verification: for equality on fixed-size networks, it offers exponentially smaller proofs [FLGNP21]. Le Gall, Miyamoto, and Nishimura [LGMN23a] developed distributed state synthesis and showed that additional resources can compensate for restricting communication to classical messages. They also reduced constant-turn classical interactive proofs to five quantum turns with constantfactor overhead in proof size [LGMN23b]. Hasegawa, Kundu, and Nishimura [HKN24] established further protocols and lower bounds, and proposed studying a variant of dQMA in which k provers supply mutually unentangled proofs, denoted dQMA(k).

1

Node u

Node v

Prover A

Prover B

Proof from A to u

Proof from B to u

Unentangled

Unentangled

Proof from A to v

Proof from B to v

Figure 1: The dQMAS(2) model on a two-node network. Amber and blue represent the proofs sent by provers A and B, respectively. The two proofs are unentangled, and each proof is separable across nodes. Gray bands span the registers held by nodes u and v. In the centralized setting, Kobayashi, Matsumoto, and Yamakami [KMY03] introduced QMA(k), where a polynomial-time quantum verifier receives mutually unentangled quantum witnesses from k provers. Ignoring all but one proof gives QMA ⊆ QMA(k), but whether additional provers offer greater power is a longstanding open question [Gha24, JLW26]. In the classical setting, the answer is negative: k witnesses can always be concatenated into one polynomiallength proof and checked as before. In contrast, combining k quantum witnesses into one proof allows entanglement between the registers, introducing cheating strategies for which the original soundness guarantee need not hold. Harrow and Montanaro [HM13] showed that two provers always suffice: QMA(2) = QMA(k) for every polynomially bounded k ≥ 2. Whether a single prover suffices, that is, QMA(2) = QMA, remains open. In the centralized setting, the main question is whether prover reduction preserves polynomialtime verification, allowing polynomial overheads in proof size and computation. In distributed verification, finer resource bounds matter: reducing the number of provers may increase global and local proof sizes or require additional communication. We therefore ask: What is the cost of reducing the number of provers in distributed quantum verification?

1.1

Our model

We consider dQMAS(k) protocols, where k unentangled provers each supply a proof that is separable, i.e., unentangled across nodes. Our interest in this model is motivated by the practical challenges of distributing entanglement across a network [WEH18, AEE+ 23]. Figure 1 illustrates this setting for k = 2 provers. For a single prover, this coincides with the dQMAsep,sep model of [HKN24], which we denote by dQMAS. We use the notation dQMAS(k)[c, s; p, r], where c and s are the completeness and soundness parameters, respectively. The parameter p bounds the maximum local proof size, counting all proof qubits supplied to any one node by all provers combined, while r bounds the number of synchronous communication rounds used throughout the protocol verification.

1.2

Our results

In the dQMAS(k) model, we quantify the proof and communication costs to reduce the number of provers in a given network of N nodes. Our construction immediately yields a distributed analogue of the two-prover reduction of Harrow and Montanaro [HM13]. By doubling the local proof size, we reduce k provers to two without any communication overhead. 2

Result 1 (Theorem 3.1, Two-prover reduction). For every integer k ≥ 2 and completeness– soundness parameters c, s satisfying c > (6 + s)/7, 6+s ; 2p, r . dQMAS(k)[c, s; p, r] ⊆ dQMAS(2) c, 7 



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. Result 2 (Theorem 3.3, One-prover reduction). For every integer k ≥ 1 and completeness– soundness parameters c, s satisfying c > (6 + s)/7, 

dQMAS(k)[c, s; p, r] ⊆ dQMAS c,

6+s ; 3p + O(log N ), r + 4 . 7 

The reduction preserves completeness but weakens soundness. For protocols with perfect completeness, we achieve arbitrarily small soundness error with the same four-round overhead. Result 3 (Theorem 4.2, Amplification for dQMAS). For every integer ℓ ≥ 1 and constant s < 1, h

i

dQMAS[1, s; p, r] ⊆ dQMAS 1, 2−ℓ ; O(ℓp + log N ), r + 4 . Beyond perfect completeness, we extend amplification to protocols on networks of bounded size, provided the initial completeness and soundness errors are sufficiently small. Together, Result 3 and the extension above show that one prover suffices in both regimes. The local proof size is at most a constant multiple of the original local proof size plus a logarithmic term in the number of nodes, and the simulation uses four additional rounds. In particular, for every integer k ≥ 2 and constant s < 1, dQMAS[1, s] = dQMAS(k)[1, s].

1.3

Overview of our techniques

We summarize the main technical arguments behind our results. Product testing without communication. We first reduce dQMAS(k) to dQMAS(2) by asking each of the two provers to send all k original proofs. This may compromise the original protocol’s soundness guarantee: while the two submitted blocks are unentangled, each prover may entangle the k registers sent to a node. Harrow and Montanaro [HM13] address this obstacle in the centralized setting via the product test. The two provers supply blocks A = A1 · · · Ak and B = B1 · · · Bk , which are unentangled with each other. Here, Aj and Bj correspond to the original proof from prover j. The product test applies a SWAP test to each pair (Aj , Bj ) and accepts if all k tests accept. Because A and B are unentangled, these tests can detect entanglement among the registers within either block, for example, between Ai and Aj . Their verifier chooses with equal probability between this product test and the original verification on one of the two blocks. In our dQMAS(2) setting, making the same random choice at every node would require coordination or shared randomness across the network. We avoid this by performing both stages sequentially, as illustrated in Figure 2. The product test itself requires no communication. Each node v receives one pair of registers for each original prover: (A1,v , B1,v ),

(A2,v , B2,v ),

...,

(Ak,v , Bk,v ).

The separation between blocks A and B ensures that Aj,v and Bj,v are unentangled for every j. Registers within the same block, such as Ai,v and Aj,v , may nevertheless be entangled. To test 3

Prover A

Prover B

Aj,u

SWAP test for each j

Node u

Bj,u

Aj,v

SWAP test for each j

Node v

Bj,v

Bj,u unused

Original distributed verification on A Runs regardless of the test outcomes

Bj,v unused

Figure 2: Reduction of a dQMAS(k) protocol to dQMAS(2) without additional communication. for such entanglement, each node v applies a SWAP test to every pair (Aj,v , Bj,v ). Together, these local tests implement the product test across the partition indexed by both the original provers and the nodes. If any SWAP test rejects, node v fixes its final output to reject but continues to participate in the protocol. The nodes then run the original verification on block A. Each node accepts only if all its local SWAP tests accept and it accepts in the original verification. Since acceptance in dQMAS(2) requires every node to accept, a failed SWAP test at any node causes global rejection. The nodes therefore enforce the product test’s acceptance condition without exchanging their test outcomes. This yields a two-prover reduction without additional communication. Protocol 1 gives the full construction and Theorem 3.1 its proof of correctness. Two unentangled blocks from one prover. Our earlier construction relies on two unentangled blocks A and B. This guarantee is built into dQMAS(2), but a single prover may entangle them. We recover it by exploiting the separability of dQMAS proofs across nodes: each node receives its second block from a supplier node that lies at distance at most two. The idea is to partition the nodes into two colors: the prover sends block A to amber nodes and block B to blue nodes. Each node v, say amber, receives its A-portion Av directly from the prover, as well as the ID of its blue supplier u. Supplier u receives from the prover both its own B-portion Bu and v’s portion Bv , which it sends to v at the start of the protocol. By nodeseparability of dQMAS, this equips v with a separable pair (Av , Bv ) and, more strongly, ensures that the full blocks A and B are separable. Moreover, each node v uses its color to distinguish Single-prover

Node u Amber

Au Av

Global A

kept at u

Au

Av : u → v

Global B

Bu

Unentangled Node v Blue

Bu Bv

Av

Bu : v → u

Bv

kept at v

Figure 3: Nodes u and v prepare two unentangled blocks A, B from one prover in dQMAS. Time flows from left (before the exchange) to the right (after the exchange). 4

v a

u

y b

x z

Figure 4: Supply chain on a general network. Recipients and suppliers have distinct colors. Av from Bv , allowing the nodes to run the original dQMAS(k) protocol on A. Figure 3 illustrates an example where u and v reciprocally supply one another. The next step is to ensure that such a supply chain can be established on any network. We do so in Lemma 3.2 by grouping the nodes into pairs and triples. The pairs {u, v} consist of nodes at distance at most two that supply one another, using an intermediate relay node when necessary. In a triple x − y − z, node y supplies both neighbors x, z and is supplied by one of them. Figure 4 illustrates this construction. The prover can safely provide both the coloring and the supply chain: the nodes check that each supplier and its recipients have opposite colors and verify the local consistency of the supply chain. If any check fails at a node, the node rejects. The full construction and its proof of correctness are given in Theorem 3.3. Amplification. An obstacle to quantum error reduction is that verification may destroy the witness, compromising further repetitions of the protocol. Strong error reduction permits witness reuse in centralized single-prover protocols [MW05]. With multiple provers, however, amplification must also account for separability between their proofs. Here, weak error reduction uses ℓ witness copies from each prover, increasing proof size [HM13]. Our construction in Theorem 4.2 implements weak error reduction for dQMAS, whose soundness guarantee still relies on separability across nodes. In particular, suppose the single-prover A sends nodes u and v the following ℓ registers each: A[1] u ,

A[2] u ,

...,

A[ℓ] u ;

A[1] v , [i]

A[2] v ,

...,

[i]

Av[ℓ] .

Nodes u, v repeat the verification on each copy (Au , Av ), and accept if all repetitions accept. [1] [1] By node-separability of dQMAS, the first pair (Au , Av ) is unentangled: u and v can safely run the original verification on this pair, with the original soundness guarantee. However, a [1] [2] [1] [2] malicious prover may entangle Au with Au , and Av with Av . Conditioned on acceptance, [2] [2] the first repetition may then transfer this entanglement to the second pair (Au , Av ), breaking the separability promise for the second repetition. Harrow and Montanaro [HM13] prevent this entanglement transfer by using an accepting effect that is separable across the relevant partition—Au : Av in the example above.1 Our sequential implementation of testing and verification need not have this property. Nevertheless, in Lemma 4.1 we show that its accepting effect admits a separable upper bound with the same soundness guarantee. This suffices to reduce soundness exponentially, even when a dishonest prover entangles registers from different repetitions. Amplification in dQMAS comes with a second hurdle: taking a majority vote over the global outcomes of the repetitions can require substantial additional communication. Our construction so far has each node accept if and only if all its repetitions accept. This preserves perfect 1

Here, separability refers to a measurement effect, rather than a witness state.

5

completeness; for c < 1, however, the completeness guarantee drops to cℓ , which decreases exponentially with the number of repetitions. Our construction in Theorem 4.3 chooses a suitable threshold for the fraction of accepting repetitions at each node, allowing completeness and soundness errors to decrease when both initial errors are sufficiently small.

1.4

Other related works

Distributed quantum algorithms have been studied in terms of both round and message complexity. In the quantum CONGEST model, algorithms are known for computing or approximating diameter, radius, and girth [LGM18, vAdV22, WY22], and for detecting triangles, cliques, and even cycles [ILGM20, CHFL+ 22, FLMT24]. In the quantum routing model [DMP25], Dufoulon, Magniez, and Pandurangan obtained nearly tight message complexity bounds for leader election, broadcast, and minimum spanning tree construction [DMP26], while Le Gall et al. showed an exponential quantum advantage in message complexity for routing on welded-tree networks [LGLMR25]. In the quantum LOCAL model [GKM09], Le Gall, Nishimura, and Rosmanis exhibited tasks on N -node networks that are solvable in a constant number of quantum rounds but require Ω(N ) randomized classical rounds [LNR19]. For locally checkable problems, Balliu et al. first established a quantum advantage that grows with the maximum degree [BBCR+ 25] and later obtained an asymptotic advantage on bounded-degree graphs [BCd+ 26]. In a recent breakthrough, Flin, Li, and Suomela gave a constant-round quantum algorithm for 3-coloring cycles with high probability [FLS26]. There is also a substantial body of work on lower bounds on the round complexity of distributed quantum algorithms [EKNP14, AF14, GKZ19, LR22, CRdG+ 24, DKL+ 24, ACRd+ 25, BCC+ 25, BG26, FMZ26, CRFdG+ 26, GL26].

1.5

Organization

The paper is organized as follows. In Section 2, we fix notation and introduce the background needed for our results. In Section 3, we present the constructions underlying Results 1 and 2 and prove their correctness. In Section 4, we amplify these protocols to obtain Result 3 and establish the resulting prover collapse for dQMAS(k). Finally, in Section 5, we show how larger local proofs allow a reduction to a single prover without any communication overhead.

1.6

Discussion

Our results show that a single prover suffices for distributed quantum Merlin–Arthur protocols with node-separable proofs and perfect completeness. In the centralized setting, by contrast, recent quantum [BGH+ 26] and classical [GMT26] oracle separations between QMA and QMA(2) provide evidence that two unentangled provers are more powerful than one. We discuss two directions for further research. Node-entangled proofs. The dQMA model relaxes the separability condition of dQMAS, allowing each prover’s witness to be entangled across nodes. Does a single prover still suffice, that is, does dQMA(k) = dQMA hold for k ≥ 2? Our distributed product test does not directly extend to this setting because completeness is no longer guaranteed. While the local SWAP tests correctly test for entanglement among the k original proofs, they also penalize entanglement across nodes, which is allowed even in honest dQMA proofs. Strong error reduction. Our amplification construction implements parallel repetition, causing the local proof size to scale linearly with the number of runs of the protocol. In QMA, strong error reduction avoids this growth by alternating applications of the verifier circuit and its 6

inverse [MW05]. In dQMAS, however, reversal after measurement need not restore separability across nodes, complicating the soundness analysis. Such an approach would also increase the round complexity linearly with the number of repetitions. Overcoming this obstacle could advance efforts to prove QMA(2) = NEXP [BFL+ 26].

1.7

AI disclosure

The authors derived Result 1 without AI assistance. They also independently derived initial versions of Result 2 and Result 3 restricted to bipartite networks. During September and October 2026, GPT-6 Astra assisted in repairing the proofs and extending Result 2 and Result 3 to general networks. These interactions yielded the technical arguments for amplification with imperfect completeness and those presented in Section 5. The same model also helped the authors draft and revise the manuscript. The authors reviewed all technical arguments in full and take full responsibility for the mathematical claims and final text.

1.8

Acknowledgments

This work was supported in part by JSPS KAKENHI (Grant Nos. JP24H00071, JP24K22293, JP25K24465, JP25K24674, and JP26H02504), MEXT Q-LEAP (Grant No. JPMXS0120319794), JST ASPIRE (Grant No. JPMJAP2302), JST CREST (Grant No. JPMJCR24I4), and JST SPRING (Grant No. JPMJSP2125).

2

Preliminaries

We assume familiarity with the basics of quantum computation [NC10]. Throughout, we write [k] = {1, . . . , k}, take logarithms to base two, and work with finite-dimensional Hilbert spaces.

2.1

Quantum notation

An n-qubit register has Hilbert space (C2 )⊗n . A quantum state is a positive semidefinite operator of trace one. A pure state is represented by a unit vector |ψ⟩, identified with |ψ⟩⟨ψ|. We use ∥ · ∥ for the Euclidean norm of vectors. For a state ρAB , its reduced state on A is ρA = trB ρAB . The relation X ≤ Y means that Y − X is positive semidefinite. An effect is an operator 0 ≤ E ≤ I; a measurement with accepting effect E accepts ρ with probability tr(Eρ). A state on H1 ⊗ · · · ⊗ Hq is separable across this partition if it can be written as ρ=

X

λa ≥ 0,

λa ρa,1 ⊗ · · · ⊗ ρa,q ,

a

X

λa = 1,

a

where each ρa,i is a state on Hi . For two registers A, B, we denote this set by Sep(A : B). A separable pure state is a product state. By convexity, the maximum acceptance probability over separable states is attained on a pure product state. Operations local to the factors, including conditioning on local measurement outcomes, preserve separability. Definition 2.1 (Separable effects). An effect Ω on HA ⊗ HB is separable across A : B if Ω=

X

Ca ≥ 0,

Ca ⊗ D a ,

Da ≥ 0,

(1)

a

where Ca and Da act on A and B, respectively. We use two bounds relating states and acceptance probabilities. For unit vectors |ϕ⟩ , |ψ⟩ and any effect E, q q q ⟨ϕ|E|ϕ⟩ ≤ ⟨ψ|E|ψ⟩ + 1 − | ⟨ϕ|ψ⟩ |2 . (2) 7

This follows by decomposing √ |ϕ⟩ into its components parallel and orthogonal to |ψ⟩, and applying the triangle inequality to E |ϕ⟩. For mixed states, the trace distance 21 ∥ρ − σ∥1 , where ∥X∥1 = √ tr X † X, satisfies tr(Eρ) − tr(Eσ) ≤ 21 ∥ρ − σ∥1 . Quantum channels are completely positive trace-preserving maps; they contract trace distance.

2.2

Distributed quantum verification

Let G = (V, E) be a finite simple undirected network with N = |V | and no isolated nodes. Each node v receives a local input xv , has a unique O(log N )-bit identifier, and knows its neighbors’ identifiers and the corresponding communication ports. We write N (v) for the neighbors of v P and distG (u, v) for graph distance. The distributed input x = (xv )v∈V has length n = v |xv |. The nodes collectively verify a property of the network and its inputs with the help of k computationally unbounded provers, each knowing the network and all local inputs. Before verification, prover j sends each node v a quantum proof register with Hilbert space Hj,v , whose N N size is prescribed by the protocol. The full witness space is H = kj=1 v∈V Hj,v . We extend the node-separable model of [HKN24] to k unentangled provers: proofs from distinct provers are unentangled, and each prover’s proof is separable across nodes. By convexity, it suffices to consider pure witnesses of the form |ψ⟩ =

k O O

|ψj,v ⟩ ,

|ψj,v ⟩ ∈ Hj,v .

(3)

j=1 v∈V

Thus, the registers supplied by different provers to the same node are also initially unentangled. After receiving the proofs, the nodes execute synchronous communication rounds. In each round, they perform local quantum operations and exchange quantum messages with their neighbors. Local computation and workspace are unrestricted, and exact operations are allowed. Auxiliary registers are initialized locally, with no prior shared randomness or entanglement. Each node outputs accept or reject; the protocol accepts if and only if all nodes accept. A distributed language L is a set of instances (G, x), where x is a distributed input on G. Definition 2.2 (Separable distributed quantum verification). For an integer k ≥ 1 and c, s ∈ [0, 1], a language L belongs to dQMAS(k)[c, s; p, r] if it admits a protocol of the above form using at most p proof qubits at each node, summed over all provers, and at most r synchronous communication rounds, such that: • Completeness. For every (G, x) ∈ L, some admissible witness makes all nodes accept with probability at least c. • Soundness. For every (G, x) ∈ / L, every admissible witness makes all nodes accept with probability at most s. Thus, p bounds the maximum local proof size. It includes classical proof bits and excludes local workspace. The parameters may depend on n and N . We write dQMAS = dQMAS(1) for the single-prover model and call c = 1 perfect completeness.

2.3

The product test

For equal-dimensional registers A, B, the operator SWAP exchanges their contents. The SWAP test is the projective measurement with accepting projector (I + SWAP)/2. The product test of Harrow and Montanaro [HM13] acts on two blocks A = A1 · · · Aq and N B = B1 · · · Bq , each with space H = qi=1 Hi . It applies a SWAP test to each pair Ai , Bi and

8

accepts if all tests accept. With SWAPi exchanging Ai and Bi , its accepting projector is Π=

q O I + SWAPi

2

i=1

(4)

.

For unit vectors |α⟩ , |β⟩ ∈ H, write PT(α, β) = ⟨α ⊗ β|Π|α ⊗ β⟩ for its acceptance probability. Identical product states pass unchanged. Π is separable across A : B [HM13, proof of Lemma 6]. For |ψ⟩ ∈ H1 ⊗ · · · ⊗ Hq , we write ωψ for its maximum squared overlap with a product vector, ωψ =

max

2

|ϕi ⟩∈Hi , ∥ϕi ∥=1 i=1,...,q

⟨ψ | ϕ1 ⊗ · · · ⊗ ϕq ⟩ .

Lemma 2.1 (Product-test overlap bound). For unit vectors |α⟩ , |β⟩ ∈ H, let ωα and ωβ be their respective maximum squared overlaps with unit product vectors in H1 ⊗ · · · ⊗ Hq . Then (1 − ωα ) + (1 − ωβ ) ≤ 4 1 − PT(α, β) .

(5)

Proof. The reduced-state identity of [HM13, Lemma 2] and Cauchy–Schwarz give PT(α, β) ≤

q

PT(α, α) PT(β, β) ≤

PT(α, α) + PT(β, β) . 2

By [BGJW26, Corollary 1.2], PT(α, α) ≤ (1 + ωα )/2, and likewise for β; the case q = 1 is immediate. Substitution gives the claim. We also use the following multiplicativity property of separable effects for parallel repetition. Lemma 2.2 ([HM13, Lemma 10]). Let Ω be an effect separable across A : B. For every integer ℓ ≥ 1, let A[i] , B [i] be copies of A, B for i ∈ [ℓ]. Every state ρ separable across A[1] · · · A[ℓ] : B [1] · · · B [ℓ] satisfies !ℓ ⊗ℓ

tr(Ω ρ) ≤

3

max

τ ∈Sep(A:B)

tr(Ωτ )

(6)

.

Prover reduction via distributed product test

We reduce the number of provers from k to two using the distributed product test in Protocol 1. N Let P be a dQMAS(k) protocol with witness space H = j,v Hj,v . Its witnesses are separable across all factors Hj,v , indexed by prover j = 1, . . . , k and node v ∈ V . In Protocol 1, node v receives registers Av = A1,v , . . . , Ak,v and Bv = B1,v , . . . , Bk,v . While separability across Av : Bv is guaranteed, the registers within either block may be entangled. The nodes test the separability promise of P by the local SWAP tests in Step 1, whose joint accepting effect on global registers A = (Av )v∈V and B = (Bv )v∈V is Π=

O I + SWAPj,v

2

j,v

(7)

.

By (4), Step 1 globally implements the product test across the factors Hj,v . Then the nodes run the original verification on register A. The separability requirement across A : B in Protocol 1 conforms to the two-prover promise of dQMAS(2), and thus yields the following reduction from k to two provers. Theorem 3.1. On any network of N nodes, for any k ≥ 2 and 0 ≤ (6 + s)/7 < c ≤ 1, 

dQMAS(k)[c, s; p, r] ⊆ dQMAS(2) c, 9

6+s ; 2p, r . 7 

Protocol 1. Sequential product-test simulation Goal: Simulate a dQMAS(k) protocol P with witness space H = j,v Hj,v . Witness: Separable registers A : B, each over H. Node v receives Aj,v , Bj,v for 1 ≤ j ≤ k. N

1. Each node v SWAP tests Aj,v against Bj,v for every j. 2. Execute P on A, regardless of the SWAP test outcomes. 3. Each node accepts if all its SWAP tests and its verification accept.

Proof. Fix a dQMAS(k) protocol P. We show correctness of Protocol 1. By convexity, we may restrict attention to pure witnesses. Two honest provers supply identical copies of an honest product witness, preparing identical pure states in Aj,v and Bj,v for every j, v. All SWAP tests accept with certainty and leave the copies unchanged, so running P on A accepts with probability at least c. For soundness, let |Ψ⟩ = |α⟩A ⊗ |β⟩B be an arbitrary witness. Let |ϕα ⟩ be the closest product state to |α⟩, with ωα = |⟨ϕα |α⟩|2 their squared overlap. Define |ϕβ ⟩ and ωβ analogously. By (7), Protocol 1 requires the product test to pass on A, B, followed by acceptance of P on A. Our proof balances rejection in the two stages: high success probability in the product test leaves both registers A and B close to a product state, allowing us to use the soundness of P. First observe that exchanging A and B leaves the unnormalized post-test state unchanged: Π(|α⟩A ⊗ |β⟩B ) = Π(|β⟩A ⊗ |α⟩B ).

(8)

The overall acceptance probability is therefore unchanged, so we may assume ωα ≥ ωβ . Let E be the accepting effect of P, and R its rejecting effect when run on A. Denote by rPT the probability that the product test rejects, and by rver the probability that it passes but the subsequent verification rejects. Explicitly, √ R = (I − E)A ⊗ IB , rPT = ∥(I − Π) |Ψ⟩ ∥2 , rver = ∥ R Π |Ψ⟩ ∥2 . (9) These two events partition overall rejection, whose probability is therefore δ = rPT + rver . Using ωα ≥ ωβ and (5) from Lemma 2.1 we obtain 1 − ωα ≤

(1 − ωα ) + (1 − ωβ ) ≤ 2rPT . 2

(10)

Since |ϕα ⟩ is a product witness, soundness of P implies that it is rejected with probability at least 1 − s. Applying (2) to I − E, we obtain √

1−s≤

q

⟨α|(I − E)|α⟩ +

√

√ √ 1 − ωα = ∥ R |Ψ⟩ ∥ + 1 − ωα .

Decomposing |Ψ⟩ = Π |Ψ⟩ + (I − Π) |Ψ⟩ gives √ √ √ 1 − s ≤ ∥ R |Ψ⟩ ∥ + 1 − ωα √ √ √ ≤ ∥ R Π |Ψ⟩ ∥ + ∥ R (I − Π) |Ψ⟩ ∥ + 1 − ωα √ √ √ ≤ rver + rPT + 1 − ωα √ √ √ ≤ rver + (1 + 2) rPT q √ √ ≤ (4 + 2 2)(rPT + rver ) ≤ 7δ

(by (11))

(12)

(triangle inequality)

(13)

(Def. of rver and R ≤ I)

(14)

(by (10))

(15)

(Cauchy–Schwarz).

(16)

Thus δ ≥ (1 − s)/7, so the overall acceptance probability is 1 − δ ≤ (6 + s)/7. 10

(11)

The correctness of Protocol 1 rests on the separability promise across A : B. This guarantee is lost upon moving to the single prover setting dQMAS. To restore it, we exploit separability across nodes. For each node v, the prover supplies one block directly to v and a second to its supplier s(v), which forwards it to v at the start of the protocol. We organize these transfers using the following routing structure. Definition 3.1. A two-step routing cut is a pair (χ, s), where χ : V → {Amber, Blue} is a coloring and s : V → V a supplier map satisfying the following conditions for every v ∈ V : 1. Its supplier is within distance two: distG (v, s(v)) ≤ 2; 2. It has a different color from its supplier: χ(s(v)) ̸= χ(v); 3. It supplies at most two nodes: |{u ∈ V : s(u) = v}| ≤ 2. Condition (1) bounds the rounds needed to deliver each block. Condition (2) and nodeseparability guarantee the desired separable cut A : B: these blocks consist of registers initially sent to amber and blue nodes, respectively. Finally, condition (3) bounds each node’s proof size. The following lemma guarantees that our routing strategy can take place over any network. Lemma 3.2. Every graph without isolated vertices admits a two-step routing cut. Proof. Choose a rooted spanning tree in each connected component. Process the tree from leaves to root, with the invariant that every processed subtree is partitioned into pairs except possibly for its root. At a vertex v, pair the unpaired child roots with one another. If one remains, pair it with v; otherwise leave v unpaired. Every pair is at tree distance at most two. After processing the tree, only its root z can remain unpaired. If this happens, choose a child u of z. By construction, u is paired either with one of its own children or with another child of z. Adding z to that pair gives a triple forming a path of length two. Thus, each component is partitioned into pairs and at most one such triple. For each pair {u, v}, give its vertices opposite colors and set s(u) = v and s(v) = u. For each triple x − y − z, give y the opposite color from x, z and set s(x) = s(z) = y and s(y) = x. Every node has a supplier of opposite color at distance at most two, and every supplier serves at most two recipients. Hence (χ, s) is a two-step routing cut. Our one-prover reduction uses Protocol 2 and achieves the following bounds. Theorem 3.3. On any network of N nodes, for every integer k ≥ 1 and every c > (6 + s)/7, 6+s dQMAS(k)[c, s; p, r] ⊆ dQMAS c, ; 3p + O(log N ), r + 4 . 7 



(17)

Proof. Fix a dQMAS(k) protocol P. We show correctness of the simulation in Protocol 2 and quantify its resource bounds. The one-prover reduction in Protocol 2 uses a two-step routing cut (χ, s) supplied by the prover. Each node v receives its color χ(v), the IDs of its supplier s(v) and relay r(v), its own witness register Ov , and a register Ru for each node u it supplies. For routes of length two, the relay is an intermediate node between v and its supplier; for direct routes, r(v) = s(v). All nodes measure their color and routing IDs in the computational basis at the start of the protocol. During the first four rounds, the nodes check the routing cut (χ, s) and deliver the proof registers accordingly. If any check fails at node v, it fixes its final output to reject but continues to participate in the protocol. Conditioned on all checks passing, each node v now holds two unentangled registers Ov and Rv , which it relabels as follows: (

(Av , Bv ) =

(Ov , Rv ), if χ(v) = Amber, (Rv , Ov ), if χ(v) = Blue. 11

(18)

Protocol 2. Two-step routing simulation Goal: Simulate a dQMAS(k) protocol P. Witness at node v. Routing labels χ(v), s(v), r(v) and registers Ov and Ru for all s(u) = v. Initialization. Node v measures χ(v), s(v) and r(v). 1. Round 1. Each node v checks that r(v) ∈ N (v) and s(v) ̸= v. If both checks pass, it
sends a request v, χ(v), s(v) to relay r(v). 2. Round 2. If r(v) ̸= s(v), r(v) checks that s(v) is a neighbor and forwards the request. Supplier s(v) checks if v has the opposite color and if it received at most two requests. On failure, s(v) fixes rejection. 3. Round 3. Supplier s(v) returns (Rv , v) to the node from which the request arrived, serving at most two requests.a 4. Round 4. For indirect routes, relays forward Rv to v. A missing Rv causes rejection at v and is replaced by a locally prepared register of the prescribed size. 5. Verification. Nodes assign registers according to (18) and run Protocol 1 to simulate P. Each node accepts if all its preliminary checks and this execution accept. a

We assume s(v) can identify Rv among its proof qubits. The assumption can be removed by ordering its outgoing registers and including the size of Rv in the request, without affecting the resource bounds.

Write A = (Av )v∈V and B = (Bv )v∈V . Every register Av was initially supplied to an amber node, whereas every register Bv was initially supplied to a blue node. By the node-separability promise of dQMAS, the resulting blocks A and B are separable across A : B. Thus, Step 5 satisfies the separability requirement of Protocol 1, and the soundness argument of Theorem 3.1 bounds its acceptance probability by (6+s)/7 on no-instances, conditioned on all routing checks passing. If any routing check fails at a node, that node, and hence the protocol, rejects with certainty. The same soundness bound therefore holds unconditionally. For completeness, the prover sends a valid two-step routing cut (χ, s), whose existence is guaranteed by Lemma 3.2, with valid relay IDs. All routing checks succeed with certainty. The prover also sends two identical copies of an honest witness in blocks A and B so that, after routing, each node v holds the intended registers Av = A1,v , . . . , Ak,v and Bv = B1,v , . . . , Bk,v , with Aj,v and Bj,v in identical pure states. The completeness argument of Theorem 3.1 therefore applies, giving acceptance probability at least c. It remains to bound the resources required by Protocol 2. The two-step routing strategy adds four rounds to the r required by Protocol 1. Each register Ov or Ru takes p qubits, the proof size of P. Since v supplies at most two nodes, these registers use at most 3p qubits in total. Since each node ID uses O(log N ) bits, the routing labels require O(log N ) qubits in total.

4

Amplification and prover collapse

In this section, we amplify Protocol 1 to compensate for the weakened soundness guarantee of our reductions. We first consider perfect completeness and then almost-perfect completeness. Under the respective error assumptions, we obtain the prover collapse to one. Construction. Our amplification construction in Protocol 3 implements parallel repetition on top of the routing strategy of Protocol 2. To each node v, the prover now sends ℓ copies of 12

Protocol 3. Parallel repetition Goal. Amplify a dQMAS(k) protocol P with one prover through ℓ ≥ 1 parallel repetitions. [1] [ℓ] Witness at node v. Routing labels χ(v), s(v), r(v) and proof registers Ov = Ov , . . . , Ov [1] [ℓ] and Ru = Ru , . . . , Ru for all s(u) = v. Initialization. Node v measures (χ(v), s(v), r(v)) in the computational basis. 1. Routing. Execute Rounds 1–4 of Protocol 2 to route Rv . [i]

[i]

[i]

[i]

2. Verification. For each i = 1, . . . , ℓ, node v assigns Ov , Rv to Av , Bv according to (18). The nodes run Protocol 1 in parallel on all ℓ repetitions. Each node accepts if and only if all its routing checks pass and it accepts in every repetition.

v’s own proof Ov and of each proof Ru that v supplies. We denote these blocks as Ov = Ov[1] , . . . , Ov[ℓ] ,

Ru = Ru[1] , . . . , Ru[ℓ] ,

for s(u) = v.

Conditioned on all routing checks passing at Step 1, the routing in Protocol 2 and the relabeling in (18) yield global blocks A = (Av )v∈V and B = (Bv )v∈V that are separable across A : B. Grouping their registers by copy, we can write this partition as A[1] · · · A[ℓ] : B [1] · · · B [ℓ] , [i]

(19)

[i]

where A[i] = (Av )v∈V and B [i] = (Bv )v∈V . At Step 2, the nodes repeat Protocol 1 on registers A[i] , B [i] for all i = 1, . . . , ℓ. The main obstacle to proving soundness of our construction is entanglement swapping. After routing, all copies are separable across A[i] : B [i] ; this is crucial to preserve the soundness guarantee of Protocol 1. Nonetheless, a malicious prover may entangle registers from different copies, for instance A[i] with A[j] and B [i] with B [j] . Conditioned on acceptance, the i-th repetition may then entangle the j-th copy across A[j] : B [j] , so the original soundness guarantee no longer applies to the j-th repetition. Harrow and Montanaro [HM13] show that this entanglement transfer cannot occur when the accepting effect of each repetition is separable across A[i] : B [i] .2 The accepting effect of Protocol 1 need not have this property. For our analysis, however, it suffices to upper-bound it by a separable effect Ω with the same soundness bound. Lemma 4.1 provides such an effect. Lemma 4.1. Let Λ be the accepting effect of Protocol 1 to simulate a protocol P with soundness s < 1. There exists an effect Ω, separable across A : B, with Λ ≤ Ω and, on every no-instance, max

τ ∈Sep(A:B)

tr(Ωτ ) ≤

6+s , 7

(20)

where Sep(A : B) denotes the set of states separable across A : B. Proof. Let E be the accepting effect of the simulated protocol P. We construct our candidate Ω by modifying the separable verifier of Harrow and Montanaro [HM13]: (a) with probability 4/7, perform the product test on A, B; (b) with probability 2/7, verify a uniformly chosen block; and (c) with probability 1/7, accept unconditionally. Write Π and Q for the accepting effects of branches (a) and (b), respectively. Then Q= 2

EA ⊗ IB + IA ⊗ EB , 2

Ω=

I + 4Π + 2Q . 7

Here, separability refers to a measurement effect rather than a state; see Definition 2.1.

13

Separability of Q across A : B is immediate from Definition 2.1, while separability of Π follows from [HM13, proof of Lemma 6]. As a convex combination of separable effects, Ω is separable. Fix a no-instance and an arbitrary product witness |Ψ⟩ = |α⟩A ⊗ |β⟩B . Let rPT and rQ denote the rejection probabilities conditional on choosing branches (a) and (b), respectively: rPT = ⟨Ψ|(I − Π)|Ψ⟩,

rQ = ⟨Ψ|(I − Q)|Ψ⟩.

Applying (11) from the proof of Theorem 3.1 to both registers A and B gives √

1−s≤

q

⟨α|(I − E)|α⟩ +

√

√

1 − ωα ,

1−s≤

q

⟨β|(I − E)|β⟩ +

q

1 − ωβ ,

where ωχ is the maximum squared overlap of |χ⟩ with a product state. Next, we average these two inequalities and apply Cauchy–Schwarz to each of the two averages, giving √

1−s≤

√

s

rQ +

√ (1 − ωα ) + (1 − ωβ ) √ ≤ rQ + 2rPT . 2

(21)

Here, the first inequality also uses the definition of rQ , while the second follows from (5). Squaring the last bound and using (x + y)2 ≤ 2x2 + 2y 2 gives 1 − s ≤ 4rPT + 2rQ . Since rejection occurs only through branches (a) and (b), the acceptance probability is ⟨Ψ|Ω|Ψ⟩ = 1 −

4rPT + 2rQ 1−s 6+s ≤1− = . 7 7 7

By convexity, the bound holds for any state τ separable across A : B. Finally, we prove Λ ≤ Ω. For an arbitrary state |Ψ⟩, we compare the rejection probabilities: Pr [Protocol 1 fails] = 1 − ⟨Ψ|Λ|Ψ⟩ = rPT + rver ,

1 − ⟨Ψ|Ω|Ψ⟩ =

4rPT + 2rQ . 7

As in (9), rver = ⟨Ψ|Π (I − E)A ⊗ IB Π|Ψ⟩ is the probability that the product test passes but verification rejects. Since |Ψ⟩ = Π |Ψ⟩ + (I − Π) |Ψ⟩, the triangle inequality gives p p p √ √ √ rQ = ∥ I − Q |Ψ⟩ ∥ ≤ ∥ I − QΠ |Ψ⟩ ∥ + ∥ I − Q(I − Π) |Ψ⟩ ∥ ≤ rver + rPT . √ Here, the last inequality uses I − Q ≤ I to get √ rPT and symmetry of the post-product test state, which gives Π(E ⊗ I)Π = ΠQΠ and hence ∥ I − QΠ |Ψ⟩ ∥2 = rver . Squaring the bound, we obtain

4rPT + 2rQ 7 √ 6rPT + 2rver + 4 rPT rver ≤ 7 ≤ rPT + rver = 1 − ⟨Ψ|Λ|Ψ⟩

1 − ⟨Ψ|Ω|Ψ⟩ =

√ (by 4 ab ≤ a + 4b).

This comparison holds for every state |Ψ⟩, so Λ ≤ Ω. Amplification for perfect completeness has each node accept if and only if all its ℓ repetitions accept. The separable upper bound of Lemma 4.1 ensures that soundness decreases exponentially in ℓ, despite possible entanglement between repetitions. Theorem 4.2 combines amplification with the reduction from k provers to one; setting k = 1 gives amplification for dQMAS. Theorem 4.2 (Amplification for perfect completeness). On any network of N nodes, for all integers k, ℓ ≥ 1 and s < 1, 6+s dQMAS(k)[1, s; p, r] ⊆ dQMAS(1) 1, 7 "

14



ℓ

#

; 3ℓp + O(log N ), r + 4 .

(22)

Proof. For an arbitrary dQMAS(k) protocol P we show correctness of Protocol 3. For completeness, the prover supplies valid routing labels and ℓ copies of the honest witness pair from Protocol 2. The copies are independent, so the same completeness argument applies to every repetition: since c = 1, all routing checks and repetitions accept with certainty. For soundness, assume all routing checks at Step 1 accept. By (19), the routed state ρ is separable across the two blocks A and B, each spanning all ℓ repetitions. Let Λ be the accepting effect of Protocol 1 and Ω its separable upper bound from Lemma 4.1. The probability that all ℓ repetitions of Protocol 1 accept at Step 2 is then 







tr Λ⊗ℓ ρ ≤ tr Ω⊗ℓ ρ

(0 ≤ Λ ≤ Ω) !ℓ

max

≤

τ ∈Sep(A[i] :B [i] )



≤

6+s 7

(by Lemma 2.2)

tr(Ωτ )

ℓ

(23)

(by Lemma 4.1),

which establishes the claimed bound. For the resource bounds, the ℓ repetitions of Protocol 1 run in parallel and thus still take [i] [i] r synchronous rounds. Two-step routing adds four rounds. Each register Ov or Ru takes p qubits. Including the routing labels, the local proof size is at most 3ℓp + O(log N ) qubits. When c < 1, requiring all ℓ repetitions to accept in Protocol 3 gives a completeness guarantee of only cℓ . A global threshold vote among the nodes would fix the problem at the price of a higher round complexity. Instead, we use a local acceptance rule to give amplification whenever completeness and soundness errors are both sufficiently small. Theorem 4.3 (Amplification for small networks). On any network of N nodes where each node knows N , for every 0 < ε < 1/2 there exists an integer ℓ = O(N log(1/ε)) such that, for every integer k ≥ 1 and c, s satisfying c − s ≥ 1 − 1/(14N ), dQMAS(k)[c, s; p, r] ⊆ dQMAS(1)[1 − ε, ε; 3ℓp + O(log N ), r + 4] . In particular, when the network size N is polynomially bounded in n, polynomially many repetitions ℓ suffice to achieve ε = 2− poly(n) . We use the Bernoulli case of Hoeffding’s lemma in the following form. For every q ∈ [0, 1] and t > 0, t2 1 − q + qe ≤ exp qt + 8 t

!

(24)

.

Proof. We modify the construction from Protocol 3 at Step 2 so that each node accepts if and only if all its routing checks pass and at most d := ⌊ℓ/(8N )⌋ of its ℓ runs of Protocol 1 reject. P Let Xi indicate global acceptance of the i-th repetition with S = ℓi=1 Xi . For completeness, the prover supplies valid routing labels and independent honest copies for the repetitions. All routing checks pass with certainty, and each repetition accepts globally with probability at least c. Since 1 − c ≤ 1/(14N ), the expected number of globally rejecting repetitions can be bounded as E[ℓ − S] ≤ ℓ(1 − c) ≤ ℓ/(14N ). If a node rejects the amplified protocol, the modified acceptance rule implies that it rejects in at least d + 1 > ℓ/(8N ) repetitions. Each of these repetitions also rejects globally, since global acceptance requires every node to accept. A Chernoff bound therefore gives ℓ 3 Pr[global rejection] ≤ Pr ℓ − S > = Pr ℓ − S > 1 + 8N 4 





where the last step uses E[ℓ − S] ≤ ℓ/(14N ). 15





ℓ 9ℓ ≤ exp − 14N 616N 





, (25)

For soundness, we first determine how many accepting repetitions are required for the amplified protocol to accept. If all nodes accept the amplified protocol, each rejects at most d repetitions. Every globally rejecting repetition has a rejecting node, so at most N d repetitions reject globally. Hence, acceptance of the amplified protocol requires S ≥ ℓ − Nd ≥

7ℓ . 8

(26)

It remains to bound Pr[S ≥ 7ℓ/8]. However, since the prover may entangle the copies, the repetitions need not be independent, so a Chernoff bound does not directly apply. As in the correctness proof of Protocol 2, assume all routing checks pass, in which case the routed state is separable across A : B. For any subset J ⊆ [ℓ], the argument of (23) bounds the probability that all repetitions in J accept globally as follows: #

"

E

Y

Xi = Pr[Xi = 1 for all i ∈ J] ≤

i∈J



6+s 7

|J|

.

(27)

Consequently, for every t > 0 and using q = (6 + s)/7 for convenience, " ℓ Y

#

E[e ] = E tS

1 + (e − 1)Xi t

i=1

"

=

X

|J|

(e − 1) E t

(28)

# Y

Xi ≤ (1 − q + qe ) , t ℓ

i∈J

J⊆[ℓ]

where the last inequality uses (27) and the binomial theorem. Even though the repetitions need not be independent, (28) allows us to use a Chernoff argument to bound the global acceptance probability in (26): 7ℓ 8 −7tℓ/8 ≤e E[etS ] 



Pr[global acceptance] ≤ Pr S ≥

(by (26)) (Markov’s inequality)

≤ e−7tℓ/8 (1 − q + qet )ℓ "

≤ exp ℓ

t2 7 −t −q 8 8 

7 = exp −2ℓ −q 8 "



5 ≤ exp −2ℓ 392 "



2 #

2 #

(by (28)) !#

(by (24))

(29)

(taking t = 4(7/8 − q) > 0) (since q ≤ 169/196).

Since N ≥ 2, we have s ≤ 1/(14N ) ≤ 1/28, and hence q = (6 + s)/7 ≤ 169/196. Thus 7/8 − q ≥ 5/392 > 0, which justifies the choice of t and the final inequality. Since rejecting routing checks cause global rejection, the bound holds unconditionally. Choosing ℓ = ⌈CN ln(1/ε)⌉ for a sufficiently large constant C makes both error bounds in (25) and (29) at most ε. Since only the local acceptance rule changes, the resource bounds remain those of Protocol 3. Combining our prover reduction with the preceding amplification results yields the following collapse to a single prover. Corollary 4.4 (Prover collapse). For every integer k ≥ 2 and constant 0 < ε < 1, the following equalities hold, allowing a constant-factor increase and an additive O(log N ) term in local proof size, and four additional rounds: 16

1. For protocols with perfect completeness, dQMAS(k)[1, ε] = dQMAS(1)[1, ε]. 2. On networks of N ≤ 1/(28ε) nodes, where each node knows N , dQMAS(k)[1 − ε, ε] = dQMAS(1)[1 − ε, ε]. Proof. For perfect completeness, apply Theorem 4.2 with a constant ℓ such that ((6 + ε)/7)ℓ ≤ ε. For the second claim, N ≤ 1/(28ε) gives completeness–soundness gap at least 1 − 1/(14N ), so Theorem 4.3 applies with ℓ = O(N log(1/ε)) = O(1). Both simulations use local proof size O(p + log N ) and r + 4 rounds. Ignoring all but one prover gives the reverse inclusions.

5

Prover reduction without additional communication

Our preceding reductions to one prover use witness routing. When the local prover registers are short, we can instead perform the reduction locally, avoiding any communication overhead. Our construction relies on properties of the symmetric subspace SymL (Cd ), which consists of all vectors in (Cd )⊗L that are invariant under every permutation of the L tensor factors. In particular, we use the following form of Chiribella’s quantum de Finetti theorem. Lemma 5.1 ([Chi11, Theorem 2]). Let B1 , . . . , BL be d-dimensional registers. There exists a measure-and-prepare channel M from SymL (Cd ) to B1 such that, for every reference register R and every state ρ supported on HR ⊗ SymL (Cd ), the state σRB1 = (idR ⊗M)(ρ) is separable across R : B1 and satisfies d 1 (30) 2 ∥ρRB1 − σRB1 ∥1 ≤ L + d , where ρRB1 is obtained by discarding B2 , . . . , BL . In our one-prover reduction, for each original prover j, node v expects L copies |ψj,v ⟩⊗L of its proof on registers B1 , . . . , BL ; v retains B1 and discards the other copies. In the yes case, v recovers |ψj,v ⟩ exactly. In contrast, the single dishonest prover may entangle B1 with the other registers by some state ρ. Lemma 5.1 states that, if ρ lies in the symmetric subspace and the number of copies L is large enough, once B2 , . . . , BL are discarded, B1 and the rest of the witness are close to a separable state. Repeating the argument for each encoded block j at every node v shows that the joint state of the N k retained proof registers is close to a witness that is fully separable across nodes and provers. The original dQMAS(k) soundness bound therefore holds up to a small additive error. The actual construction repeats the argument for k − 1 provers: if k − 1 registers are separable, the remaining k-th register must also be. One thing to address is that ρ need not satisfy the symmetric-subspace assumption of Lemma 5.1. To enforce this condition, fix an isometry from SymL (Cd ) into a qubit register, and call its image the valid encoding subspace. To decode, a node measures whether the received register lies in this subspace. On a valid outcome, it applies the inverse isometry; otherwise, it discards the register and prepares a fixed symmetric state. Theorem 5.2. On any network of N nodes, consider a dQMAS(k) protocol with parameters (c, s; p, r), where k ≥ 2. Suppose that, at each node, all but one of the k proof registers contain at most b qubits, and let pA bound the proof size of the remaining register at any node. For every 0 < η < c − s,   dQMAS(k)[c, s; p, r] ⊆ dQMAS c, s + η; p′ , r , (31) where



p′ ≤ pA + O k 2b log 17

Nk . η 

In particular, if b = O(log n) and pA , N , k, and log(1/η) are polynomially bounded in n, then p′ also is. At node v, let Av denote the unencoded register, of size at most pA . Proof. At each node v, the construction replaces each of the k − 1 registers other than Av by a block of L registers, each of dimension d = 2b . By the above argument, the state of each block is supported on SymL (Cd ). Let D denote the dimension of this subspace and q the number of qubits used to encode each block. We set dN k L= , η 



L+d−1 , d−1 !

D=

q = ⌈log D⌉.

To each node v, the prover sends register Av and k − 1 encodings. Each node decodes them into the symmetric subspace, replacing invalid encodings by a fixed symmetric state. From each of the k − 1 decoded blocks, the node keeps one register and discards the other L − 1. Finally, it runs its part of P on the k − 1 retained registers together with Av . For completeness, choose an honest witness |ψ⟩ as in (3). At each node v, the prover sends Av in its honest state and encodings of |ψj,v ⟩⊗L for the other k − 1 original registers. Decoding and keeping one register from each block recover |ψ⟩ exactly, preserving completeness c. For soundness, each decoded block is supported on SymL (Cd ), even for invalid encodings, which the decoder replaces by a fixed symmetric state. Consider one decoded block B1 , . . . , BL , and let R contain all registers outside it. The actual protocol discards B2 , . . . , BL , producing a joint state τRB1 . By Lemma 5.1, there is a measure-and-prepare channel whose output σRB1 is separable across R : B1 and satisfies 1 d ∥τRB1 − σRB1 ∥1 ≤ . 2 L+d Let τall be the witness retained for P and σall the comparison state obtained using the measure-and-prepare channels. Applying the single-block bound to all N (k − 1) replacements and using contractivity of trace distance and the triangle inequality, we obtain 1 d ∥τall − σall ∥1 ≤ N (k − 1) ≤ η. 2 L+d For each of the k − 1 decoded blocks at a node, the state σB1 R is separable across B1 : R. Together with node-separability of dQMAS, the local measure-and-prepare channels ensure that σall is a convex combination of admissible product witnesses. By linearity, P accepts with probability at most s. Acceptance probabilities differ by at most the trace distance, so acceptance on the actual witness τall is at most s + η. Finally, D ≤ [e(L + d)/d]d gives q = O(d log(N k/η)). Hence Nk p ≤ pA + (k − 1)q ≤ pA + O k 2 log . η 

′

b



All preprocessing is local, preserving the round complexity r and proving (31).

18

References [ACRd+ 25]

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d’Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, and Jukka Suomela. Online locality meets distributed quantum computing. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 1295–1306, 2025. doi:10.1145/3717823.3718211.

[AEE+ 23]

Koji Azuma, Sophia E. Economou, David Elkouss, Paul Hilaire, Liang Jiang, Hoi-Kwong Lo, and Ilan Tzitrin. Quantum repeaters: From quantum networks to the quantum internet. Reviews of Modern Physics, 95(4):045006, 2023. doi: 10.1103/RevModPhys.95.045006.

[AF14]

Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? ACM SIGACT News, 45(3):82–104, 2014. doi:10.1145/2670418. 2670440.

[BBCR+ 25] Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. Distributed quantum advantage for local problems. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 451–462. ACM, 2025. doi:10.1145/3717823.3718233. [BCC+ 25]

Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d’Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, and Jukka Suomela. New limits on distributed quantum advantage: Dequantizing linear programs. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs. DISC.2025.11.

[BCd+ 26]

Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. Distributed quantum advantage in locally checkable labeling problems. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 1268–1308. SIAM, 2026. doi:10.1137/1.9781611978971.49.

[BFL+ 26]

Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an Internally Separable Proof. In Rotem Arnon and Aram W. Harrow, editors, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026), volume 389 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:13, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/ LIPIcs.TQC.2026.5.

[BG26]

Sebastian Brandt and Tim Göttlicher. A post-quantum lower bound for the distributed Lovász local lemma. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 3298–3312. SIAM, 2026. doi:10.1137/1.9781611978971.119.

[BGH+ 26]

John Bostanci, Sabee Grewal, Jonas Haferkamp, Andrew Huang, Yeongwoo Hwang, Anand Natarajan, and Chinmay Nirkhe. A quantum oracle separation between QMA(2) and QMA, 2026. arXiv:2609.02865. 19

[BGJW26]

Jacob Beckey, Fernando Granha Jeronimo, and Pei Wu. An optimal analysis of the product test, 2026. arXiv:2607.21477.

[CHFL+ 22]

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum distributed algorithms for detection of cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 35:1–35:25, 2022. doi:10.4230/LIPIcs.ITCS.2022.35.

[Chi11]

Giulio Chiribella. On quantum estimation, quantum cloning and finite quantum de Finetti theorems. In Wim van Dam, Vivien M. Kendon, and Simone Severini, editors, Theory of Quantum Computation, Communication, and Cryptography, volume 6519 of Lecture Notes in Computer Science, pages 9–25. Springer, 2011. arXiv:1010.1875, doi:10.1007/978-3-642-18073-6_2.

[CRdG+ 24]

Xavier Coiteux-Roy, Francesco d’Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 1901–1910, 2024. doi:10.1145/3618260.3649679.

[CRFdG+ 26] Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, and Isadora Veeren. Distributed quantum algorithms cannot color cycles with probability 1, 2026. arXiv:2608.11720. [DKL+ 24]

Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Müftüoğlu, Jan Studený, and Jukka Suomela. Local problems in trees across a wide range of distributed models. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024), pages 27:1–27:17, 2024. doi: 10.4230/LIPIcs.OPODIS.2024.27.

[DMP25]

Fabien Dufoulon, Frédéric Magniez, and Gopal Pandurangan. Quantum communication advantage for leader election and agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 230–240, 2025. doi:10.1145/3732772.3733509.

[DMP26]

Fabien Dufoulon, Frédéric Magniez, and Gopal Pandurangan. Tight communication bounds for distributed algorithms in the quantum routing model, 2026. To appear in SODA 2027. arXiv:2602.15529.

[EKNP14]

Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 166–175, 2014. doi:10.1145/2611462.2611488.

[FLGNP21]

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:20. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.28.

[FLMT24]

Pierre Fraigniaud, Maël Luce, Frédéric Magniez, and Ioan Todinca. Even-cycle detection in the randomized and quantum CONGEST model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 209– 219, 2024. doi:10.1145/3662158.3662767.

20

[FLS26]

Maxime Flin, Longcheng Li, and Jukka Suomela. Quantum advantage for distributed symmetry breaking, 2026. arXiv:2609.26788.

[FMZ26]

Pierre Fraigniaud, Frédéric Magniez, and Isabella Ziccardi. No distributed quantum advantage for 3-coloring rooted trees and 2-coloring even cycles, 2026. arXiv:2607.04852.

[Gha24]

Sevag Gharibian. Guest column: The 7 faces of quantum NP. ACM SIGACT News, 54(4):54–91, 2024. doi:10.1145/3639528.3639535.

[GKM09]

Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? Round-based models for quantum distributed computing. In Distributed Computing: 23rd International Symposium, DISC 2009, volume 5805 of Lecture Notes in Computer Science, pages 243–257, 2009. doi:10.1007/ 978-3-642-04355-0_26.

[GKZ19]

Cyril Gavoille, Ghazal Kachigar, and Gilles Zémor. Localisation-resistant random words with small alphabets. In Combinatorics on Words (WORDS 2019), pages 193–206, 2019. doi:10.1007/978-3-030-28796-2_15.

[GL26]

Tom Gur and Longcheng Li. Impossibility of one-way one-round quantum 4coloring via matrix-space stability, 2026. arXiv:2609.09091.

[GMT26]

Sabee Grewal, Saachi Mutreja, and Kabir Tomer. A classical oracle separation between QMA and QMA(2), 2026. arXiv:2610.06760.

[GS16]

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1–33, 2016. doi:10.4086/toc.2016.v012a019.

[HKN24]

Atsuya Hasegawa, Srijita Kundu, and Harumichi Nishimura. On the power of quantum distributed proofs. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, pages 220–230, 2024. doi:10.1145/3662158. 3662788.

[HM13]

Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin–Arthur games and tensor optimization. Journal of the ACM, 60(1), 2013. doi:10.1145/2432622.2432625.

[ILGM20]

Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs. STACS.2020.23.

[JLW26]

Fernando Granha Jeronimo, Itai Leigh, and Pei Wu. The QMA(2) universe: Complexity, entanglement, and optimization. ACM SIGACT News, 57(1):64–99, 2026. doi:10.1145/3802807.3802814.

[KKP10]

Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010. doi:10.1007/s00446-010-0095-3.

[KMY03]

Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? In Algorithms and Computation (ISAAC 2003), volume 2906 of Lecture Notes in Computer Science, pages 189–198. Springer, 2003. doi:10.1007/ 978-3-540-24587-2_21. 21

[LGLMR25] François Le Gall, Maël Luce, Joseph Marchand, and Mathieu Roget. Exponential quantum advantage for message complexity in distributed algorithms, 2025. arXiv:2510.01657. [LGM18]

François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 337–346. ACM, 2018. doi:10.1145/3212734.3212744.

[LGMN23a] François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.MFCS.2023.63. [LGMN23b] François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed quantum interactive proofs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:21. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2023. doi:10.4230/LIPIcs.STACS.2023.42. [LNR19]

François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:14, 2019. doi: 10.4230/LIPIcs.STACS.2019.49.

[LR22]

François Le Gall and Ansis Rosmanis. Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model, 2022. arXiv:2212.02768.

[MW05]

Chris Marriott and John Watrous. Quantum Arthur–Merlin games. Computational Complexity, 14(2):122–152, 2005. doi:10.1007/s00037-005-0194-x.

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.

[vAdV22]

Joran van Apeldoorn and Tijn de Vos. A framework for distributed quantum queries in the CONGEST model. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 109–119, 2022. doi: 10.1145/3519270.3538413.

[WEH18]

Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead. Science, 362(6412):eaam9288, 2018. doi:10.1126/ science.aam9288.

[WY22]

Xudong Wu and Penghui Yao. Quantum complexity of weighted diameter and radius in CONGEST networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 120–130, 2022. doi:10.1145/3519270. 3538441.

22

Related documents

• Quantum Advantage in Local Certification of Graph Properties#1571722
• AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates#1013761
• Quantum Advantage for Distributed Symmetry Breaking#1062712
• Quantum Advantage for Distributed Symmetry Breaking#1043062
• Interactive proofs for verifying (quantum) learning and testing#1014478