Quantum Advantage in Local Certification of Graph Properties

Quantum Advantage in Local Certification of Graph Properties Benjamin Jauregui1,2 and Masayuki Miyamoto3 1

arXiv:2611.08076v1 [cs.DC] 5 Nov 2026

2

Universidad de Chile, Chile IRIF & Université Paris Cité, France 3 University of Tsukuba, Japan

Abstract Local certification asks how the vertices of a network can verify a global property using certificates from an untrusted prover and communication with their neighbors. Its central complexity measure is the maximum certificate size at any vertex. Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021) introduced quantum local certification through the distributed quantum Merlin–Arthur (dQMA) model and established an exponential quantum advantage in certificate size for distributed equality. In this problem, t vertices each hold an N -bit string, and the network must verify that all these strings are identical. That separation is measured in the length N of these strings, rather than the number of vertices. Hasegawa, Kundu, and Nishimura (PODC 2024) explicitly asked whether quantum advantages also arise for graph properties, which depend solely on the network topology. We answer this question affirmatively, establishing unconditional exponential and polynomial quantum advantages measured with respect to the number n of vertices. • First, for every fixed integer µ ≥ 1, we construct a graph property TreeEQµ . We show that this property admits a one-round dQMA protocol with O(µ log n)-qubit certificates and messages (hence O(log n) for constant µ), whereas every µ-round dMA protocol for this property requires Ω(n/(µ log2 n))-bit certificates. • Second, for graph symmetry, which asks whether the network has a nontrivial automore 5/3 )-qubit certificates. This yields a phism, we give a one-round dQMA protocol with O(n polynomial quantum advantage over both locally checkable proofs (LCP) and one-round dMA protocols, for which an Ω(n2 )-bit certificate lower bound is known. With respect to graph symmetry, we extend the results in two ways. On one hand, we show that the quadratic classical lower bound persists for any fixed number of verification rounds, or even if the graphs have bounded radius. On the other hand, for certifying symmetry in graphs with radius at most D, our quantum cost improves to O(nD log n). These separations rely on two advances in quantum certification of distributed equality. First, for N -bit inputs at the endpoints of an r-edge path, we improve the dQMA certificate bound of Hasegawa et al. (PODC 2024) from O(r2 log N ) to O(r log N ) qubits per vertex. e 2/3 ) certificate qubits Second, we give a new dQMA protocol for equality on paths using O(N at every vertex, independently of the path length. This avoids the linear-size certificates used at relay vertices in the previous construction and enables our quantum advantage for graph symmetry. Finally, we provide an Ω(log N ) certificate lower bound for one-round quantum equality protocols on paths of at least three edges, even with arbitrary entanglement and unrestricted communication.

1

Contents 1 Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Equality problem on paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Exponential advantage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Polynomial advantage for graph symmetry . . . . . . . . . . . . . . . . . . . . 1.3 Organization of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 7 7 11 12 14

2 Preliminaries 14 2.1 Local certification models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 Distributed equality problem 16 3.1 Improved analysis of the equality protocol . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 A new equality protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 Encoding of classical strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Soundness for one label index . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.3 Soundness analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Improved lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4 Exponential quantum advantage 34 4.1 Encoding EQ2N into trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 Quantum advantage for TreeEQµ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 Graph Symmetry 44 5.1 Quantum upper bounds for symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2 A hard family for symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3 Classical lower bounds for symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 A Proof of Claim A

58

B Proof of Claim B

61

2

1

Introduction

A distributed system consists of independent computing devices that communicate through a network. Examples of such networks include data-center networks, peer-to-peer systems, wireless, and sensor networks. These networks are usually seen as a connected graph in which the devices are represented as nodes, and edges represent direct communication links between devices. Then, a task to be solved within this network requires the development of a distributed algorithm through the graph, in which each node performs its own computation and exchanges messages with its neighbors. Here, a fundamental measure of efficiency is the number of communication rounds. The LOCAL model [Lin92] is a standard model focusing on this resource by allowing unrestricted local computation and message sizes, with synchronous communication restricted to network edges. It is also important to verify whether a given property holds in the network. For example, the nodes may want to verify whether the network has a certain topology, such as being a tree or a planar graph, whether a distributed computation has produced a valid output, or whether some other global condition is satisfied. In this setting, the goal is to design a protocol that allows the nodes to collectively decide whether the property holds, despite each node having access only to local information and to the information obtained through communication with other nodes. Such verification protocols are relevant for several reasons. On the one hand, distributed algorithms are often designed under specific assumptions on the network. For example, an algorithm may be more efficient on a particular class of graphs, or may only be correct when the network is a tree, a planar graph, or satisfies some other structural property. Before running such an algorithm, it is therefore important to verify that the network indeed satisfies the assumptions under which the algorithm was designed. On the other hand, verification may be necessary for the correct operation of the distributed system itself. Nodes may need to check that a computation has produced a valid output, that the information stored across the network is consistent, or that the system remains in a valid state. Verification can also support fault tolerance: detecting that a required condition is no longer satisfied may indicate that an error has occurred and that a recovery procedure should be triggered. In all these cases, the fundamental challenge is to verify a global condition using only local communication. Local certification. The verification of such properties is studied within the framework of local certification, where nodes use additional information, supplied as certificates, to check global properties through local communication. In a local certification protocol, a prover assigns a certificate c(v) to each node v of the graph, and the nodes inspect their certificates and exchange messages with their neighbors before deciding whether to accept. The prover here is not trusted: when the property holds, there must be certificates that make all nodes accept; when it does not hold, every certificate assignment must cause at least one node to reject, with a required probability. After receiving certificates, the network is allowed to perform an efficient verification algorithm. For example, in locally checkable proofs [GS16], the network performs a constant-round LOCAL algorithm, and in proof-labeling schemes [KKP10], each node only broadcasts its certificate to its neighbors in a single round. There are many other related models (see the survey [Feu21]). Certificates, therefore, allow the nodes to check a global claim without having to reconstruct the entire network at every node. A central question is how much information these certificates must contain. In particular, the size of the certificates depends on the property being checked. As arguably the simplest case, consider the property of being k-colorable: the vertices can be assigned colors from {0, . . . , k − 1} so that adjacent vertices receive different colors. This property admits a simple certification protocol. The prover assigns a color to each node as its certificate. Each node exchanges its color with its neighbors and accepts if its color belongs to the allowed set and differs from every 3

neighbor’s color. If the graph is k-colorable, the prover can supply a valid coloring that makes all nodes accept. Conversely, if all nodes accept, the supplied colors define a valid k-coloring. Thus, k-colorability can be certified in one communication round using O(log k) bits per node. Indeed, extensive research has established efficient certification protocols, with O(log n) bits per node, for multiple graph properties such as planar, bounded-genus and interval graphs [FFM+ 21, EL22, JMRRR25], connectivity-related properties [BFP24, CLT26], as well as meta-theorems covering broad families of logically definable properties on structurally restricted graphs [BC25, BFP22, CKM25]. In contrast, it is known that some other properties require much more information. e Indeed, Ω(n) bits are required for properties such as unit-disk graphs [DEL+ 24], bounded diameter graphs [CHPP20], graphs with forbidden subgraphs [BCF+ 24, BZ25, Miy25]. A canonical maximally hard example is graph symmetry, the existence of a nontrivial automorphism. In their seminal work, Göös and Suomela established its Θ(n2 ) certificate complexity [GS16], matching the universal O(n2 )bit upper bound obtained by supplying every vertex with a complete description of the network. Quantum local certification. Understanding when quantum computation and communication can reduce the round complexity of distributed algorithms has received growing attention in both the CONGEST and LOCAL models [GM18, GNR19, WY22, vAdV22, FLMT24, FLS26]. For locally checkable problems, recent work has established quantum advantages [BBCR+ 25, BCd+ 26], while also identifying limitations for graph coloring [CRdG+ 24, FMZ27] and the distributed Lovász local lemma [BG26], with further structural insights coming from connections between quantum distributed computing, non-signaling distributions, and online locality [ACRd+ 25]. In this paper, we focus on a complementary line of work, which investigates quantum advantages in the certificate space required for constant-round verification [FLNP21, GMN23, LGMN23, HKN24] with a basic question about how much smaller quantum certificates can be than classical ones. Fraigniaud, Le Gall, Nishimura, and Paz [FLNP21] initiated this direction by introducing a framework of quantum local certification, more precisely, distributed quantum Merlin–Arthur (dQMA) protocols (see Definition 7 for a formal definition). Within this model, they proved a quantum advantage for the verification of “replicated data”, which we will refer to as the distributed equality problem and denote as EQtN : Given two parameters N, t ∈ N, and a collection of N -bit strings x1 , . . . , xt stored at t terminal nodes u1 , . . . , ut , the problem EQtN corresponds to verifying the equality x1 = · · · = xt . In [FLNP21], they proved that EQtN can be certified in the dQMA model with O(tr2 log N ) qubits, where r := mini∈{1,...,t} maxj∈{1,...,t} distG (ui , uj ) is the radius of the terminal set {u1 , . . . , ut }, but requires Ω(N ) bits in the classical dMA model. Subsequent works further developed this framework [GMN23, HKN24]. In all these works, the quantum advantage established is with respect to the size N of the input strings. Therefore, whether quantum advantages extend to graph properties, which depend only on the network topology rather than additional inputs supplied to its vertices, remained a central open question [HKN24]. As we explain next, we answer this question affirmatively.

1.1

Our results

In this paper, we compare classical distributed Merlin–Arthur protocols, abbreviated dMA, with quantum distributed Merlin–Arthur protocols, abbreviated dQMA, as in [FLNP21, HKN24, GMN23]. See Definition 7 for formal definitions of the models.

4

Quantum advantage for graph properties We obtain a quantum advantage for two different graph properties. Throughout this work, we identify each graph property P with the class of graphs satisfying it. Thus, we use “G satisfies P” and “G ∈ P” interchangeably. Exponential advantage. Inspired by the equality problem EQ2N , for every constant µ ≥ 1, we introduce the graph property µ-tree-encoded equality, denoted by TreeEQµ . To define TreeEQµ , we encode the strings to be compared in the original EQ2N problem into the network topology itself. Informally, the construction consists of two tree components joined by a path of size Θ(µ), each encoding a binary string through its branching structure. A graph belongs to TreeEQµ if it has the prescribed structure and the two encoded strings coincide. We defer the precise construction and formal definition to Section 4. We establish the following quantum advantage for TreeEQµ . Theorem 1 (Exponential quantum advantage for TreeEQµ ). Let µ ≥ 1 be a fixed positive integer. There exists a graph property TreeEQµ that admits a one-round dQMA protocol with perfect completeness, soundness error 1/3, and certificates with O(µ log n) qubits. The implicit constant is independent of µ. In contrast, every µ-round dMA protocol for TreeEQµ with completeness c and soundness error s satisfying 2c − 1 > s requires certificates of Ω(n/(µ log2 n)) bits. Theorem 1 establishes an exponential separation between quantum and classical certificate sizes, measured as a function of the number of vertices. For example, by taking µ = 1, this theorem gives a property with distributed quantum complexity equal to O (log n) qubits, while any 1-round dMA protocol requires Ω(n/ log2 n) bits. Polynomial advantage for Graph Symmetry. The separation in Theorem 1 is obtained by encoding instances of EQ2N into a carefully constructed family of trees. Although this demonstrates the power of quantum certification even on trees, the property is specifically defined to express an underlying equality problem. We therefore complement this construction with a quantum advantage for a more natural graph property without input: the well-studied symmetry problem, denoted by SYM, which asks whether the graph admits a nontrivial automorphism, that is, an adjacencypreserving permutation of the vertices other than the identity. It is known [FMO+ 19] that any oneround dMA protocol for this problem requires certificates of Ω(n2 ) bits. We exhibit a polynomial quantum advantage for this problem. Theorem 2 (Quantum advantage for graph symmetry). The graph symmetry problem SYM admits a one-round dQMA protocol with perfect completeness, soundness error 1/3, and certificates with O(n5/3 (log n)7/3 ) qubits per node. It is known that any 1-round dMA protocol for SYM requires Ω(n2 )-bit certificates [FMO+ 19], and therefore Theorem 2 gives a polynomial quantum advantage for this problem. We complement this result with smaller quantum certificates for graphs of bounded radius. For a known integer D ≥ 1, let SYMD denote the class of graphs of radius at most D that admit a nontrivial automorphism. We obtain the following upper bound. Corollary 3. For every known integer D ≥ 1, the property SYMD admits a one-round dQMA protocol with perfect completeness, soundness error 1/3, and O(nD log n) certificate qubits per node. We also show that the quadratic classical lower bound persists for any fixed number of verification rounds, both for SYM and for SYMD when D ≥ µ + 4. More generally, we prove the following bound. 5

Theorem 4. Let µ = µ(n) ≥ 1 satisfy µ = o(n). Every µ-round dMA protocol for SYM with fixed completeness c and soundness error s satisfying 2c − 1 > s has worst-case certificate size Ω(n2 /µ) bits. The same bound holds for SYMD whenever D ≥ 5 and µ ≤ D − 4. For fixed integers µ ≥ 1 and D ≥ µ + 4, Corollary 3 and Theorem 4 therefore establish a quantum advantage for SYMD : O(n log n) quantum certificate qubits in one round versus Ω(n2 ) classical certificate bits in µ rounds. Improved bound for equality problem. A key ingredient in establishing quantum advantages for graph properties is our improved protocol for the distributed equality problem EQtN , previously studied in [FLNP21, HKN24]. We consider the equality problem on a path: two endpoints of a path of r edges receive an N -bit input string. The best known dQMA upper bound is O(r2 log N ) [FLNP21, HKN24]. We improve this upper bound in two ways. Theorem 5 (Improved protocols for equality on a path). For every path P = v0 , . . . , vr of length r ≥ 1, the problem EQ2N of two N -bit strings held at the endpoint nodes v0 and vr admits a one-round dQMA protocol with perfect completeness, soundness error at most 1/3 and certificates of   O min{r log N, N 2/3 (log N )5/3 } qubits per node. Theorem 5 provides two complementary bounds, each obtained by an independent protocol (Protocols 1 and 2). The first bound improves the previous best known upper bound of O(r2 log N ) qubits. The second is the first sublinear-in-N bound that is independent of the path length r at every vertex. The relay-based construction of Hasegawa et al. [HKN24] removes the distance dependence by storing complete Θ(N )-bit descriptions at designated relay vertices; these vertices determine its worst-case certificate size. Our second protocol compresses the certificates at all vertices, including potential relays. The two improvements have different applications. The distance-independent bound gives Theorem 2 for unrestricted symmetry. The O(r log N ) bound improves the radius dependence for SYMD from O(nD2 log n) to O(nD log n), and the central-path contribution for TreeEQµ from O(µ2 log n) to O(µ log n). We finally show that quantum verification cannot make the local information cost of equality arbitrarily small. Theorem 6 (Quantum lower bound). Consider a one-round dQMA protocol for equality of N -bit strings held at the endpoints of a path with at least three edges. Suppose its fixed completeness c and soundness error s satisfy 2c − 1 > s. Then the protocol requires a certificate of Ω(log N ) qubits at some node, even if the certificates are arbitrarily entangled and the messages have unrestricted size. The previously known bounds are Ω((log N )1/4−ε ) and Ω((log N )1/2−ε /r1+ε ) on the total proof and message size over all nodes, obtained by simulating entangled protocols with separable ones [HKN24], together with an Ω(log N ) bound that applies to separable proofs only. One round of quantum verification therefore outperforms µ rounds of classical randomized verification. Table 1 summarizes the bounds.

6

Property

One-round dQMA: qubits per node and message

µ-round dMA: certificate bits per node

TreeEQµ

Ω(n/(µ log2 n)); fixed µ ≥ 1

SYM

O(µ log n) e 5/3 ) O(n

Ω(n2 /µ); µ = o(n)

SYMD

O(nD log n)

Ω(n2 /µ); D ≥ 5, µ ≤ D − 4, µ = o(n)

EQ2N

O(min{r log N, N 2/3 (log N )5/3 })

Ω(N/µ) if r ≥ 2µ + 1 [FLNP21, Theorem 9]

Table 1: Quantum upper bounds have perfect completeness and soundness error 1/3. Classical lower bounds assume fixed completeness c and soundness error s with 2c − 1 > s. Here r is the number of path edges, and N is the input-string length.

1.2

Our technique

Now we provide a high-level description of the techniques and new ideas used to obtain our results. We defer the formal presentation of our models to Section 2 and our protocols to Section 3, Section 4 and Section 5. For the following overview, we only need a few graph-theoretic notions. Given two graphs G and H, an isomorphism from G to H is a bijection φ : V (G) → V (H) such that, for all u, v ∈ V (G), the vertices u, v are adjacent in G if and only if φ(u), φ(v) are adjacent in H. We write G ∼ = H when such an isomorphism exists. For rooted trees T1 , T2 with roots r1 , r2 , a rooted isomorphism is a graph isomorphism φ : V (T1 ) → V (T2 ) satisfying φ(r1 ) = r2 . The isomorphism class of a graph consists of all graphs isomorphic to it; for rooted trees, we define the rooted isomorphism class using rooted isomorphisms. Accordingly, two graphs have the same isomorphism type when they are isomorphic, and two rooted trees have the same rooted isomorphism type when they are isomorphic by an isomorphism mapping root to root. 1.2.1

Equality problem on paths

The complexity from Theorem 5 comes from two different protocols. We first explain the O(r log N ) upper bound which follows from a sharper soundness analysis of the protocol of [HKN24]. The main idea of that protocol is the following: An N -bit string x can be represented by an O(log N )-qubit state |hx ⟩ so that distinct strings |hx ⟩ and |hy ⟩ have overlap bounded away from one [BCWDW01]. Such states, called quantum fingerprints, allow strings to be compared without recovering them. In the existing protocols [FLNP21, HKN24], an honest prover supplies two copies of the same fingerprint along the path. Each vertex selects one of two registers uniformly at random, sends it to the right, then performs SWAP tests, while the endpoints check against their inputs. See Figure 1. v0

v1

|hx ⟩⟨hx |

SWAP

vr

vr−1 ···

SWAP

SWAP test 1/2

or

|hy ⟩⟨hy | 1/2

Figure 1: Graphical example of the execution of the protocol. Each square represents a register. v0 checks if its register contains |hx ⟩. Intermediate vertices perform the SWAP test. The test of vr is uniform randomly chosen. 7

For unequal inputs on an r-edge path, the previous analysis of the protocol guarantees that at least one vertex rejects with probability Ω(1/r2 ) per repetition [HKN24]. Hence, O(r2 ) repetitions are required for constant soundness. We improve this to Ω(1/r), reducing the certificate size from O(r2 log N ) to O(r log N ). Let us focus on cheating strategies of the malicious prover. The natural strategy for the prover is to change fingerprints in equal angles in small increments between two endpoints of the path. Thus, the angle difference between each consecutive certificates is only 1/r, which makes the rejection probability 1/r2 . The previous analysis used union bound to lower bound the probability that some node rejects, which is Ω(1/r2 ). However, since the proofs are not entangled in this case, the rejection events are effectively independent at each node, and the probability that at least one test will fail is 1/r. This suggests that, the prover should correlates the rejection events to decrease the rejection probability. We show that even arbitrary entanglement cannot reduce rejection below Ω(1/r). Let |Ψ⟩ be a purification of the joint state after communication and before measurement, averaged over the random choices of which registers to send. The joint state of the two registers compared by the SWAP test at vertex vj is σj = Tr¬j |Ψ⟩⟨Ψ|. Order this pair as the register received from vj−1 , followed by the register retained at vj . Their individual states are Tr2 σj and Tr1 σj , respectively. For unequal inputs x ̸= y, sufficiently small overall rejection probability forces those endpoint registers to be close to the distinct fingerprints |hx ⟩ and |hy ⟩. Consequently, the sum of the trace distance (D(·)) of two registers on which SWAP tests are performed is Ω(1) ≤

r X

(1)

D(Tr2 σj , Tr1 σj ) .

j=1

Condition on vr choosing its SWAP test. The performed tests are then the fingerprint check at v0 and the SWAP tests at v1 , . . . , vr . To keep track of which vertices reject together, label their joint outcomes by z ∈ {0, 1}r+1 , where zi = 0 means P acceptance at vi and zi = 1 means rejection. This gives an orthogonal decomposition of |Ψ⟩ = z |ψz ⟩. Writing az = ∥ψz ∥, we have X q□ := Pr(at least one vertex rejects) = a2z . z̸=0r+1

The same decomposition gives σj =

X

(2)

Tr¬j |ψz ⟩⟨ψz ′ | .

z,z ′

For each summand Tr¬j |ψz ⟩⟨ψz ′ | , if zi ̸= zi′ for some i ̸= j, the outcome of the
test at vi on |ψz ⟩ and |ψz ′ ⟩ is distinct, hence their reduced states are orthogonal and Tr¬j |ψz ⟩⟨ψz ′ | = 0. For z = z ′ , applying Tr1 or Tr2 to the corresponding summand in (2) gives the same operator. Thus, among the summands in (2), only those indexed by strings z, z ′ that differ at j and agree everywhere else can make Tr2 σj and Tr1 σj different. These pairs are edges of the hypercube on {0, 1}r+1 . Ultimately, together with (1), we obtain Ω(1) ≤

r X

X

D(Tr2 σj , Tr1 σj ) ≤ 2

az az ′

{z,z ′ } an edge

j=1

p ≤ 2 (r + 1)q□ + (r + 1)q□ . Hence q□ = Ω(1/r), and so is the rejection probability. 8

Removing the dependence on distance. Now we explain the second Õ(N 2/3 ) upper bound proved in Theorem 5. Our starting point is to replace the large classical input strings with compact quantum states, which we call label states. In the protocol, the nodes only need to verify whether the represented classical values agree, rather than recover the represented strings from the states, so non-orthogonal states can be used. This idea is the same of the previous quantum protocol, with a standard O(log N )-qubit fingerprints as label states. The label states associated with the input strings are compared in parallel along the path by the SWAP test. However, the SWAP test accepts two copies of every pure state, allowing the prover to change states gradually along a long path. Neighboring states can then be almost identical even when the endpoint states differ, explaining why the certificate size depends on r. We therefore incorporate the family of label states into the local test. The label states now have equal-magnitude amplitudes in a fixed basis, with signs determined by the represented bits: L

1 X |ϕu ⟩ = √ (−1)ua |a⟩, L a=1

u ∈ {0, 1}L .

Here L = Θ̃(N 1/3 ) is a parameter which decides the length of encoded classical strings. The new local test accepts exactly the linear combinations of identical pairs of label states, namely, WL = span{|ϕu ⟩⊗2 : u ∈ {0, 1}L }. Each vertex receives a pair of registers and tests whether that pair lies in WL before communication. Every vertex except the right endpoint then sends its second register to its right neighbor, which performs another WL -test to a new pair. Thus, the two stages test every adjacent pair in the sequence obtained by concatenating the vertices’ pairs along the path. After communication, the endpoints also check the first and last registers of this sequence against the label states specified by their inputs. For soundness, the central task is to lower-bound the rejection probability when two endpoints hold different label states, independently of the path length. We analyze the protocol from the Hamiltonian viewpoint, which is a central methodological contribution of our protocol and analysis. Since the protocol checks every adjacent pair in the full register sequence, it can be viewed as the local Hamiltonian on a chain of qudits. More precisely, we can define a local Hamiltonian X H= Hi i

where Hi is the projector onto the rejection space of a local test applied to the i-th pair of registers. Here, input-dependent checks performed by two endpoinds are not included in H. For this Hamiltonian, we prove two properties. First, the ground space of H is spanned by tensor powers of label states. Second, we use a bound on the spectral gap (the minimum energy of a normalized state orthogonal to the ground space) to obtain an energy lower bound for unequal endpoint labels that is independent of the path length. Each tensor power of a single label state is unchanged when the endpoint registers are exchanged. A state close to the ground space must therefore also change only slightly under this exchange. However, exchanging two different endpoint label states changes the state by a constant amount, because the label states assigned to distinct encoded values are designed to have overlaps bounded away from one. Hence a state satisfying both endpoint requirements for no-instance cannot be close to the ground space: it must have a constant weight outside it. The spectral-gap bound turns this constant weight into an energy lower bound independent of the path length. Consequently, the 9

mismatch between the endpoints cannot be made arbitrarily cheap by spreading it over a longer chain. The protocol applies the WL -test to two kinds of pairs. Before communication, each vertex tests the two registers supplied to it by the prover. After communication, each vertex other than v0 tests the register received from its left neighbor together with its own retained first register. The endpoint checks are also performed after communication. Let p > 0 be the probability that all tests accept, and let ρ be the normalized final state conditioned on this event. All tests after communication act on disjoint registers, so once one of these tests has accepted, it would still accept if repeated after the others. Consequently, ρ satisfies both endpoint checks, and for every Hi corresponding to a test performed after communication, Tr(Hi ρ) = 0. However, for a test performed before communication, Tr(Hi ρ) can be positive even though that test accepted when it was performed. The energy of ρ is Tr(Hρ). We will prove the following inequality where the endpoint conditions give the lower bound, while the detectability lemma [AAV16] gives the upper bound: X 4(1 − p) e −2 ) ≤ Tr(Hρ) = Ω(L Tr(Hi ρ) ≤ . p i

e −2 ), independently of the path length. Hence 1 − p = Ω(L

Finally, we encode each N -bit input using a Reed–Solomon code into K strings of Θ(L) bits each, so that unequal inputs produce at least K/2 of K strings differ. To do so, we choose N = Θ(KL), K = Θ̃(L2 ). The prover uses K label states from each of L-bit strings, and we perform the above protocol, K times in parallel. Since at least K/2 repetitions the two label states at endpoints differ, the corresponding test is rejected with probability Ω̃(L−2 ), and K repetitions make the overall rejection probability Ω(1). Finally, the combined certificate is e 2/3 ), O(K log L) = O(N independently of r. Imroved lower bound. We next explain the lower bound side. The known classical and quantum lower bounds for EQ2N on a path are based on the fooling set method, as used in previous work [FLNP21, HKN24]. In dQMA this is achieved by first combining one half of the honest proof for the input (x, x) and one half of the honest proof for the input (y, y), and then showing the combined new proof passes all tests with high probability on the mismatched input (x, y), which is a contradiction. However, this argument crucially relies on the assumption that proofs have “halves”, which means the argument only applies to separable proofs. We instead use the causality of a single round of communication. Every node at distance at least 2 from vr cannot see the input y, so if the prover supplies the honest proof for the instance (x, x) on the mismatched instance (x, y), the nodes v0 , . . . , vr−2 accept with high probability. Soundness therefore forces vr−1 or vr to reject with high probability. From outside the pair, these two nodes receive only their proof registers and the message from vr−2 , and everything else they use is produced by their own operations. Stopping the protocol just before they act, the reduced state σx on those registers is independent of y, while their subsequent operations depend only on y, which is represented by a single POVM element Ey . Since Ey must accept σy due to completeness and must reject σx due to soundness, the two states must be far apart in trace distance. What remains is a counting problem; how small a dimension can hold 2N quantum states that are pairwise far apart in trace distance? This is already answered in [HKN24]: it can be shown that the dimension must be at least polynomial in N , that is, the corresponding proof contains at least log N qubits. 10

1.2.2

Exponential advantage

Our first separation is given by a graph property that we call TreeEQµ , and whose members are trees. To define TreeEQµ , our idea is to start with an instance of EQ2N on a path, with two input strings z, z ′ ∈ {0, 1}N , one input string at each endpoint, and to replace each input string by a tree attached to the corresponding endpoint, so that the strings are encoded in the structure of the tr (z, z ′ ). We describe our encoding at a high level. resulting graph that we denote TN,µ Encoding. We focus on the equality problem EQ2N , where N is even and each input string has Hamming weight exactly N/2.1 Our first observation is that such a string is uniquely determined by the numbers of zeros before the first one, between consecutive ones, and after the last one. More precisely, for every z ∈ {0, 1}N of Hamming weight N/2, there are unique values r0 , . . . , rN/2 ∈ {0, . . . , N/2} such that z = 0r0 1 0r1 1 · · · 1 0rN/2 . (3) PN/2 These values satisfy i=0 ri = N/2, since z also contains exactly N/2 zeros. We first describe the rooted tree that encodes a single string z satisfying the above conditions with decomposition given by (r0 , . . . , rN/2 ). We start with a root hz and attach the vertices a0 , . . . , aN/2 to it. For each i, we attach ri leaves to ai , where (r0 , . . . , rN/2 ) is the vector of z satisfying (3). The names a0 , . . . , aN/2 are only notation and are not part of the input graph. An important feature of our encoding is the following: A tree encoding a string z cannot be isomorphic to another tree encoding a string z ′ ̸= z, i.e., our encoding must retain the order of the vectors (r0 , . . . , rN/2 ): two rooted encodings should be isomorphic if and only if they represent the same string. To obtain this property, we attach to each node ai a rooted tree Tag(i), defined in Definition 22 (see Figure 2(a) for a graphical example). The tag has a root si with child ti , from which L = Θ(log N ) paths of distinct lengths 1, . . . , L grow; the last vertex of path b carries two extra leaves exactly when the b-th least significant bit of i is 1. We show (Lemma 25) that this rooted structure identifies the index i. The corresponding value ri is then recovered by counting the leaves attached to ai . Together, these observations allow us to recover the encoded strings (Lemma 26). tr (z, z ′ ), we take the rooted trees encoding z and z ′ , call their Finally, to construct the graphs TN,µ roots hL and hR , and join these roots by a central path of ρ = 2µ + 1 edges, using new internal vertices. We denote the two rooted encodings by TL (z) and TR (z ′ ), respectively. See Figure 2(b) for a graphical example. This encoding has the following properties for each z, z ′ ∈ {0, 1}N : tr (z, z ′ ) is a tree (by construction). • The encoded graph TN,µ tr (z, z ′ ) can be verified with a deterministic dMA protocol (Lemma 27). • The shape of the tree TN,µ tr (z, z ′ ) is Θ(N log2 N ) (Fact 1). • The number of nodes of any tree TN,µ

• In each tree, the pair of encoded strings z and z ′ can be recovered uniquely from the isomorphism class (Lemma 26). The fourth property means that the tree structure alone determines the two encoded strings, up to exchanging them, regardless of the names assigned to the vertices. We therefore define TreeEQµ tr (z, z) for some input string z. With this definition, to consist of all graphs isomorphic to TN,µ tr TN,µ (z, z ′ ) ∈ TreeEQµ 1

⇐⇒

z = z′.

The Hamming weight of a binary string is the number of positions containing 1.

11

Thus, checking membership in TreeEQµ on an encoded instance is equivalent to checking equality of its two strings. This equivalence is the basis of our separation. For the quantum upper bound, we combine the classical structural verification with the O(r log N )qubit equality protocol of Theorem 5 in a single communication round, during which the nodes exchange the classical information and the quantum registers in parallel. Since the quantum operations performed before communication do not require knowledge of z and z ′ , the roots hL and hR can reconstruct these strings from the received classical messages and complete the corresponding local endpoint tests after reception, without any additional communication round. Indeed, given an input graph T , the prover supplies O(log n)-bit classical certificates to allow the tr (z, z ′ ) (Lemma 27). If nodes to verify that there exist two strings z, z ′ ∈ {0, 1}N such that T ∼ = TN,µ tr ′ this structural verification passes, then T ∼ = TN,µ (z, z ) for the strings determined by the reported run lengths. Moreover, the root of each tree can reconstruct the string being encoded in the tree. This classical verification requires only O (log n) bits per vertex.2 The roots hL and hR can reconstruct the strings z and z ′ , respectively. Along with the classical certificate of Lemma 27, the prover supplies to the vertices in the central path the quantum certificates of the O(ρ log N )-qubit protocol from Theorem 5 to verify that z = z ′ . Only the endpoint tests depend on these strings, so the roots can reconstruct them during the communication round, before performing these tests. The central path has length ρ = Θ(µ), independent of the number of vertices in the tree. Thus, each vertex in the central path receives O(µ log N ) certificate qubits. Together with the O(log n)-bit classical certificates and the relation log N = Θ(log n), this gives a one-round dQMA protocol using O(µ log n) certificate qubits per vertex. On a yes-instance, honest classical certificates and quantum registers make every check accept with certainty. For soundness, condition on the outcomes of the initial classical measurements. If the structural or routing checks fail, some node rejects. Otherwise, the input is isomorphic to tr (z, z ′ ) for the reconstructed strings. If T ∈ / TreeEQµ , these strings must be distinct, and the TN,µ soundness guarantee of the equality protocol bounds the probability that all nodes accept by 1/3, even for arbitrarily entangled quantum certificates. For the classical lower bound, we adapt the fooling-set argument of Fraigniaud et al. [FLNP21] tr (z, z) to our family of encoded trees. The encoding ensures that combining the left side of TN,µ tr ′ ′ ′ with the right side of TN,µ (z , z ) gives a no-instance whenever z ̸= z . This allows us to follow an analogous counting and splicing argument to apply to certificates on the central path. 1.2.3

Polynomial advantage for graph symmetry

Our main technique to obtain a quantum advantage for the graph symmetry problem is to reduce the verification of the existence of a non-trivial automorphism to a series of equality problems on a path, which can then be verified using our improved quantum equality protocols from Theorem 5. Reducing symmetry to distributed equality. Recall that a bijection α : V (G) → V (G) is an automorphism exactly when α(N (v)) = N (α(v)) for every vertex v. Thus, once a proposed bijection is fixed, preserving adjacency can be checked by comparing two descriptions: the images of the neighbors of v, and the actual neighbors of its proposed image. These descriptions are available at different vertices, which may be far apart. To perform these comparisons, the prover supplies each vertex v with two identifier values π(v) and σ(v), intended to describe its image and inverse image. It also supplies a path starting at each 2

tr Here we use Fact 1: The number of nodes n of a tree TN,µ (z, z ′ ) is Θ(N log2 N ).

12

vertex v. The classical certificates allow the nodes to verify these paths locally. Write τ (v) for the endpoint of the path starting at v. At this stage, the paths are well defined, but we still need to verify that their endpoints agree with the proposed images and together define an automorphism. We incorporate all these requirements into one equality test per path. At its starting vertex v and endpoint w = τ (v), respectively, we construct the strings
Xv := enc id(v), π(v), deg(v), (π(u))u∈N (v) ,
Yw := enc σ(w), id(w), deg(w), (id(u))u∈N (w) . Here enc is an injective encoding with sorted neighbor lists and padding to a common length. Each endpoint can construct its own string after receiving its neighbors’ identifiers and classical certificate fields. Suppose Xv = Yτ (v) for every v. The second fields give π(v) = id(τ (v)), so each path ends at the claimed image of its source. The first fields give σ(τ (v)) = id(v). In particular, two distinct sources cannot have the same endpoint, since that endpoint has only one value of σ. Thus τ is injective and, on the finite vertex set, bijective. Finally, equality of the degrees and neighbor lists gives τ (N (v)) = N (τ (v)) for every v. Hence τ is an automorphism. To ensure that it is nontrivial, we additionally certify a spanning tree whose root v ∗ satisfies π(v ∗ ) ̸= id(v ∗ ). Conversely, any nontrivial automorphism α provides certificates satisfying these conditions: use its images and inverse images for π and σ, choose paths from v to α(v), and root the spanning tree at a vertex moved by α. All the corresponding string equalities then hold. Consequently, certifying symmetry reduces to verifying the classical data and one equality instance along each certified path. The quantum part performs precisely these equality tests. The prover supplies the quantum registers along the paths, and all quantum operations before reception are independent of the endpoint strings. The nodes can therefore exchange their classical headers and quantum registers in the same round, construct the strings after reception, and then complete the tests that depend on them. For SYMD , we additionally certify the radius bound. This ensures that the paths can be chosen with length at most 2D, allowing us to use the fingerprint equality protocol with a smaller cost. The common string length is N∗ = O(n log n), and at most n comparison paths pass through any e ∗2/3 ) = O(n e 5/3 ). vertex. Thus the distance-independent cost is multiplied by at most n, giving n· O(N Under a radius bound, the fingerprint cost is O(D log N∗ ) per path, hence O(nD log n) overall. This path congestion explains both the need for compression at every vertex in the unrestricted case and the benefit of short paths in the bounded-radius case. For the classical lower bounds in Theorem 4, we use the graphs Bρ (H, H ′ ) of Definition 31, obtained by joining two k-vertex graphs H, H ′ ∈ Fk by a path of ρ ∈ {2µ+2, 2µ+3} edges, where Fk consists of pairwise non-isomorphic asymmetric graphs of diameter at most 2 and minimum degree 2 at least 3. An Erdős–Rényi counting argument gives |Fk | ≥ 2(1−o(1))k /2 (Fact 2), while asymmetry and the degree distinction between the attached graphs and the path ensure that Bρ (H, H ′ ) has a nontrivial automorphism exactly when H = H ′ (Lemma 32). Moreover, its radius is at most ⌈ρ/2⌉ + 2 ≤ µ + 4, so the same family applies to SYMD whenever µ ≤ D − 4 (Fact 3). Then we apply again a fooling-set argument to show that in any µ-round protocol the honest certificate tuples on 2µ central-path vertices must distinguish all instances Bρ (H, H), since otherwise splicing two accepting assignments would violate soundness on some Bρ (H, H ′ ) with H ̸= H ′ (Claim D); counting these tuples forces Ω(k 2 /µ) = Ω(n2 /µ) certificate bits at some node, using n = 2k + ρ − 1 and µ = o(n).

13

1.3

Organization of the paper

In Section 2 we define the model and notations used throughout the paper. In Section 3 we describe the improved upper and lower bounds for the equality problem EQ2N . Then in Sections 4 and 5 we prove Theorem 1 and Theorem 2, respectively.

2

Preliminaries

Graphs. For a positive integer k, write [k] := {1, . . . , k}. All graphs are finite, simple, undirected, and connected. For a graph G = (V, E), we write n = |V |, NG (v) = {u ∈ V : {u, v} ∈ E}, and degG (v) = |NG (v)|. The distance dG (u, v) is the number of edges in a shortest path between u and v. The eccentricity of a vertex v, the radius of G, and its diameter are, respectively, eccG (v) = max dG (u, v), u∈V

rad(G) = min eccG (v), v∈V

diam(G) = max eccG (v). v∈V

In particular, rad(G) ≤ k means that some vertex is within distance k of every vertex, and implies diam(G) ≤ 2k. A path v0 , . . . , vr has r edges and r + 1 vertices. A tree is a connected acyclic graph. A spanning tree of G is a tree with vertex set V and edge set contained in E. In a rooted tree, the parent of a nonroot vertex is its neighbor on the unique path to the root. The depth of a vertex is its distance from the root, and the depth of the rooted tree is the maximum vertex depth. For rooted trees T1 , T2 with roots r1 , r2 , a rooted isomorphism is a graph isomorphism φ : V (T1 ) → V (T2 ) satisfying φ(r1 ) = r2 ; we write T1 ∼ =rt T2 when such an isomorphism exists. An automorphism of G is an isomorphism from G to itself. It is nontrivial if it moves at least one vertex. We call a graph symmetric if it admits a nontrivial automorphism, and asymmetric otherwise. A graph property is a class of graphs closed under isomorphism. We identify a property with the class of graphs satisfying it. Quantum computing. We follow mostly standard notation from quantum computing; see [NC10] for a thorough review. All Hilbert spaces are finite-dimensional. A quantum state is represented by p a positive semidefinite operator of trace one. For vectors, ∥|ψ⟩∥ := ⟨ψ|ψ⟩. For an operator A, its operator norm and trace norm are √ ∥A∥ := sup ∥A|ψ⟩∥, ∥A∥1 := tr A† A. ∥|ψ⟩∥=1

For Hermitian operators, A ⪰ B (equivalently, B ⪯ A) means that A − B is positive semidefinite. For density operators on the same space, the trace distance is 1 D(ρ, σ) := ∥ρ − σ∥1 = max tr(E(ρ − σ)). 0⪯E⪯I 2 A quantum channel is a completely positive trace-preserving map Λ. Trace distance is contractive under channels: D(Λ(ρ), Λ(σ)) ≤ D(ρ, σ). In particular, partial trace discards registers and is a quantum channel; the trace norm also satisfies ∥trB X∥1 ≤ ∥X∥1 . The dual map Λ∗ is defined by tr(EΛ(X)) = tr(Λ∗ (E)X). We use root-fidelity q √ √ √ √ F(ρ, σ) := ∥ ρ σ∥1 = tr ρ σ ρ.

14

Uhlmann’s theorem identifies it with the maximum absolute inner product of purifications of ρ and σ on a common sufficiently large auxiliary space. In particular, any such purifications have overlap at most F(ρ, σ). The Fuchs–van de Graaf inequalities state p 1 − F(ρ, σ) ≤ D(ρ, σ) ≤ 1 − F(ρ, σ)2 . For a pure state |ψ⟩, F(ρ, |ψ⟩⟨ψ|)2 = ⟨ψ|ρ|ψ⟩. A two-outcome POVM is specified by effects {E, I − E} with 0 ⪯ E ⪯ I, and its first outcome has probability tr(Eρ). For an orthogonal projector P , the non-destructive projective measurement {P, I − P } leaves the state in P ρP/tr(P ρ) conditioned on its first outcome. For a pure state this is P |ψ⟩/∥P |ψ⟩∥; states already in the image of P are unchanged. For an N -bit string X, a quantum fingerprint |hX ⟩ has O(log N ) qubits and satisfies |⟨hX |hY ⟩|2 ≤ 1/2 whenever X ̸= Y . Its precise construction is not needed here (see [BCWDW01]). The SWAP operator is S(|a⟩⊗|b⟩) = |b⟩⊗|a⟩, and Π± := (I±S)/2 project onto the symmetric and antisymmetric subspaces. The SWAP test accepts on Π+ and rejects on Π− , with rejection probability tr(Π− ρ) on a joint state ρ. On |ψ⟩ ⊗ |ϕ⟩, its acceptance probability is (1 + |⟨ψ|ϕ⟩|2 )/2. Thus equal fingerprints are accepted with certainty, and distinct ones with probability at most 3/4.

2.1

Local certification models

An instance is a pair I = (G, x), where G = (V, E) is a connected graph with n = |V | nodes and x = (xv )v∈V is an assignment of classical local inputs. A distributed language L is a set of instances. For a graph property, there are no additional inputs, and membership depends only on the isomorphism class of G. Each node v knows its local input and its own distinct identifier id(v) ∈ [U ], where U = nO(1) is a common identifier bound. Its incident edges have distinct local port numbers 1, . . . , deg(v); the port numbers at opposite ends of an edge need not agree. A node can address an outgoing message by its local port and identify the local port on which each incoming classical or quantum message arrives. Our upper bounds use known n, U , and the common problem parameters. Nodes are not initially given the global topology or inputs held elsewhere. The lower bounds hold even with these parameters known. Definition 7 (dMA and dQMA protocols [FLNP21]). A µ-round distributed Merlin–Arthur protocol for L is described as follows. An untrusted prover, Merlin, knows the entire instance and the identifier and port assignments and supplies certificates before the verifiers communicate. The certificates and verification operations depend on the model: • In a classical protocol (dMA), Merlin supplies a classical certificate zv to each node v. The nodes perform randomized classical computation and exchange classical messages. • In a quantum protocol (dQMA), Merlin supplies an arbitrary joint quantum state ρ on O H= Hv , v∈V

with node v receiving the register Hv . The state may be entangled across nodes. The nodes may perform arbitrary local quantum operations, including measurements, and exchange quantum messages. Classical fields are allowed as qubits in the computational basis, measured before other local operations or routing. 15

For fixed size parameters, certificate registers have prescribed finite size. When measured classical records select roles or active register lengths, our upper-bound protocols reserve a fixed maximum register budget and use only the prescribed active slots, ignoring padding. Malformed records or incompatible register formats cause rejection. These budgets apply also on no-instances. After receiving their certificates, the nodes execute µ synchronous communication rounds along the edges of G, with no further interaction with Merlin. In each round, every node prepares and sends its outgoing messages before receiving the messages sent to it in that round, and may then perform local computation. Thus a single round has three phases: local preparation (including measurement of classical certificate fields), simultaneous message exchange, and local computation and measurements after reception. Operations before reception may depend only on information already available locally. Local computation, local workspace, and message sizes are unrestricted. Therefore, verification can be viewed as a µ-round (classical or quantum) LOCAL algorithm with private randomness and no prior shared entanglement beyond the supplied quantum certificates. Our classical lower bounds also hold when the verifiers additionally share public randomness, sampled after the certificates have been supplied. At the end of verification, each node outputs accept or reject, and the network accepts if and only if every node accepts. Let Acc denote the event that the network accepts. The protocol has completeness c and soundness error s, where 0 ≤ s < c ≤ 1, if, for every instance I, I∈L

=⇒

∃ Γ : Pr[Acc | I, Γ] ≥ c,

I∈ /L

=⇒

∀ Γ : Pr[Acc | I, Γ] ≤ s.

Here, Γ ranges over all certificates of the prescribed size: classical certificate assignments in dMA and arbitrary joint quantum states in dQMA. Probabilities are taken over the verifiers’ randomness and, in the quantum model, their measurement outcomes. The certificate size is the maximum number of certificate bits in dMA, or qubits in dQMA, per node, in the worst case over instances with the relevant size parameters fixed (these parameters include n and, for problems involving input strings, their length N ). The message size is the maximum number of bits or qubits in one directed edge message in any round. Classical fields count toward the corresponding message and certificate sizes. All upper bounds below bound both resources, although message size is unrestricted in the model and in our lower bounds. Distributed equality. In the distributed equality problem EQtN , a set of t ≥ 2 designated nodes, called terminals, hold strings x1 , . . . , xt ∈ {0, 1}N . The task is to verify whether x1 = x2 = · · · = xt . Nonterminal nodes hold no input. In the path setting, the network is a path P = v0 , . . . , vr , the two terminals v0 , vr are its endpoints, and their inputs are denoted by x and y. We use N for the length of each input string and n for the number of network nodes. e and Ω e hide polylogarithmic factors in the relevant size Asymptotic notation. The notations O parameter: in n for bounds in the number of nodes, and in N for bounds in the input-string length. Unless explicitly written as ln, logarithms are to base 2.

3

Distributed equality problem

In this Section we prove Theorem 5 by giving two independent protocols achieving the corresponding bounds.

16

3.1

Improved analysis of the equality protocol

In this section we prove the O(r log N ) upper bound of Theorem 5. This result is proved by a refined analysis of the previous protocols used in [FLNP21, HKN24]. Let m ∈ Θ(r) be the repetition parameter to be fixed afterwards. We first describe our protocol, which is almost identical to the one from [HKN24]. Protocol 1 Certificate. For each repetition k ∈ [m], each node vj with 0 ≤ j ≤ r −1 receives an ordered (k) (k) (k) pair of blocks (Aj , Bj ), and vr receives a single block Ar . On a yes-instance the honest certificate places every individual block in the state |hx ⟩, so each pair is in |hx ⟩⊗2 and the single block at vr is in |hx ⟩. Communication. Independently for each repetition k: each vj with 0 ≤ j ≤ r − 1 flips (k) (k) a private fair coin sj and, if sj = 1, swaps the two blocks of its pair. This is the symmetrization step, which we import from the improved equality protocol of Hasegawa, Kundu and Nishimura [HKN24]. Concretely, the node either applies the unitary that exchanges the two ℓ-qubit blocks, or does nothing, each with probability 12 . This is equivalently implemented by preparing an ancilla qubit in |+⟩, applying the swap controlled on the ancilla, and discarding the ancilla. The node then sends the post-swap (k) (k) register B̃j to vj+1 and keeps the other register Ãj . Tests. For each repetition k: (k)

Test T0 : Node v0 measures {|hx ⟩⟨hx |, I − |hx ⟩⟨hx |} on Ã0 outcome.

and accepts on the first (k)

(k)

Test Tj : Each intermediate vj , 1 ≤ j ≤ r − 1, performs the swap test on (B̃j−1 , Ãj ). Test Tr and Tr+1 : Node vr flips a private fair coin t(k) and performs the swap test on (k) (k) (k) (B̃r−1 , Ar ) if t(k) = 0 (Tr ), or measures {|hy ⟩⟨hy |, I − |hy ⟩⟨hy |} on Ar if t(k) = 1 (Tr+1 ). It rejects iff the performed test fails. Per node this uses 2mℓ proof qubits and mℓ message qubits, where m is the repetition parameter and ℓ is the size of the fingerprints. By choosing m ∈ O (r) and using the fact that the fingerprints have size O(log N ), we conclude that it uses O(r log N ) qubits each for m = Θ(r). Completeness is perfect and the analysis is trivial. What remains to be done is thus the proof of soundness. Soundness We show that when x ̸= y, the probability that some node rejects is Ω(1/r) in each repetition k of Protocol 1, for any (possibly entangled) quantum proofs. Before that, we first prove the following lemma. Lemma 8. Let ρ be a bipartite state on two registers A and B with dim A = dim B, let Π± be a projector onto the symmetric and antisymmetric subspaces, and set the rejection probability of the swap test α := tr(Π− ρ) and κ := ∥Π+ ρΠ− ∥1 . Then 1. D(ρA , ρB ) ≤ 2κ p √ 2. κ ≤ α(1 − α) ≤ α 17

where ρA , ρB are the reduced states on registers A and B and D is the trace distance. Proof. Let S = Π+ − Π− be the swap operator. Then we have

ρA − ρB = trB ρ − SρS = 2trB Π+ ρΠ− + Π− ρΠ+ , using trB (SρS) = trA (ρ) and SΠ± = ±Π± . The partial trace does not increase ∥ · ∥1 , so 1 D(ρA , ρB ) = ∥ρA − ρB ∥1 ≤ (∥Π+ ρΠ− ∥1 + ∥Π− ρΠ+ ∥1 ) 2 = 2κ. For a pure state ρ = |ψ⟩⟨ψ|, Π+ |ψ⟩⟨ψ|Π− is a rank-1 operator and its trace norm is κ = ∥Π+ |ψ⟩⟨ψ|Π− ∥1 = ∥Π+ |ψ⟩∥ · ∥Π− |ψ⟩∥ p = α(1 − α) P P For a mixed state ρ = k pk |ψk ⟩⟨ψk | and αk = ∥Π− |ψk ⟩∥2 we have α = k pk αk by linearity. Now similarly to the case of pure states, κ = ∥Π+ ρΠ− ∥1 = ∥

X

pk Π+ |ψk ⟩⟨ψk |Π− ∥1

k

≤

X

pk ∥Π+ |ψk ⟩⟨ψk |Π− ∥1

k

≤

X

=

X

pk ∥Π+ |ψk ⟩∥ · ∥Π− |ψk ⟩∥

k

pk

p αk (1 − αk ).

k

The concavity of α 7→

p

α(1 − α) gives κ ≤

p α(1 − α).

The next proposition improves the Ω(1/r2 ) lower bound for the rejection probability in the earlier protocols in [FLNP21, HKN24] to Ω(1/r). The distinction is that we keep the tests’ joint P rejecting weight. Separate estimates D(µj−1 , µj ) ≤ √ 2κj ≤ 2 αj and Cauchy–Schwarz yield only j αj = Ω(1/r); relating this sum to the probability of P any rejection can lose another factor of r. The hypercube decomposition below instead bounds j κj directly by the total weight outside the all-accepting subspace, avoiding this second loss. Lemma 9 (Soundness of a single repetition). Suppose x ̸= y. Then for every state of the blocks of a fixed repetition k ∈ [m], arbitrarily entangled internally and with the rest of the proof, the probability 1 that all tests of repetition k accept is at most 1 − γ, where γ := 70(r+1) . Proof. We focus on a single repetition k of Protocol 1 and drop the superscript k for simplicity. Before the one-round communication, each node vj (0 ≤ j ≤ r − 1) holds a pair of registers (Aj , Bj ) and vr holds Ar . After the symmetrization step we write the registers (Ãj , B̃j ), and B̃j is sent to vj+1 . The reduced states on the two registers Ãj , B̃j are identical, and we denote both by µj . Indeed, if ρAj and ρBj are their marginals before symmetrization, then µj = (ρAj + ρBj )/2. This identity makes the trace-distance bounds telescope along the path. Let Px := |hx ⟩⟨hx | and Py := |hy ⟩⟨hy |. 18

Let ν be the reduced state of Ar , let α0 := 1 − tr(Px µ0 ) and αr+1 := 1 − tr(Py ν), and for 1 ≤ j ≤ r let κj = ∥Π+ σj Π− ∥1 be the quantity of Lemma 8 performed by the node vj on the reduced state σj on (B̃j−1 , Ãj ). Then by definition, the reduced states of σj on each of the two registers are (µj−1 , µj ) for j ≤ r − 1 and (µr−1 , ν) for j = r. Let q be the probability that some test (of the fixed repetition k) rejects. Since the test
T0 is always performed and the test Tr+1 is performed with probability 21 , q ≥ max α0 , 12 αr+1 . If 1 1 1 α0 ≥ 100 or αr+1 ≥ 70 , then q ≥ 140 ≥ γ for every r ≥ 1, and we are done. Hence assume that 1 1 α0 < 100 and αr+1 < 70 . By Lemma 8 and the triangle inequality, D(µ0 , ν) ≤

r−1 X

D(µj−1 , µj ) + D(µr−1 , ν)

j=1 r X

≤2

κj ,

j=1

while testing the observable |hy ⟩⟨hy | against the pair (µ0 , ν) gives    √  1 − 21 + α0 ≥ 0.39, D(µ0 , ν) ≥ tr(|hy ⟩⟨hy | · ν) − tr(|hy ⟩⟨hy | · µ0 ) ≥ 1 − 100 1 using tr(|hy ⟩⟨hy | · µ0 ) ≤ tr(|hy ⟩⟨hy | · |hx ⟩⟨hx |) + D(µ0 , |hx ⟩⟨hx |), tr(|hy ⟩⟨h Pyr| · |hx ⟩⟨hx |) ≤ 2 for x ̸= y, √ and the Fuchs–van de Graaf inequality D(µ0 , |hx ⟩⟨hx |) ≤ α0 . Hence j=1 κj ≥ 0.19. For each node, we define two orthogonal projectors (good and bad) defined by the performed test. Specifically, (0)

(0)

• Q+ = |hx ⟩⟨hx | and Q− = I − |hx ⟩⟨hx | (j)

(j)

• Q+ = Π+ and Q− = Π− for 1 ≤ j ≤ r (j)

(j)

(j)

(j)

where Q+ + Q− = I and Q+ Q− = 0 for all 0 ≤ j ≤ r. Let |Ψ⟩ be a purification of the post-symmetrization proof state, including the untouched control ancillas and any other purifying registers. The identity factor below acts on those ancillary registers. The test register sets Ã0 , (B̃j−1 , Ãj ) for 1 ≤ j < r, and (B̃r−1 , Ar ) are pairwise disjoint. Conditioned on the independent endpoint coin being t(k) = 0, the tests T0 , . . . , Tr are exactly these commuting projective measurements. For each z = z0 z1 · · · zr ∈ {0, 1}r+1 , we write (1) (r) |ψz ⟩ = (Q(0) z0 ⊗ Qz1 ⊗ · · · ⊗ Qzr ⊗ I)|Ψ⟩ (j)

(j)

(j)

where in this relation Qzj is Q+ for zj = 0 and Q− for zj = 1. Define az := ∥|ψz ⟩∥. The projectors defining these vectors are mutually orthogonal and sum to the identity, so X a2z = ∥|Ψ⟩∥2 = 1. z∈{0,1}r+1

By definition we have

(j)

(j)

κj = ∥Q+ σj Q− ∥1 and σj = tr¬j (|Ψ⟩⟨Ψ|) 19

where tr¬j traces out all registers except the registers used for the test of node vj . Using |Ψ⟩ = P z |ψz ⟩, X X (j) (j) (Q+ ⊗ I)|Ψ⟩⟨Ψ|(Q− ⊗ I) = |ψz ⟩⟨ψz ′ |. z:zj =0 z ′ :zj′ =1

Thus we have

(j)

(j)

X

Q+ σj Q− =

X

tr¬j (|ψz ⟩⟨ψz ′ |)

z:zj =0 z ′ :zj′ =1

Next we show that for z, z ′ with Hamming distance at least 2, tr¬j (|ψz ⟩⟨ψz ′ |) = 0: there is a (i) (i) position i ̸= j at which z and z ′ differ. Since this position is traced out, Qzi Qz ′ = 0 and i

   (i) Q(i) zi ⊗ I |ψz ⟩⟨ψz ′ | Qz ′ ⊗ I   i (i) (i) = tr¬j Qzi Qz ′ ⊗ I |ψz ⟩⟨ψz ′ |

tr¬j (|ψz ⟩⟨ψz ′ |) = tr¬j



i

= 0. Therefore, we have (j)

(j)

X

Q+ σj Q− =

tr¬j (|ψz ⟩⟨ψz⊕ej |).

z:zj =0

Here ej is a vector whose j-th element is 1 and the other elements are 0. By contractivity of the trace norm under partial trace, tr¬j (|ψz ⟩⟨ψz⊕ej |) 1 ≤ |ψz ⟩⟨ψz⊕ej | 1 = az az⊕ej . Therefore, (j)

(j)

κj = ∥Q+ σj Q− ∥1 X ≤ ∥tr¬j (|ψz ⟩⟨ψz⊕ej |)∥1 z:zj =0

≤

X

az · az⊕ej .

z:zj =0

Summing up over all 1 ≤ j ≤ r, we have r X

X

κj ≤

j=1

az az ′

{z,z ′ }: an edge of the hypercube {0,1}r+1

P Define q□ := 1 − a20 = z̸=0 a2z where 0 = 0r+1 is all-zero vector. This is exactly the probability that some test among T0 , . . . , Tr rejects conditioned on t(k) = 0. Since this coin outcome has probability 1/2, the unconditional rejection probability satisfies q ≥ q□ /2. Now our goal is to bound q□ . To this end, we divide X {z,z ′ }: an edge of the hypercube {0,1}r+1

az az ′ =

r X

az az ′

{z,z ′ }: an edge of the hypercube {0,1}r+1 ,z̸=0,z ′ ̸=0

i=0

|

X

a0 aei + {z (I)

} 20

|

{z

(II)

}

By Cauchy-Schwarz (I) =

r X

v v ! r u r u r X X u X p u t 2 2 t a0 aei ≤ 1 · aei = (r + 1) · a2ei ≤ (r + 1)q□ .

i=0

i=0

i=0

i=0

For (II), using 2az az ′ ≤ a2z + a2z ′ , we obtain (II) ≤

=

1 2

X

(a2z + a2z ′ )

{z,z ′ }: an edge of {0,1}r+1 z̸=0, z ′ ̸=0

1X deg(z) · a2z 2 z̸=0

r+1X 2 ≤ az 2 z̸=0

r+1 = q□ . 2 The second inequality holds because the degree of each vertex z is at most r + 1. To summarize, 0.19 ≤ (I) + (II) ≤

p 1 (r + 1) · q□ + (r + 1) · q□ . 2

p 1 With u := (r+1)q□ , the constraint u + u2 /2 ≥ 0.19 gives u ≥ 0.174, i.e. q□ ≥ 35(r+1) and 1 q ≥ 70(r+1) ≥ γ. Lemma 10. With m := ⌈70(r + 1) ln 3⌉ = Θ(r) repetitions, the protocol has perfect completeness and soundness error at most 1/3 against arbitrary entangled certificates, with O(r log N ) qubits of proof and of messages per node. Proof. Completeness obviously holds. For x ̸= y, let Mk be the effective accepting POVM element of repetition k, averaged over its private coins. Lemma 9 bounds tr(Mk σ) ≤ 1 − γ for every state σ, so ∥Mk ∥ ≤ 1 − γ. The Nmrepetitions use disjoint registers and independent coins; hence their joint accepting effect is k=1 Mk . For any certificate state ρ, including states entangled across repetitions, " m ! # m O Y Mk ρ ≤ ∥Mk ∥ ≤ (1 − γ)m ≤ e−γm ≤ 13 . tr k=1

3.2

k=1

A new equality protocol

e 2/3 ) upper bound of Theorem 5. In the protocol used to prove the In this section, we prove the O(N O(r log N ) upper bound, the O(r) repetitions are inevitable, as it is known that there is a concrete cheating strategy for o(r) repetitions [FLNP21, Section 3]. Therefore, to obtain a new protocol without dependence on r, we need to design a new protocol.

21

Roadmap. The full symmetric subspace accepts |ψ⟩⊗2 for every pure |ψ⟩, permitting gradual

L L+1 rotation along a path. Our subspace WL has dimension 1 + 2 , rather than 2 , and imposes equality of the diagonal amplitudes in addition to symmetry. These constraints force the chain’s zero-energy space to be the span St of tensor powers of the finitely many phase labels. They prevent arbitrary pure-state powers from remaining accepting along the chain. The proof uses two length scales. The three-register estimate first yields the inverse-square bound Ht ⪰ 4t−2 (I − Gt ). Grouping m = Θ(L log L) registers into a block makes distinct label powers nearly orthogonal: their off-diagonal Gram-matrix row sums are at most 1/10. The resulting overlapping-block gap exceeds 3/4, so a Knabe bound promotes the Ω(1/m2 ) estimate on a pair of blocks to the same lower bound on arbitrarily long chains. The detectability lemma then gives rejection probability Ω(1/m2 ) for unequal endpoint labels. This also explains the parameters below. Taking K = Θ(m2 ) Reed–Solomon evaluations amplie 3 ), fies rejection to a constant. Each evaluation carries Θ(L) classical bits, so N = Θ(KL) = Θ(L 2 e whereas each vertex receives O(K log L) = O(L ) qubits. Thus the exponent 2/3 comes from the ratio between these cubic input and quadratic certificate scales. 3.2.1

Encoding of classical strings

We first describe a fixed encoding of a classical input X ∈ {0, 1}N into K quantum states of O(log L) qubits, which is based on the standard Reed–Solomon encoding. For simplicity, assume that N = KL/6, where L is divisible by 3 and sufficiently large, and set    
L 6L m := ln L + , K := 2 300(ln 3)m2 = Θ L2 (log L)2 . 2 5 Thus K is even, K ≥ 600(ln 3)m2 , and, for sufficiently large L, K ≤ 2L/3 . General input lengths are handled by padding both inputs with zeros to the next admissible length; finitely many smaller lengths can be handled directly. These parameters give N = Θ(L3 (log L)2 ) and L = Θ(N 1/3 (log N )−2/3 ). The certificates have 2K⌈log L⌉ qubits per node, hence size  
O L2 (log L)3 = O N 2/3 (log N )5/3 . Given a string X ∈ {0, 1}N , divide X into K/2 consecutive blocks of length L/3. We regard each block as an element of the finite field with 2L/3 elements. That is, the input X is a sequence of such elements q0 , . . . , qK/2−1 . Next, use these K/2 field elements as the coefficients of a polynomial K/2−1

fX (t) :=

X

qi ti

i=0

of degree at most K/2−1. Fix K distinct field elements g1 , . . . , gK , and evaluate fX at these points: fX (g1 ), . . . , fX (gK ). If X ̸= Y , then fX − fY is a nonzero polynomial of degree at most K/2 − 1 and can vanish at no more than K/2 − 1 points. Consequently, fX (gb ) ̸= fY (gb ) for at least K/2 values of b. We next fix 2L/3 binary strings of length L such that any two distinct chosen strings differ in at least L/8 and at most 7L/8 positions (such a collection can be obtained greedily), and fix a one-to-one correspondence between the 2L/3 field elements and these selected strings. For each b, let zb (X) be the L-bit label corresponding to fX (gb ). 22

In this way, we obtain K strings z1 (X), . . . , zK (X) ∈ {0, 1}L from an N -bit string X. By construction, if X ̸= Y , then for at least K/2 positions b, the two labels zb (X) and zb (Y ) have Hamming distance between L/8 and 7L/8. For completeness, let H2 (p) := −p log2 p−(1−p) log2 (1− p). For each selected string, fewer than X L ≤ 21+H2 (1/8)L < 20.55L 2 j j<L/8

strings are excluded by the two forbidden distance ranges, for sufficiently large L, since H2 (1/8) < 0.55. Greedy selection therefore yields at least 20.45L ≥ 2L/3 strings. We now define the corresponding label states. Definition 11 (Label states). For every L-bit string u = u1 · · · uL ∈ {0, 1}L , define L

1 X |ϕu ⟩ = √ (−1)ux |x⟩, L x=1 and let  WL = span |ϕu ⟩ ⊗ |ϕu ⟩ : u ∈ {0, 1}L . Each physical register has ⌈log L⌉ qubits. We embed CL as the span of its first L computational basis vectors, labelled |1⟩, . . . , |L⟩. Let ΠL be the orthogonal projector onto WL , extended by zero on the rest of the two-register physical space. Thus an accepting pre-communication measurement removes every component outside CL ⊗CL , justifying the subsequent chain analysis on L-dimensional registers. The definition of WL uses all L-bit strings, including those not used by the encoding. The identity

2 dist(u, v) L shows why both distance restrictions matter: complementing all bits negates a label state. At each of the K/2 positions for which zb (X) and zb (Y ) differ, ⟨ϕu |ϕv ⟩ = 1 −

ϕzb (X) ϕzb (Y )

3 ≤ . 4

Protocol. Given these definitions, we describe our protocol. Protocol 2 1. Certificates and local preparation. For every node vi and every index b ∈ [K], the prover supplies a certificate register Ai,b ⊗ Bi,b , each containing ⌈log L⌉ qubits. The node performs the non-destructive projective measurement {ΠL , I − ΠL } on Ai,b ⊗ Bi,b and records rejection on the second outcome. The accepting outcome projects onto WL and leaves every state already in WL unchanged. 2. Communication. Each node vi with i < r keeps all registers Ai,b and sends all registers Bi,1 , . . . , Bi,K to vi+1 . The right endpoint vr keeps its register Br,b . After the communication, vi holds Bi−1,b Ai,b for every 1 ≤ i ≤ r. 3. Measurements and acceptance. For every b ∈ [K], the following measurements are performed, where accepting projectors are defined in Definition 11 (the rejecting

23

projector is the orthogonal complement of the corresponding accepting projector). node

register(s)

accepting projector

v0

A0,b

|ϕzb (X) ⟩⟨ϕzb (X) |

vi (1 ≤ i ≤ r)

Bi−1,b Ai,b

ΠL

vr

Br,b

|ϕzb (Y ) ⟩⟨ϕzb (Y ) |

A node accepts if every measurement assigned to it, for every b ∈ {1, . . . , K}, has the accepting outcome. The protocol accepts if and only if every node accepts. At the right endpoint vr , the received register Br−1,b and the local registers Ar,b , Br,b serve two distinct tests: the link test on Br−1,b Ar,b and the endpoint test on Br,b . Both are performed. Steps 1 and 2 are independent of X and Y ; only the final endpoint tests in Step 3 use those strings. This permits a single-round composition with classical input reconstruction. Perfect completeness. When X = Y , the two endpoints have the same label at every index b. For each node and each b, the prover directly supplies the state in WL |ϕzb (X) ⟩ ⊗ |ϕzb (X) ⟩. The resulting state for this index is

|ϕzb (X) ⟩⊗(2r+2) ,

so every measurement accepts with probability one. 3.2.2

Soundness for one label index

We write z = zb (X), w = zb (Y ) for z ̸= w for a fixed index b ∈ [K] and analyze Protocol 2 for this b. Set m = ⌈ L2 ln L + 6L 5 ⌉. We prove the following. Lemma 12. For the distinct labels z = zb (X), w = zb (Y ), every certificate in Protocol 2 is rejected by at least one node with probability at least   1 1 =Ω . 129m2 L2 (log L)2 The chain Hamiltonian To prove Lemma 12, we first study the sum of the rejection probabilities of the tests of intermediate nodes in Protocol 2 whose accepting projector is ΠL . At the fixed label index b, Ai , Bi denote the registers Ai,b and Bi,b at vertex vi for simplicity. Set n = 2r + 2 (only in this chain analysis, n denotes the number of registers rather than graph vertices) and identify these n registers, in order, with A0 , B0 , A1 , B1 , . . . , Ar , Br . For each integer t ≥ 2, consider an ordered chain of t registers, each with Hilbert space CL , and define t−1 X Ht = (I − Πj,j+1 ) on (CL )⊗t . j=1

24

Here Πj,j+1 acts as ΠL on registers j and j + 1 and as the identity on all other registers. We use the same superscript convention specifying the registers to be considered for other operators. Under this notation, r r X X Hn = (I − ΠAi Bi ) + (I − ΠBi−1 Ai ). i=0

i=1

The first sum corresponds to the measurements before communication, and the second to those after communication in Protocol 2. The two endpoint measurements are not included in Hn . We may also apply Ht to any t consecutive registers in the above ordering, numbering the registers within that interval from 1 to t from left to right. Therefore, for a quantum state |x⟩, ⟨x|Ht |x⟩ is the sum of the rejection probabilities when each adjacent-pair test is applied separately to |x⟩. In the language of Hamiltonian complexity, Ht is a frustration-free local Hamiltonian on a chain of qudits. The accepting space. Let St = span{|ϕu ⟩⊗t : u ∈ {0, 1}L }. Every vector |ϕu ⟩⊗t is accepted by every test, and thus a ground state of Ht , meaning St ⊆ kerHt . The following lemma shows the two spaces are identical. Lemma 13. For every t ≥ 2, kerHt = St . Moreover, every vector in St is fixed by every permutation of the registers. Proof. Since St ⊆ kerHt is obvious, we focus on proving kerHt ⊆ St . First, observe that 1 X |aa⟩, |Ω⟩ = √ L a

|sab ⟩ =

|ab⟩ + |ba⟩ √ 2

(1 ≤ a < b ≤ L)

is an orthonormal basis of WL : From the definition of label states, √ 2X 1 ⊗2 |ϕu ⟩ = √ |Ω⟩ + (−1)ua +ub |sab ⟩, L L a<b hence every state in WL is spanned by this basis. On the other hand, averaging over all strings u gives √ 1 X 1 1 X 2 ⊗2 ua +ub ⊗2 |ϕu ⟩ = √ |Ω⟩, (−1) |ϕu ⟩ = |sab ⟩ L 2L 2 L L u u∈{0,1}L hence |Ω⟩, |sab ⟩ ∈ WL . L L ⊗2 as PLLet |1⟩, . . . , |L⟩ be an orthonormal basis of C , and write an arbitrary state in (C ) a,b=1 dab |ab⟩. Suppose that this state is in WL and write X

dab |ab⟩ = α|Ω⟩ +

a,b

X

βab |sab ⟩.

a<b

Comparing the coefficients gives α daa = √ L

(1 ≤ a ≤ L), 25

βab dab = √ 2

(a < b),

and in particular, for all a ̸= b ∈ [L], daa = dbb , Conversely a state in WL . Next, write

PL

a,b=1 dab |ab⟩ satisfying (4) equals

X

|x⟩ =

a=(a1 ,··· ,at )∈[L]t

√

X

x(a)|a⟩ =

(4)

dab = dba . L d11 |Ω⟩ +

√ P 2 a<b dab |sab ⟩ and thus lies

x(a)|a1 ⟩ ⊗ · · · ⊗ |at ⟩ ∈ kerHt .

a=(a1 ,··· ,at )∈[L]t

P Since Ht = j (I − Πj,j+1 ) is a sum of positive semidefinite operators, |x⟩ ∈ ker Ht if and only if Πj,j+1 |x⟩ = |x⟩ for every j, that Pis, if and only if for every j and every fixed choice of the entries other than aj , aj+1 , the vector aj ,aj+1 x(a)|aj aj+1 ⟩ lies in WL . By (4), this holds if and only if x(· · · , aj , aj+1 , · · · ) = x(· · · , aj+1 , aj , · · · ),

x(· · · , a, a, · · · ) = x(· · · , b, b, · · · ).

(5)

For a ∈ [L]t , let p(a) ∈ {0, 1}L be the vector whose c-th entry is the number of occurrences of the symbol c in a, modulo two. Then, the coefficient x(a) is determined by p(a): for every symbol c, keep one instance of c that appears an odd number of times in a, group the remaining into pairs, replace all of them with 11 by the two operations of (5), and arrange the remaining symbols in increasing order. The sequence obtained by this operation is determined solely by p(a) and t. Then, for X |vp′ ⟩ = |a1 · · · at ⟩ (p′ ∈ {0, 1}L ), a:p(a)=p′

|x⟩ ∈ span{|vp′ ⟩}p′ ∈{0,1}L . On the other hand, by the definition of label states, X 1 ′ |ϕu ⟩⊗t = √ (−1)u·p |vp′ ⟩. t L p′ ∈{0,1}L Therefore, √

Lt · 2L

X

′

(−1)u·p |ϕu ⟩⊗t =

u∈{0,1}L

1 2L

′′

X

′

(−1)u·p +u·p |vp′′ ⟩

u,p′′ ∈{0,1}L

1 2L

= |vp′ ⟩ +

X

′′

′

(−1)u·(p +p ) |vp′′ ⟩

u,p′′ ∈{0,1}L :p′′ ̸=p′

= |vp′ ⟩. Here, the last equality used the following. For each p′′ ̸= p′ , choose an arbitrary index k such that p′′k ̸= p′k . Since p′′k ̸= p′k ∈ {0, 1}, we have p′′k + p′k ≡ 1 (mod 2), which simplifies the coefficient of uk in the exponent. Then P X X X ′′ ′ ′′ ′ (−1)u·(p +p ) = (−1) i̸=k ui (pi +pi )+uk u

=

ui ∈{0,1}:i̸=k uk ∈{0,1} P X

(−1)

′′ ′ i̸=k ui (pi +pi )

ui ∈{0,1}:i̸=k

= 0. 26

+ (−1)

P

′′ ′ i̸=k ui (pi +pi )+1

Therefore, we have

|x⟩ ∈ span{|vp′ ⟩}p′ = span{|ϕu ⟩⊗t }u ,

meaning kerHt ⊆ St . Finally, every |ϕu ⟩⊗t is fixed by every permutation of the registers, hence so is every vector in St . A spectral gap independent of the path length. Let Gt be the orthogonal projector onto St . For the proof of Lemma 12, we use the following lemma showing a spectral gap of the Hamiltonian that is independent of the path length r. Its proof appears later in this subsection, under Spectral gap of the Hamiltonian. Lemma 14 (Spectral gap). For every integer s ≥ 2, with m as in the statement of Lemma 12, Hsm ⪰

1 (I − Gsm ). 4m2

We next combine this bound with the endpoint conditions. Lemma 15. For the distinct labels z, w fixed above, let t ≥ 2 and let |x⟩ ∈ (CL )⊗t satisfy
|ϕz ⟩⟨ϕz | ⊗ I ⊗(t−1) |x⟩ = |x⟩,
I ⊗(t−1) ⊗ |ϕw ⟩⟨ϕw | |x⟩ = |x⟩. Then ⟨x|Ht |x⟩ ≥

∥|x⟩∥2 . 32m2

Proof. First suppose that t = sm for an integer s ≥ 2. Let F exchange the first and last registers. Every vector in St is fixed by F , so the orthogonal projector (I − F )/2 vanishes on St . Hence, for any vector |v⟩, 2 I −F I −F ⟨v| |v⟩ = |v⟩ 2 2 2 I −F (I − Gt )|v⟩ = 2

≤ ∥(I − Gt )|v⟩∥2 = ⟨v|(I − Gt )|v⟩. The inequality holds because an orthogonal projection cannot increase the norm. We now have the inequality I −F ⪯ I − Gt . 2 The endpoint conditions imply |x⟩ = |ϕz ⟩ ⊗ |χ⟩ ⊗ |ϕw ⟩ for some vector |χ⟩ on the middle t − 2 registers. Consequently, ⟨x|F |x⟩ = |⟨ϕz |ϕw ⟩|2 ∥|x⟩∥2 .

27

Combining it with the above inequality and the spectral-gap bound of Lemma 14 gives 1 ⟨x|(I − Gt )|x⟩ 4m2 I −F 1 ⟨x| ≥ |x⟩ 2 4m 2 1 − |⟨ϕz |ϕw ⟩|2 = ∥|x⟩∥2 8m2 ∥|x⟩∥2 , ≥ 32m2

⟨x|Ht |x⟩ ≥

where the last inequality uses |⟨ϕz |ϕw ⟩| ≤ 3/4. This completes the proof when t = sm. For arbitrary t, choose t′ = sm > t with s ≥ 2 and set ′

|e x⟩ = |x⟩ ⊗ |ϕw ⟩⊗(t −t) . The last register of |x⟩ is fixed to |ϕw ⟩. Thus every newly added adjacent pair, including the pair joining the original and appended registers, is in the state |ϕw ⟩ ⊗ |ϕw ⟩ and is accepted by ΠL . Therefore ⟨e x|Ht′ |e x⟩ = ⟨x|Ht |x⟩, ∥|e x⟩∥2 = ∥|x⟩∥2 . The vector |e x⟩ satisfies the same endpoint conditions, so applying the case already proved at length t′ gives the claim. Proof of Lemma 12 Let
A
B H ′ = Hn + I − |ϕz ⟩⟨ϕz | 0 + I − |ϕw ⟩⟨ϕw | r be the sum of all rejecting projectors at the fixed label index b. We use the detectability lemma in the following form. P Proposition 16 (Detectability lemma, [AAV16]). Let R1 , . . . , RM be projectors and H = k Rk , and assume Q that each Rk commutes with all but at most g of the others. For a unit vector |ψ⟩, let |ξ⟩ = k (I − Rk )|ψ⟩, where the product is taken in arbitrary order. If |ξ⟩ ̸= 0 and ϵ := ⟨ξ|H|ξ⟩/∥|ξ⟩∥2 , then 1 ∥|ξ⟩∥2 ≤ . 1 + ϵ/g 2 Using Lemma 15 and the detectability lemma, we can prove Lemma 12. Proof of Lemma 12. The certificate may be entangled with the registers of the other label indices. Tracing these registers out leaves a mixed state on the 2r + 2 registers of the index b, and since the acceptance probability is linear in the state, it suffices to consider a pure state |ψ⟩ on these registers. Let ! r ! r Y Y A0 Br Bi−1 Ai Ai Bi |ϕ⟩ := (|ϕz ⟩⟨ϕz |) (|ϕw ⟩⟨ϕw |) · Π Π |ψ⟩. i=1

i=0

The rightmost product is applied before communication and the remaining factors after communication. The acceptance probability is therefore ∥|ϕ⟩∥2 . If |ϕ⟩ = 0, the protocol rejects with certainty. 28

Otherwise, all projectors applied after communication act on disjoint registers, so both endpoint projectors fix |ϕ⟩. Their rejecting projectors therefore annihilate |ϕ⟩, and Lemma 15 with t = n gives ⟨ϕ|H ′ |ϕ⟩ ⟨ϕ|Hn |ϕ⟩ 1 = ≥ . 2 2 ∥|ϕ⟩∥ ∥|ϕ⟩∥ 32m2 Each term of H ′ shares a register with at most two other terms, and hence commutes with all but at most two of them. Proposition 16 with g = 2 therefore yields ∥|ϕ⟩∥2 ≤

1 , 1 + 1/(128m2 )

so the protocol rejects with probability at least 1/(128m2 + 1) ≥ 1/(129m2 ). Spectral gap of the Hamiltonian Now we move to the proof of the spectral gap shown in Lemma 14. To do so, we use projectors on pairs of blocks, following earlier arguments [FNW92, Nac96] for proving spectral gaps of one-dimensional frustration-free Hamiltonians. We fix s ≥ 2, consider the sm registers on which Hsm acts, and partition the registers into s consecutive blocks be the projector onto S2m on the 2m registers of these of m registers each. For 1 ≤ j < s, let Gj,j+1 2m two blocks, and let γj = I − Gj,j+1 (1 ≤ j < s). 2m The two ingredients of the proof are the following claims. Their proofs are given in the appendix. The first uses the three-site gap 1/2 and a weighted sum of local terms to obtain an inverse-square finite-chain estimate. At this scale the three-site bound alone does not give a length-independent gap; the second claim supplies the stronger overlapping-block estimate needed after coarse-graining. Claim A. For every integer t ≥ 2, Ht ⪰

4 (I − Gt ). t2

Claim B. For 1 ≤ j ≤ s − 2, the operator γj + γj+1 has no eigenvalue in the open interval (0, 3/4). For the second claim, Lemma 34 makes distinct label powers on an m-register block nearly orthogonal. The resulting three-block projection estimate, (15), gives a gap at least 9/11 > 3/4 for γj + γj+1 . Thus the block size m = Θ(L log L) raises the local estimate above the threshold in the following Knabe bound. We prove Lemma 14 using Claim A and the following variant of PKnabe’s bound [Kna88]. Claim B gives the condition on γj + γj+1 needed to apply this bound to s−1 j=1 γj . Proposition 17. Let γ1 , . . . , γk be projectors such that γi and γj commute whenever |i − j| ≥ 2, and Pk suppose that γi + γi+1 has no eigenvalue in the open interval (0, 3/4) for 1 ≤ i < k. Then i=1 γi has no eigenvalue in the open interval (0, 1/2). Proof. The operator γi +γi+1 is positive semidefinite with no eigenvalue in (0, 3/4), so (γi +γi+1 )2 ⪰ 3 2 4 (γi + γi+1 ). As (γi + γi+1 ) = γi + γi+1 + γi γi+1 + γi+1 γi , this says 1 γi γi+1 + γi+1 γi ⪰ − (γi + γi+1 ) 4

(1 ≤ i < k).

Expanding the square, k X i=1

!2 γi

=

k X i=1

γi +

k−1 X

X
γi γi+1 + γi+1 γi + γi γj

i=1

1≤i,j≤k |i−j|≥2

29

(6)

⪰

k X i=1

⪰

1 2

k−1

1X γi − γi + γi+1 4 i=1

k X

γi .

i=1

Here, the first inequality applied (6) to the middle sum and the fact that the last sum is positive semidefinite (γi γj is a projector whenever |i − j| ≥ 2). The second inequality holds because each γi P γi+1 ). occurs at most twice in k−1 i=1 (γi +P Every positive eigenvalue λ of i γi therefore satisfies λ2 ≥ λ/2, so λ ≥ 1/2. Proof of Lemma 14. Apply Claim A with t = 2m to each pair of blocks j and j + 1. Note that the blocks j and j + 1 contain 2m registers numbered from (j − 1)m + 1 to (j + 1)m. Claim A thus gives (j+1)m−1 X 4 1 (I − Πi,i+1 ) ⪰ (I − Gj,j+1 γj . 2m ) = 2 (2m) m2 i=(j−1)m+1

Summing over 1 ≤ j < s, s−1 (j+1)m−1 X X

s−1

i,i+1

(I − Π

j=1 i=(j−1)m+1

1 X )⪰ 2 γj . m j=1

In the left-hand side, each term (I − Πi,i+1 ) appears at most twice, so 2Hsm ⪰ (LHS). Therefore, to complete the proof, it suffices to show s−1 X j=1

1 γj ⪰ (I − Gsm ). 2

(7)

⊥ . It therefore suffices to show that The right-hand side vanishes on Ssm and equals 12 I on Ssm Ps−1 ker( j=1 γj ) = Ssm and that all positive eigenvalues of the sum are at least 1/2. The latter is easy to see: the projectors γj and γj ′ act on disjoint blocks when |j − j ′ | ≥ 2 and therefore commute, and by Claim B the operatorPγj + γj+1 has no eigenvalue in (0, 43 ). Proposition 17 thus shows that every positive eigenvalue of j γj is at least 1/2. We thus prove the kernel identity. By Lemma 13, G2m is the orthogonal projector onto S2m = ker H2m . Thus, 2m−1 \ ker(I − G2m ) = ker H2m = ker(I − Πi,i+1 ). i=1

For each 1 ≤ j < s, we have γj = I − Gj,j+1 = I ⊗(j−1)m ⊗ (I − G2m ) ⊗ I ⊗(s−j−1)m . 2m Together with the kernel identity above, this gives (j+1)m−1

ker γj =

\

ker(I − Πi,i+1 ).

i=(j−1)m+1

30

Consequently, for every vector |x⟩ on all sm registers, |x⟩ ∈

s−1 \

ker γj

j=1

⇐⇒

(I − Πi,i+1 )|x⟩ = 0 for every 1 ≤ j < s and every (j − 1)m + 1 ≤ i ≤ (j + 1)m − 1

⇐⇒

(I − Πi,i+1 )|x⟩ = 0 for every 1 ≤ i < sm

⇐⇒

|x⟩ ∈ ker Hsm .

Again by Lemma 13, this implies

3.2.3

s−1 \

  s−1 X ker γj = ker  γj  = Ssm .

j=1

j=1

Soundness analysis

Set δ0 := 1/(300m2 ) < 1/(129m2 ), using the one-label rejection bound of Lemma 12. For each label index b ∈ [K], let Qb be the product of the accepting projectors measured before communication, and let Pb be the product of those measured after communication. Within either product, the factors act on disjoint registers, so both Pb and Qb are orthogonal projectors. In particular, Pb† Pb = Pb . The effective accepting POVM element of first measuring Qb and then Pb is Ab = (Pb Qb )† (Pb Qb ) = Qb Pb Qb . The two appearances of Qb in this expression describe a single sequential measurement, rather than measuring it twice. For a position with unequal labels zb (X) ̸= zb (Y ), Lemma 12 gives for every vector |x⟩, ⟨x|Ab |x⟩ = ∥Pb Qb |x⟩∥2 ≤ (1 − δ0 )∥Qb |x⟩∥2 ≤ (1 − δ0 )∥|x⟩∥2 . Thus ∥Ab ∥ ≤ 1 − δ0 at each position b suchNthat zb (X) ̸= zb (Y ). Let ρ be any certificate density operator on the overall registers and Aall = K b=1 Ab . Then the acceptance probability of the entire protocol is Pr[The protocol accepts] = Tr(Aall ρ) ≤ ∥Aall ∥ =

K Y

∥Ab ∥

b=1

≤ (1 − δ0 )K/2 ≤ 1/3, where the second last inequality comes from the fact that for X ̸= Y , at least K/2 positions have different labels. The last inequality follows from our choice of K, since (1 − δ0 )K/2 ≤ e−δ0 K/2 ≤ e− ln 3 = 1/3.

31

3.3

Improved lower bound

To prove our lower bound in Theorem 6, we first formalize quantum protocols on a path as follows. Definition 18 (one-round dQMA on a path). Let v0 , . . . , vr be nodes on a path; v0 holds x ∈ {0, 1}N and vr holds y ∈ {0, 1}N . A protocol specifies finite register sizes and, for each node, input-dependent local operations, as follows. Nr 1. The prover prepares an arbitrary pure state ξ on j=0 Hj , where Hj has c(vj ) qubits, and node vj receives Hj . 2. Simultaneously, each node applies an isometry to its register, producing a kept part and outgoing message registers, and sends each message to the corresponding neighbour; m(vj , vj+1 ) denotes the total qubits exchanged between vj and vj+1 . The isometry of v0 may depend on x, that of vr on y. 3. Each node measures its kept part together with its incoming messages with a two-outcome POVM (accept/reject). The POVM of v0 may depend on x, that of vr on y. The protocol has completeness c and soundness s for EQ2N if: for x = y some proof makes all nodes accept with probability ≥ c, and for x ̸= y, every proof makes all nodes accept with probability ≤ s. Fix a protocol as in Definition 18 with completeness c and soundness s, and for each x fix an honest proof ξx for the instance (x, x) accepted with probability ≥ c. We first observe the following. Lemma 19. On the instance (x, y) with proof ξx , the joint outcome distribution of the measurements of v0 , . . . , vr−2 coincides with that on the instance (x, x) with the same proof. Proof. The only y-dependent elements of the protocol are the isometry and the POVM of vr . The registers measured by vj for j ≤ r − 2 are its kept part and the messages from vj±1 ; none of these is acted on by vr ’s isometry, because in a simultaneous round vr−1 ’s outgoing message to vr−2 is produced from Hr−1 alone, before anything sent by vr arrives. Hence the state of those registers, and the measurements applied to them, are identical in the two instances. Let q∂ := c(vr−1 ) + c(vr ) + m(vr−2 , vr−1 ) be the number of qubits of certificate and messages handled by the two nodes nearest the endpoint holding y. Assume that the protocol runs on proof ξx with left input x and stop after the isometries of v0 , . . . , vr−2 have been applied and their messages sent, but before any operation of vr−1 or vr . Let W := Hr−1 ⊗ Mr−2→r−1 ⊗ Hr , of dimension 2c(vr−1 )+m(vr−2 ,vr−1 )+c(vr ) ≤ 2q∂ , and let σx be the reduced state on W at that moment. After this moment, all remaining operations of vr−1 and vr act only on W and on registers produced from it (the exchanged messages come from Hr−1 and Hr , and the message Mr−1→r−2 is discarded), and are independent of x. Hence there is a POVM element 0 ≤ Ey ≤ 1W , depending only on y and the protocol, with Pr[ vr−1 and vr accept | instance (x, y), proof ξx ] = tr[Ey σx ] ,

(8)

which decomposes the acceptance probability to Ey (independent of x) and σx (independent of y). We now show that for distinct x ̸= y, the reduced states σx and σy are Ω(1)-far from each other in trace distance: 32

Lemma 20. For all x ̸= y, tr[Ex σx ] ≥ c and tr[Ey σx ] ≤ s + (1 − c). Consequently D(σx , σy ) ≥ δ := 2c − 1 − s. Proof. The first inequality is completeness together with (8) at y = x: all nodes accepting implies the window pair accepting. For the second, on instance (x, y) with proof ξx let A≤r−2 be the event that v0 , . . . , vr−2 all accept and A∂ the event that both vr−1 and vr accept; these are outcomes of measurements on disjoint registers, so their joint distribution is well defined. Soundness gives Pr[A≤r−2 ∧ A∂ ] ≤ s, and Lemma 19 with completeness gives Pr[A≤r−2 ] ≥ c. Hence tr[Ey σx ] = Pr[A∂ ] ≤ Pr[A≤r−2 ∧ A∂ ] + Pr[¬A≤r−2 ] ≤ s + (1 − c). Finally, for x ̸= y, D(σx , σy ) ≥ tr[Ey σy ] − tr[Ey σx ] ≥ c − s − (1 − c) = δ. Theorem 21. Any one-round dQMA protocol for EQ2N on a path of length r ≥ 2 with fixed completeness c and soundness error s satisfying δ = 2c − 1 − s > 0 has q∂ ≥ Ω(log N ). Moreover, if r ≥ 3, then c(vr−2 ) + c(vr−1 ) + c(vr ) = Ω(log N ), independently of the message sizes. Proof. By Lemma 20, the 2N states {σx } have pairwise trace distance at least δ on W . Write D := dim W . Fix for each x a purification |ψx ⟩ of σx on W ⊗ W ′ , where W ′ has dimension D, so that the |ψx ⟩ are unit vectors in a space of dimension D2 . By Uhlmann’s theorem, |⟨ψx |ψy ⟩| ≤ F(σx , σy ), and by √ the Fuchs–van de Graaf inequality and Lemma 20, F(σx , σy ) ≤ 1 − δ 2 for all x ̸= y. N 2 √ We thus have 2 unit vectors in dimension D whose pairwise inner products are at most 2 1 − δ < 1 in absolute value. By the lower bound argument of [HKN24](see also [DW01, BdW01]), we have log(D2 ) = Ωδ (log N ). Since D ≤ 2q∂ , this proves the first assertion. For the certificate-only assertion, assume r ≥ 3 and let τx be the reduced state of the honest proof ξx on f := Hr−2 ⊗ Hr−1 ⊗ Hr . W The node vr−2 then holds no input. Its fixed local isometry, including any initialized workspace, followed by retaining only its message to vr−1 , defines an input-independent quantum channel. Tensoring this channel with the identity on Hr−1 ⊗ Hr gives a channel Λ satisfying σx = Λ(τx ) for every x. Equivalently, (8) can be written as tr[Ey σx ] = tr[Λ∗ (Ey )τx ], f . By contractivity of trace absorbing the local operation into the accepting POVM element on W distance and Lemma 20, the states τx have pairwise trace distance at least δ. Applying the same packing argument in dimension f = 2c(vr−2 )+c(vr−1 )+c(vr ) dim W proves the second assertion. In particular, at least one of these three nodes receives Ω(log N ) certificate qubits, proving Theorem 6 even with unrestricted messages. The restriction r ≥ 3 is essential here: for r = 2, the input endpoints can send their strings directly to the middle node in one round, with no certificates. 33

4

Exponential quantum advantage

Our first separation is given by a graph property TreeEQµ whose members are trees. To define TreeEQµ , we start with an instance of EQ2N on a path, with one input string at each endpoint. We remove the two input strings and encode each of them in the structure of a tree attached to the corresponding endpoint. The encoding has the following properties: • All encoded graphs are trees (by definition). • The shape of the trees can be verified with a deterministic dMA protocol. • In each tree, the pair of encoded strings can be recovered uniquely from the isomorphism type (Lemma 26).

4.1

Encoding EQ2N into trees

Fix a positive integer µ ≥ 1, known to the nodes, and an even integer N ≥ 8. Set L := ⌈log2 (N/2 + 1)⌉ ,

ρ := 2µ + 1.

The central-path length depends only on µ. We first treat fixed µ and state the uniform parameter dependence at the end of the section. We encode strings z ∈ {0, 1}N of Hamming weight N/2 by their zero-run lengths. If the ones occur at positions p1 < · · · < pN/2 ∈ {0, . . . , N − 1}, define r(z) = (r0 , . . . , rN/2 ) by   i = 0, p1 , ri := pi+1 − pi − 1, 1 ≤ i < N/2,   N − 1 − pN/2 , i = N/2. N/2+1

This is a bijection between balanced N -bit strings and vectors in Z≥0 summing to N/2. The vertex ai will carry ri pendant leaves. To retain the order of these numbers under isomorphism, we attach a tag whose rooted shape identifies i: below ai is the path ai − si − ti , and the distinct-length arms below ti record the bits of i. The rigidity lemma will also exclude accidental tag branches elsewhere in the tree. This gives the following formal definition. Definition 22. For i ∈ {0, . . . , N/2}, the rooted tree Tag(i) has a root s with a single child t. For each b ∈ [L], a path of b edges starts at t. These paths share only t. If the b-th least significant bit of i is 1, we attach two additional leaves to the last vertex of the corresponding path. See Figure 2(a). And using Definition 22 we can finally define the encoding of two input strings z, z ′ into a tree. tr (z, z ′ ) is conDefinition 23. For strings z, z ′ ∈ {0, 1}N of Hamming weight N/2, the tree TN,µ structed as follows. Start with two vertices hL , hR joined by the central path P = hL , w1 , . . . , wρ−1 , hR of ρ edges. Attach N/2 + 1 new vertices a0 , . . . , aN/2 to hL . For each i, attach ri (z) leaves to ai , and join ai by an edge to the root of a disjoint copy of Tag(i). Attach the same structure to hR , using r(z ′ ) in place of r(z). See Figure 2(b).

We use the following useful notation for the rest of the Section. Remark 24. We call ai together with its leaves and its tag the i-th gadget. We call hL together with its gadgets the left side, and define the right side symmetrically. Also, we denote as TL (z) the subtree consisting of hL and all the gadgets attached to it, rooted at hL ; the subtree TR (z ′ ) is defined symmetrically, with root hR . 34

tr ′ Thus, TNtr (z, z ′ )(z, consists of the of two rooted trees Ttrees TRand (z ′ ), Twhose joined the by L (z) and Thus, TN,µ z ′ ) consists the two rooted TL (z) whoseare roots areby joined R (z ), roots central path of ρ edges. the central path of ρ edges. N , the graph T tr (z, z ′ ) is a tree N number FactFact 1. For eachevery N and z, z ′ ∈ {0, 1}µ, its of vertices 1. For positive integer every even NN≥ 8, and z, z ′ ∈ and {0, 1} of Hamming weightisN/2, 2 ′ 2 increasing in N . tr ′ Θ(Nthe loggraph N ), It depends only on N (not on (z, z )), and is strictly TN,µ (z, z ) is a tree. Its order is nµ (N ) = Θ(N log N ) + 2µ, with constants independent of µ. For fixed µ, this order depends only on N , not on (z, z ′ ), and is strictly increasing in N . Proof. Define the values m := N/2, BL := L(L + 1)/2, and let wt(i) denote the Hamming weight of the binary i. A m path b edges starting t contributes exactly b new vertices. Hence Proof. expansion Define the of values := of N/2, BL := L(L + at 1)/2, and let wt(i) denote the Hamming weight of the binary expansion of i. A path of b edges starting at t contributes exactly b new vertices. Hence |Tag(i)| = 2 + BL + 2wt(i). |Tag(i)| = 2 + BL + 2wt(i). One side contains its hub, m + 1 vertices ai , exactly m pendant leaves at those vertices, and one copyOne of every tag. Consequently, order side contains its hub, mthe + 1exact vertices ai , isexactly m pendant leaves at those vertices, and one " # copy of every tag. Consequently, the exact order is m X n(N ) = 2 1 +"m + (m + 1)(3 + BL ) + 2 wt(i) + ρ#− 1. m X nµ (N ) = 2 1 + m + (m + 1)(3 + BL )i=0 +2 wt(i) + ρ − 1. i=0

This depends only on N . Since L = Θ(log N ) and ρ = O(log N ), or ρ is fixed, it is Θ(N log2 N ). As increases, m, L, only BL , and the Hammingexpression weights are whileuniversal the Foreven fixedN µ, this depends on N . sum The ofbracketed is nondecreasing, Θ(N log2 N ) with m term strictlyand increases. When increases, adding leading zero bits does noton change theinweights constants, ρ−1 = 2µ. LThis gives the stated additive dependence µ, and particular 2 central-path term is nondecreasing for either length rule. Thus n(N ) is of the old indices. The nµ (N ) = Θ(N log N ) for fixed µ. strictly As increasing. even N increases, m, L, BL , and the sum of Hamming weights are nondecreasing, while the m term strictly increases. When L increases, adding leading zero bits does not change the weights of the old indices. (a) The central-path term is constant for fixed µ. Thus nµ (N ) is strictly increasing. to hL

(a) to hL

a3

s3 a3

t3 s3

t3

r3 leaves r3 leaves (b) hL a0

w1

w2

hR

a4

Figure 1: (a) tag Tag(3) for Lfor=L3 = (3 3=(3011 , with bits read from the least significant). The Figure 2: The (a) The tag Tag(3) =2011 2 , with bits read from the least significant). The paths starting at t have lengths 1, 2, 3; the first two end in two extraextra leaves. No other branch of of paths starting 3at t3 have lengths 1, 2, 3; the first two end in two leaves. No other branch tr an instance is isomorphic to a as taga (Lemma 25).to(b) The(Lemma instance25). T8 (z, z) The for zinstance = 01011010 and tr (z, an instance is isomorphic rooted tree a tag (b) T8,µ z) for r(z)z==(1, 1, 0, 1, 1). The central path has ρ = ⌈log 8⌉ = 3 edges. Each side has vertices a , . . . 4 01011010 and r(z) = (1, 1, 0, 1, 1). Here µ2= 1, so the central path has ρ = 2µ + 01 = 3, aedges. carrying leaves drawnthe as prescribed triangles. Each hub reconstructs all pairs (i, r̂i )Each Eachthe sideprescribed has vertices a0 , .and . . , atags, carrying leaves and tags, drawn as triangles. 4 of itshub sidereconstructs in one communication all pairs (i, r̂round. ) of its side in one communication round. i

28 35

tr Properties of TN,µ (z, z ′ ) and the class TreeEQµ tr (z, z ′ ) consist of a path of length ρ with many Tag graphs adjacent to Given that the trees TN,µ the endpoints, the verification of such structures and its connection with the original EQ2N problem relies on understanding how the Tag graphs encode the problem. For a vertex v of a tree T and a neighbor u of v, we refer to the branch of T at v containing u as the connected component of T − v containing u, rooted at u. Rooted isomorphism uses the notation ∼ =rt from Section 2.

Lemma 25. Let µ ≥ 1 and even N ≥ 8, let z, z ′ ∈ {0, 1}N have Hamming weight N/2, and denote tr (z, z ′ ). The following properties hold. T := TN,µ 1. For any i, j ∈ {0, . . . , N/2}, Tag(i) ∼ =rt Tag(j) if and only if i = j. 2. For every vertex v of T , every neighbor u of v, and every i ∈ {0, . . . , N/2}, the branch of T at v containing u is isomorphic as a rooted tree to Tag(i) if and only if v is an index-i vertex ai , on either side, and u is the root of the tag attached to v. Proof. For the first claim, consider the subtrees hanging below node t of any graph Tag(i). The subtree corresponding to arm b ∈ [L] consists of b vertices in a path, possibly with two extra leaves at its last vertex. Two such rooted subtrees are isomorphic exactly when they have the same length (i.e. the same arm index b) and the same structure at the end. Suppose first that there exists a rooted isomorphism between Tag(i) and Tag(j). Such an isomorphism maps the node t to its counterpart and matches the subtrees below these vertices. It therefore preserves every length path and its number of leaves. The bits of i and j agree, so i = j. The converse follows directly from the construction. For the second claim, note that the branch at ai containing its tag root is Tag(i) by construction. We show that no other branch is a tag. Define m := N/2 and BL := L(L + 1)/2. Since N ≥ 8, we have m ≥ 4 and L ≥ 3. Every tag has at most 2 + BL + 2L vertices. Moreover, every branch containing a hub or a central-path vertex contains at least m entire gadgets, and hence at least m(3 + BL ) vertices. This is larger than every tag, since m(3 + BL ) − (2 + BL + 2L) ≥ 10 + 3BL − 2L > 0. Thus such branches cannot be tags. The remaining branches are contained in a single gadget. Apart from the tag itself, they are exhausted by the following cases. • A branch at a hub containing ai . If ri ≥ 1, its root ai has at least two children, whereas a tag root has one. If ri = 0, its root has the single child si , but si has one child, whereas the child of a tag root has L ≥ 3 children. • A branch at ai containing one of its pendant leaves, or a branch at the last vertex of a tag arm containing one of its extra leaves. Such a branch is a singleton, whereas a tag root has a child. • A branch at the tag root containing ti . Its root has L ≥ 3 children, whereas a tag root has one. • A branch at ti containing the first vertex of an arm, or a branch at an arm vertex containing the next vertex. Such a branch is a path, possibly with two extra leaves at its end. Every vertex has at most two children, whereas a tag contains a vertex with L ≥ 3 children. 36

• An upward branch from a vertex inside the gadget. This contains ai and its hub, and is therefore excluded by the size argument above. This exhausts all branches of T . Now we prove the following characterization that links isomorphism between trees in TreeEQµ with our equality problem. Lemma 26. For every µ ≥ 1, even N, N̂ ≥ 8, strings z, z ′ ∈ {0, 1}N of Hamming weight N/2, and tr (z, z ′ ) ∼ T tr (ẑ, ẑ ′ ) if and only if strings ẑ, ẑ ′ ∈ {0, 1}N̂ of Hamming weight N̂ /2, it holds that TN,µ = N̂ ,µ N = N̂ and (z, z ′ ) = (ẑ, ẑ ′ )

or

(z, z ′ ) = (ẑ ′ , ẑ).

Proof. The parameters N and N̂ agree because the vertex count is strictly increasing in N , by Fact 1. Let φ be an isomorphism. By Lemma 25, having a branch isomorphic as a rooted tree to Tag(i) characterizes the two index-i vertices, one on each side. Hence φ maps each ai to an index-i vertex of the target. Distinct vertices ai , aj of the same side are at distance 2, whereas vertices on opposite sides are at distance ρ + 2 ≥ 5. After interchanging the left and right designations in the target, if necessary, assume that φ maps the left a0 to the left â0 . Every other left ai is at distance 2 from a0 , rather than ρ + 2 ≥ 5. Its image, already restricted to the target’s two index-i vertices, therefore also lies on the left. The vertex hL maps to the common neighbor of φ(a0 ) and φ(a1 ), namely the target’s hL . For each i, the tag root adjacent to ai maps to the tag root adjacent to φ(ai ), by Lemma 25: the graph isomorphism induces a rooted isomorphism on each corresponding branch. The remaining ri (z) neighbors of ai are its pendant leaves. Consequently, for every i.

ri (z) = ri (ẑ)

The run-length bijection gives z = ẑ. The same argument on the right gives z ′ = ẑ ′ . If the target’s side designations were interchanged, the conclusion is instead (z, z ′ ) = (ẑ ′ , ẑ). Conversely, either equality of ordered pairs gives an isomorphism directly, permuting interchangeable leaves and exchanging the two sides when necessary. Now, we finally define the property TreeEQµ . For any fixed positive integer µ ≥ 1, we define the graph property TreeEQµ as follows:  tr TreeEQµ := T : T ∼ (z, z) for some even N ≥ 8 and z of weight N/2 . = TN,µ tr Certifying the graphs TN,µ (z, z ′ ) tr (z, z ′ ), without checking We first give a deterministic one-round certification of the graphs TN,µ equality of the encoded strings. We formally analyze the more general property tr Treeµ := {T : T ∼ (z, z ′ ) for some even N ≥ 8, = TN,µ

z, z ′ ∈ {0, 1}N with wt(z) = wt(z ′ ) = N/2}. And we prove the following result. Lemma 27. The property Treeµ admits a deterministic one-round dMA protocol on connected nvertex graphs, using O(log n) certificate bits per node and bits per message. 37

Name

Auxiliary field

Required multiset of neighboring names

hL

none

One side-L vertex ai for each 0 ≤ i ≤ N̂ /2, and w1

hR

none

One side-R vertex ai for each 0 ≤ i ≤ N̂ /2, and wρ−1

wj , 1 ≤ j < ρ

none

wj−1 , wj+1 , interpreting w0 = hL , wρ = hR

ai on side σ

r̂iσ

hσ , si , and r̂iσ pendant leaves of ai

Pendant leaf of ai

none

Only ai

Tag root si

none

ai , ti

ti

none

si and the first vertex of each arm b ∈ [L̂]

Position p of arm b

none

Its predecessor (ti if p = 1); its successor if p < b; at p = b, two extra leaves if the b-th least significant bit of i is 1, and none otherwise

Extra leaf of arm b

none

Only position b of arm b; this role is valid only if the b-th least significant bit of i is 1

Table 2: Classical fields and local rules for Treeµ . Every gadget reference preserves the same side and index; arm predecessors, successors, and extra leaves also preserve the same arm index. If all nodes accept in Lemma 27, the certificates identify the left and right trees and their roots hL , hR , together with a valid parameter N̂ . During the same communication round, hL reconstructs ẑ from the run lengths reported by its neighbors, and hR reconstructs ẑ ′ in the same way. These strings have Hamming weight N̂ /2 and satisfy G∼ = TN̂tr,µ (ẑ, ẑ ′ ). tr (z, z ′ ) allows us to give a deterministic classical certification The local structure of each graph TN,µ for Treeµ , although a bit tedious given the different sub-parts that we need to verify. Nevertheless, the following certification follows a basic idea: We can give to each node its role in the tree, i.e., to which part it belongs, and certify its correctness through local rules.

Proof of Lemma 27. Fix the constant µ ≥ 1 and let ρ := 2µ + 1. By Definition 23, in any yes instance of Treeµ the central path connecting the left and right trees has constant length ρ and therefore it is fixed throughout the protocol, and does not depend on the input size. Certificates and local rules. Each node receives a claimed even integer 8 ≤ N̂ ≤ n, encoded in a fixed O(log n)-bit field, and a name from Table 2. It computes L̂ := ⌈log2 (N̂ /2 + 1)⌉. Every gadget name contains its side σ ∈ {L, R} and index i ∈ {0, . . . , N̂ /2}. Arm vertices and extra leaves additionally contain b ∈ [L̂], and an arm vertex also contains its position p ∈ [b]. Leaves sharing a parent and role have the same name. The only auxiliary field beyond these name coordinates is the run length r̂iσ ∈ {0, . . . , N̂ /2} at ai . Verification. Before communication, each node checks the local conditions in (V1), including nµ (N̂ ) = n, using the exact count in Fact 1. If no even N̂ ≥ 8 satisfies this equality, it rejects. Otherwise it broadcasts its certificate in one round and performs the remaining checks after reception: (V1) N̂ is even, 8 ≤ N̂ ≤ n, nµ (N̂ ) = n, and its name is valid, all fields required by that name are present, and all indices and run lengths are in their specified ranges. Every neighbor reports the same N̂ . 38

(V2) The multiset of its neighbors’ names equals the multiset required by its own certificate. (V3) If its name is hσ , the run lengths obtained from its neighbors named a0 , . . . , aN̂ /2 satisfy N̂ /2

X

r̂iσ = N̂ /2.

i=0

A node accepts if and only if all applicable verifications pass. tr (z, z ′ ) witnessing Completeness. Suppose G ∈ Treeµ . Choose an isomorphism from G to TN,µ this membership. The prover assigns every node the parameter N and the name of its image under this isomorphism. Each vertex named ai additionally receives the corresponding run length of z or z ′ . The neighboring names agree with the construction, and the run lengths on each side sum to N/2. Thus every node passes (V1)–(V3).

Soundness. The model tree has a unique name for every non-leaf vertex, and any repeated leaf name has a single parent. We use these names to build an injective homomorphism into G; exact degree matching and connectedness then force its image to be the whole graph, without needing global distance labels. Suppose all nodes accept on a connected graph G. By (V1) and the connectedness of G, all nodes report the same even integer N̂ ≥ 8. First, some node has name hL . Indeed, starting from any gadget vertex, the neighboring names required by (V2) give a finite sequence leading to its ai and then to its corresponding root. From a vertex named hR or wj , the required central-path neighbors give a sequence ending at a vertex named hL . Let u0 be such a vertex. Starting at u0 , follow the required neighboring names w1 , . . . , wρ−1 , hR , and denote the last vertex by uρ . These vertices are distinct because their names are distinct. By (V2), u0 has exactly one neighbor named ai of side L for each i ∈ {0, . . . , N̂ /2}. Likewise, uρ has exactly one neighbor named ai of side R for each such i. Let r̂iL and r̂iR be the run lengths reported by these neighbors. By (V3), they define strings L

L

r̂L

R

R

r̂R

ẑ = 0r̂0 1 0r̂1 1 · · · 1 0 N̂ /2 , ẑ ′ = 0r̂0 1 0r̂1 1 · · · 1 0 N̂ /2 . Each string has exactly N̂ /2 zeros and N̂ /2 ones, so both belong to {0, 1}N̂ and have Hamming weight N̂ /2. Define T := TN̂tr,µ (ẑ, ẑ ′ ), rooted at hL . We construct an injective map ψ : V (T ) → V (G) that preserves names and edges. Set ψ(hL ) := u0 , and proceed by increasing distance from hL in T. Suppose ψ(x) has been defined. For every child y of x whose name occurs only once in T , define ψ(y) to be the neighbor of ψ(x) with that name. For a group of children sharing a leaf name, match these children bijectively with the neighbors of ψ(x) carrying that name. The required neighbors exist, with exactly the required multiplicities, by (V2). In particular, the central path maps to the path chosen above, and the vertices named ai map to the neighbors of u0 and uρ from which the run lengths were read. Their claimed run lengths therefore agree with those used to construct T . Every non-leaf name occurs only once in T . At uρ = ψ(hR ), the neighbor named wρ−1 required by (V2) is necessarily the already visited vertex ψ(wρ−1 ): it is adjacent to uρ , and (V2) requires 39

exactly one neighbor with that name. Thus expanding hR introduces only its gadget children and does not create a second copy of the central path. This construction is injective. Vertices with different names have different images. The only names shared by several vertices of T are leaf names, and all leaves with one such name have a common parent; their images are distinct by the chosen bijection. Since every nonroot vertex of T has a unique parent, the construction defines ψ on all of V (T ). Every edge of T maps to an edge of G. Moreover, by (V2), for every x ∈ V (T ), degG (ψ(x)) = degT (x). By injectivity, the images of the neighbors of x already account for all neighbors of ψ(x). Consequently, no additional edge is incident to any vertex in the image of ψ. In particular, no vertex outside the image is adjacent to a vertex inside it. The image is nonempty and G is connected, so the image is all of G. Thus ψ is an isomorphism, and G ∼ = TN̂tr,µ (ẑ, ẑ ′ ). Therefore G ∈ Treeµ , proving soundness. The reconstruction above uses only the certificates received by the two roots during the communication round. Hence the roots reconstruct ẑ and ẑ ′ by the end of that same round. By Lemma 26, their unordered pair is determined by the isomorphism type of G. Complexity. Each certificate contains a constant number of fields encoding the parameter, the name, and, when applicable, a run length. The fixed field bounds N̂ ≤ n, all name ranges in Table 2, and ρ < n on any size passing (V1) give O(log n) bits per node and per message on every instance, including no-instances. Larger or malformed encodings are rejected before communication.

4.2

Quantum advantage for TreeEQµ

We prove Theorem 1 by combining the quantum upper bound of Lemma 28 with the classical lower bound of Theorem 29. Lemma 28. For every fixed integer µ ≥ 1, the property TreeEQµ admits a one-round dQMA protocol on connected n-vertex graphs with perfect completeness, soundness error at most 1/3, and O(µ log n) certificate qubits per node and qubits per individual message. The implicit constant is independent of µ; for fixed µ this is O(log n). Proof. Fix µ ≥ 1 and let ρ := 2µ + 1. We combine the structural certification of Lemma 27 with the path equality protocol of Theorem 5, applied to the central path of ρ edges. The key point that allows this combination in one round is that the equality protocol needs the endpoint strings only for its final local tests. All operations performed before receiving the messages are independent of those strings. Certificates The prover supplies each node with the classical certificate of Lemma 27. The nodes named hL , w1 , . . . , wρ−1 , hR in this protocol also receive the quantum registers prescribed by the equality protocol of Theorem 5, using the claimed string length N̂ and path length ρ fixed in Lemma 27. Use mρ := ⌈70(ρ + 1) ln 3⌉ repetitions of Protocol 1. Because local (V1) checks uniquely determine N̂ from known n and µ, register dimensions are bounded before any quantum operation. Pad fingerprints to a common width ℓ(n) = O(log n), large enough for every N ≤ n, and reserve at most 2mρ ℓ(n) quantum certificate qubits at each node. Its measured role selects the prescribed blocks within this fixed budget (one block per repetition at hR , two at each other central-path node); unused padding is ignored. These budgets do not depend on the validity of the instance. Each node named hL or wj additionally receives the port leading to its claimed successor on the path hL , w1 , . . . , wρ−1 , hR . This port number uses O(log n) bits and allows the node to send its quantum registers before learning its neighbors’ names. 40

Verification Before communication, every node measures the classical part of its certificate in the computational basis. It first checks the local part of (V1), its successor port when applicable, and that the active register format has exactly the number and widths of blocks prescribed for its measured role. If a check fails, it records rejection and applies no dimension-dependent quantum operation. Well-formed nodes proceed with their locally prescribed blocks; rejecting nodes may send dummy quantum messages. During the communication round, every node sends its measured classical certificate, including its successor port when applicable, to each neighbor. At the same time, the nodes named hL or wj perform the random swaps prescribed by the equality protocol (Protocol 1) and send their quantum registers through their claimed successor ports. These operations require neither ẑ nor ẑ ′ . After receiving the messages, every node performs checks (V1)–(V3) from the structural certification from Lemma 27. Every node records the local port on which each incoming classical and quantum message arrives. Each sender checks that the classical certificate received on its designated successor port carries the required successor name. Each receiver in {w1 , . . . , wρ−1 , hR } identifies the unique port carrying its predecessor’s classical certificate, checks that the expected quantum registers arrived on that same port, and uses those registers in its quantum test. Before applying a SWAP or endpoint test, each receiver also checks that the incoming quantum block count and widths agree with mρ and ℓ(n). A failed classical, routing, or dimension check causes rejection without applying that test. If all these verifications pass, the structural certification identifies a single central path, and the quantum registers have been transmitted along that path as required by the equality protocol. The roots hL and hR can now reconstruct their respective strings. Indeed, hL receives exactly one pair (i, r̂iL ) for each i ∈ {0, . . . , N̂ /2}, and reconstructs L

L

r̂L

ẑ = 0r̂0 1 0r̂1 1 · · · 1 0 N̂ /2 . The root hR reconstructs ẑ ′ in the same way. The structural verification ensures that these run lengths agree with the actual gadgets. Although each root receives many classical messages, every individual message has only O(log n) bits, and local computation and storage are unrestricted. The path vertices then complete the local tests of the equality protocol, using |hẑ ⟩ and |hẑ ′ ⟩ for the projection of the endpoints. Therefore, the roots learn their strings before computing the only tests that depend on them. Every node accepts if and only if all its structural, routing, and quantum checks accept. tr (z, z). The prover Completeness. Suppose G ∈ TreeEQµ , and choose an isomorphism G ∼ = TN,µ supplies the corresponding structural certificates and successor ports, together with the honest quantum certificates for equality of z with itself. All structural and routing checks pass. The roots reconstruct z, and perfect completeness of the equality protocol ensures that every quantum test accepts with certainty.

Soundness. Suppose G ∈ / TreeEQµ , and consider any joint quantum certificate supplied by the prover. Condition on the outcomes of all initial measurements of the classical certificate parts. For these fixed outcomes, the structural and routing checks are deterministic. If any of them fails, some node rejects with certainty. Otherwise, Lemma 27 gives G∼ = TN̂tr,µ (ẑ, ẑ ′ ), where ẑ and ẑ ′ are the strings reconstructed by the two roots. These strings must be distinct: if they were equal, this isomorphism would imply G ∈ TreeEQµ . 41

Conditioned on the classical outcomes, the quantum registers on the central path may still be in an arbitrary joint state, including a state entangled across nodes and repetitions. The soundness guarantee of Theorem 5 applies to every such state. Since the routing checks ensure that the registers follow the prescribed path, the probability that all quantum tests accept is at most 1/3. Averaging over the classical measurement outcomes proves the same bound for the original certificate. Complexity. The structural certificates and successor ports use O(log n) classical bits per node. The equality protocol uses O(ρ) repetitions, with padded O(log n)-qubit registers, giving O(ρ log n) certificate qubits in the fixed budget and qubits per path-edge message. Only the central-path quantum slots are used; the remaining active fields and messages are classical. Since ρ = 2µ + 1, the maximum certificate size, including padding, and individual message size are O(log n + ρ log n) = O(µ log n), with a universal implicit constant. Now we prove the classical lower bound of Theorem 1. Theorem 29. For every fixed integer µ ≥ 1, any µ-round dMA protocol for TreeEQµ with completeness c and soundness error s such that 2c − 1 > s has worst-case certificate size Ω(n/(µ log2 n)) bits. The implicit constant is independent of µ. Proof. Fix µ ≥ 1 and a µ-round dMA protocol Π for TreeEQµ , with completeness c and soundness error s satisfying 2c − 1 > s. Recall that the central path has length ρ = 2µ + 1. We follow the fooling-set argument of Fraigniaud et al. [FLNP21, Theorem 9]. tr (z, z ′ ) encoding N -bit strings z and z ′ with Fix an even integer N ≥ 8. By Fact 1, all trees TN,µ Hamming weight N/2 have the same number n of vertices, regardless of the strings z and z ′ . Let b := b(n) be the worst-case certificate size of Π on n-vertex instances. tr (z, z) and T tr (t, t) into a new In this argument, the main idea is to “combine” two instances TN,µ N,µ tr (z, t), taking the left tree from the first instance and the right tree from the second. In instance TN,µ order to apply the argument, we need to choose identifiers and ports consistently so that, when the certificates are combined as described below, the nodes in each tree retain their µ-round views from the corresponding original instance. Agreement of the certificates on the central path will ensure that the appropriate views are also preserved at the internal path vertices. tr (z, z ′ ), both the We therefore assign the identifiers and ports as follows. Given an instance TN,µ left and right trees have the same number of vertices for every string (with Hamming weight N/2): its tags are fixed, and the total number of pendant leaves encoding the string is N/2. We can therefore reserve disjoint identifier intervals for the two sides and the internal path vertices, using O(n) identifiers in total as follows: First, we can keep the identifiers of hL , hR and all wj fixed. Second, within each side, enumerate the vertices other than its root in a fixed order determined by the encoded string,3 and assign them the remaining identifiers from the interval reserved for that side in increasing order. Third, choose the internal port numbering of each side in the same way, and keep the ports along the central path, including its attachments to hL and hR , fixed. Consequently, whenever the same string occurs on the same side of two instances, that side has identical identifiers and ports. All common parameters, including n, are also unchanged. 3 Order the gadgets by increasing i. Within each gadget, list ai , its pendant leaves, si , ti , and then the tag arms by increasing b. List the vertices of each arm by increasing p, followed by its extra leaves, if any. Leaves sharing a parent may be listed in any order, since they have identical neighborhoods.

42

For each balanced string z ∈ {0, 1}N , denote by Γz a certificate assignment under which all nodes tr (z, z) accept with probability at least c in Π. Such an assignment exists by completeness. of TN,µ The following claim states that different balanced strings cannot produce the same certificates in the nodes of the central path. Recall that by construction, the central path has the same length (for a fixed µ) and the identifiers and ports are the same. Claim C. Let z, t ∈ {0, 1}N be two different balanced strings. Then

Γz (w1 ), . . . , Γz (w2µ ) ̸= Γt (w1 ), . . . , Γt (w2µ ) , tr (z, z) and T tr (t, t). where w1 , . . . , w2µ are the nodes of the central path of both TN,µ N,µ

Proof of Claim C. Suppose that two distinct strings z, t give the same tuple in the central path. tr (z, t), which is a no-instance by Lemma 26. Partition its vertices into a left group Consider TN,µ consisting of the entire left side and w1 , . . . , wµ , and a right group consisting of all remaining vertices. Give the left group its certificates from Γz and the right group its certificates from Γt . On w1 , . . . , w2µ , the two assignments agree by assumption. Every vertex of the left group has the same radius-µ neighborhood, including identifiers, ports, tr (z, z) with Γ . Indeed, the right root is at distance at least ρ − µ = µ + 1 and certificates, as in TN,µ z from this group. Any internal path vertex visible across the cut has index at most 2µ, so its certificate belongs to the common tuple. tr (t, t) Similarly, every vertex of the right group has the same radius-µ neighborhood as in TN,µ with Γt . The left root is at distance at least µ + 1 from this group, and every certificate visible across the cut belongs to the common block. The side structures and their identifiers and ports agree by construction. Couple the mixed execution and the two diagonal executions using the same public random tape and the same private tape at each corresponding identifier. Each individual execution still has the prescribed distribution of public and private randomness. Since information crosses at most one edge per round, the matching neighborhoods imply matching decisions after µ rounds. The probability that all vertices of the left group accept in the mixed execution is therefore at least c: whenever all vertices accept in the first diagonal execution, this group accepts as well. The same reasoning applies to the right group using the second diagonal execution. Without assuming independence between these events,   tr Pr all vertices accept on TN,µ (z, t) ≥ 1 − (1 − c) − (1 − c) = 2c − 1 > s. This contradicts soundness and proves that the tuples are distinct. There are

N N/2

balanced strings, and a binary certificate of length at most b has b X

2i = 2b+1 − 1

i=0

possible values, including the empty string. Thus the injectivity proved in Claim C gives   N ≤ (2b+1 − 1)2µ < 22µ(b+1) , N/2 and hence

  1 N b> log2 − 1. 2µ N/2 43

The central binomial coefficient is the largest term in the binomial expansion of 2N , so 2

N

=

N   X N i=0

Consequently, b>

i



 N ≤ (N + 1) . N/2

N − log2 (N + 1) − 1. 2µ

Since µ is fixed, this gives b = Ω(N/µ) as N grows. Finally, Fact 1 gives n = Θ(N log2 N ), and therefore log n = Θ(log N ) and N = Θ(n/ log2 n). It follows that   n . b := b(n) = Ω µ log2 n The implicit constants are universal: the only requirement for absorbing the additive term in the counting bound is N/µ → ∞. Growing round budgets. The same construction and estimates apply uniformly to growing known µ along the constructed instance sizes. Indeed, n = nµ (N ) = Θ(N log2 N ) + 2µ. If µ = o(n/ log2 n), then 2µ = o(n), N = Θ(n/ log2 n), and µ = o(N ). The counting bound still gives Ω(n/(µ log2 n)) bits, while the quantum budget remains O(µ log n) qubits. Thus these cost bounds extend to this range of parameterized instances.

5

Graph Symmetry

Our second separation concerns graph symmetry, the existence of a nontrivial automorphism. Let SYM be the class of connected graphs having such an automorphism. For a known integer D ≥ 1, we also consider the restricted symmetry class SYMD := {G ∈ SYM : rad(G) ≤ D}. As usual in local certification, we assume that the input graph is connected, but the radius condition is part of the property being certified for SYMD . We use in our argument two implications of the condition rad(G) ≤ D: Every instance of SYMD has diameter at most 2D and a vertex of eccentricity at most D. The quantum protocols certify a proposed automorphism by comparing strings that describe the neighborhoods of vertices and their proposed images. We use the distance-independent equality protocol for SYM, and the fingerprint protocol for SYMD , where the comparisons can follow short paths. For the classical lower bounds, we construct a family in which a nontrivial automorphism exists exactly when two attached graphs are isomorphic. The reduction runs one comparison of N∗ = Θ(n log n) bits for each vertex, along a simple path of length at most n − 1. Up to n such paths can cross one vertex or edge. Applying the O(r log N∗ ) e 2 ) worst-case bound under this fingerprint cost to paths with r = Θ(n) therefore gives only a O(n congestion. The relay-based approach of [HKN24] likewise retains a linear-in-N∗ certificate bound at relay vertices and does not give a subquadratic guarantee from this composition. e ∗2/3 ) qubits at every path vertex, independently of the path length. Protocol 2 instead uses O(N e 5/3 ). For radius at most D, comparison paths can have Multiplying by the congestion gives O(n length at most 2D, and Protocol 1 gives O(D log n) per path and O(nD log n) in total. 44

Both compositions fit in one round because all pre-communication quantum operations and outgoing registers are independent of the endpoint strings. Classical headers and quantum registers can be sent together; the endpoints construct their neighborhood strings upon reception and only then perform the input-dependent tests. We use this property explicitly below.

Classical certificates and local verifications We first describe the classical part of our protocols. Its purpose is to certify the paths along which the equality protocols will run and to construct the strings compared at their endpoints. The difference between the protocol for SYM and SYMD is minimal, since for the latter we only need to give a few extra certificates, and the radius condition will imply the improved complexity; therefore, we present both protocols, proving Theorem 2 and Corollary 3 together. Fix a connected n-vertex graph G, with n ≥ 2, and denote by U the known identifier range, where U = nO(1) . We use the known n and U convention from Section 2.1, so all string lengths and quantum register budgets below are determined before communication. If n is not provided, the classical scaffold can certify it by adding a common claimed order and subtree-size fields to (L2): neighbors agree on the claim, each vertex checks one plus the sizes of children pointing to it, and the root checks that its size equals the common claim. These are O(log n)-bit fields on an accepting assignment. We analyze the quantum upper bounds with n and U known, as stated in the model. Define also for every n-node graph G the function ( n − 1, for SYM, h(G) := min{2D, n − 1}, for SYMD . The following lemma states the guarantees of the classical verification. Once these classical verifications pass, verifying the remaining string equalities using our quantum protocol from Theorem 5 will certify a nontrivial automorphism. Lemma 30. There is a deterministic one-round dMA protocol using O(n log n) certificate bits per node with the following guarantees. If all nodes accept, the certificates define functions π, σ : V (G) → [U ], a spanning tree rooted at a vertex v ∗ satisfying π(v ∗ ) ̸= id(v ∗ ), and exactly one simple path Pv starting at each vertex v, of length at most h, and at most n paths pass through any vertex. For SYMD , acceptance also guarantees rad(G) ≤ D. By the end of the verification round, every vertex v constructs strings Xv , Yv of length O(n log n) with the following properties: 1. If all nodes accept and Xv = Yτ (v) for every v, where τ (v) is the endpoint of Pv , then τ is a nontrivial automorphism of G. 2. If G ∈ SYM, or G ∈ SYMD for the bounded-radius version, there is a certificate assignment under which all nodes accept and all these equalities hold. Proof. We describe the certificates and their verification first. Certificates Each node v receives the following classical data. (L1) For SYMD only, the certificate contains a root identifier rtℓ and a label ℓ(v) ∈ {0, . . . , min{D, n − 1}}. 45

(L2) The certificate contains a root identifier rt, a depth d(v) ∈ {0, . . . , n − 1}, and a parent port, or ⊥ at depth zero.4 (L3) The certificate contains two identifier values π(v), σ(v) ∈ [U ], intended to identify the images of v under an automorphism and its inverse. (L4) The certificate contains at most n path records, with at most one record for each path identifier c ∈ [U ]. A record has the form (c, t, j, pred, succ),

0 ≤ j ≤ t ≤ h.

Here t is the claimed path length and j is the node’s position. Each predecessor or successor field is either ⊥ or a pair consisting of a local port and a claimed neighbor identifier. A record has pred = ⊥ if and only if j = 0, and succ = ⊥ if and only if j = t. A position-zero record must have c = id(v), and every node must have such a record for its own identifier. All fields use O(log n) bits. Malformed certificates are rejected. Verification Every node sends its certificate and identifier to each neighbor. Each message also specifies the local port through which it is sent, allowing reciprocal port pointers to be checked after reception. The nodes perform the following verifications. (L1) For SYMD , neighboring nodes must report the same rtℓ . Each node checks that ℓ(v) = 0 if and only if id(v) = rtℓ , and that a node with positive label has a neighbor whose label is one smaller. (L2) Neighboring nodes must report the same rt. Each node checks that d(v) = 0 if and only if id(v) = rt. At depth zero its parent must be ⊥; otherwise, its parent port must lead to a neighbor of depth d(v) − 1. The depth-zero node additionally checks π(v) ̸= id(v). (L3) Each node checks that π(v) and σ(v) lie in [U ]. (L4) Every predecessor or successor port must lead to the neighbor with the claimed true identifier. A successor must hold a record with the same c, t, position j + 1, and a predecessor pointer back to the current node. A predecessor must similarly hold the record at position j − 1 with a successor pointer back. The exchanged port numbers allow these pointers to be checked against the actual edge used. Each node accepts if and only if all the above verifications hold. After the reception of the certificates, the nodes also construct the strings that will be compared by the quantum protocol. Set ℓ∗ := ⌈log2 (U + n + 2)⌉,

N∗ := (n + 2)ℓ∗ ∈ O(n log n).

Use ℓ∗ bits for each integer field. To encode two identifiers, a degree, and a neighbor list, sort the list and pad it with zeros to n − 1 entries. Including the degree makes this encoding unambiguous. Define
Xv := enc id(v), π(v), deg(v), (π(u))u∈N (v) ,
Yv := enc σ(v), id(v), deg(v), (id(u))u∈N (v) . The lists are treated as multisets and sorted as above. Every string has length N∗ . Each node knows its own certificate and degree, and receives its neighbors’ claimed images and true identifiers during the round. It can therefore construct both strings by the end of that round. 4

This is a standard spanning-tree certification scheme (see, e.g., [KKP10]). We include its short description and verification for completeness.

46

Completeness. Suppose G belongs to the property under consideration, and choose a nontrivial automorphism α. Choose a vertex v ∗ moved by α, supply correct spanning-tree data rooted there, and set π(v) := id(α(v)), σ(v) := id(α−1 (v)). For each v, choose a shortest path from v to α(v) and supply its records and ports. These paths are simple and have length at most n − 1. For SYMD , additionally choose a vertex of eccentricity at most D and provide its true distance labels for (L1). The diameter is then at most 2D, so every chosen shortest path has length at most min{2D, n − 1} = h. All classical checks pass. Moreover, τ (v) = α(v). The inverse identities and preservation of degrees and neighborhoods give Xv = Yα(v) = Yτ (v)

for every v.

Soundness. Suppose all nodes accept. For SYMD , connectedness and (L1) make rtℓ common to all nodes. A node of minimum label must have label zero, since otherwise it would need a neighbor with smaller label. Distinct identifiers make this node unique. Following decreasing labels reaches it from every node within D steps. Thus rad(G) ≤ D. The same argument for (L2) gives a unique depth-zero vertex v ∗ . The spanning-tree construction is standard and known to correctly construct a spanning tree if all the verification holds [KKP10]. The pointers, therefore, form a spanning tree. The root check gives π(v ∗ ) ̸= id(v ∗ ). We next show that the certificates describe simple paths. Start at a vertex v with position zero in its certificate and follow the successor pointers. The checks ensure that successive vertices report the same path length t, while their positions increase by one. At position t, the successor is ⊥, so the path ends. A vertex cannot appear twice, since its certificate would then have to specify two different positions on the same path, which is not allowed. Thus, this is a simple path of length t ≤ h. Conversely, consider any vertex with a certificate for a path with identifier c, and follow the predecessor pointers. Positions decrease by one until reaching position zero. The vertex at this position must have identifier c, so the starting vertex is unique. The predecessor and successor pointers agree at every step, so following successors from this starting vertex leads back to the original vertex. Thus, every certificate for c describes a position on this same path. Since each certificate specifies at most one successor, the path cannot branch. There is exactly one path for each starting vertex, so at most n paths pass through any vertex or edge. Finally, suppose that Xv = Yτ (v) for every v. The first fields give σ(τ (v)) = id(v). If τ (v) = τ (u), these equalities imply id(v) = id(u), and hence v = u. Thus τ is injective and, since V (G) is finite, bijective. The second fields give π(v) = id(τ (v)). Equality of the degrees and neighbor lists gives {π(u) : u ∈ N (v)} = {id(z) : z ∈ N (τ (v))} as multisets. Substituting the second-field equalities and using distinct identifiers yields τ (N (v)) = N (τ (v)) 47

for every v.

By injectivity, u ∈ N (v) if and only if τ (u) ∈ N (τ (v)). Therefore τ is an automorphism. Furthermore, id(τ (v ∗ )) = π(v ∗ ) ̸= id(v ∗ ), so it is nontrivial. Complexity. Each path record contains a constant number of O(log n)-bit fields, and each node holds at most n records. The remaining certificate fields use O(log n) bits. Thus the certificate size is O(n log n) bits per node. Every node sends these data, its true identifier, and the sending port to each neighbor. Each individual message therefore has O(n log n) bits. The strings are constructed locally after reception and require no additional communication.

5.1

Quantum upper bounds for symmetry

We prove Theorem 2, which we re-state below. Theorem 2 (Quantum advantage for graph symmetry). The graph symmetry problem SYM admits a one-round dQMA protocol with perfect completeness, soundness error 1/3, and certificates with O(n5/3 (log n)7/3 ) qubits per node. Proof. We combine the classical certification above with one equality protocol along each certified path. As in the protocol for TreeEQµ , the endpoint strings are learned during the communication round, before the final tests that depend on them. Certificates The prover supplies each node with the classical certificate fields (L2)–(L4) from Lemma 30. For each positive-length path through a node, it also supplies separate quantum registers for comparing Xv at the starting vertex v with Yτ (v) at the endpoint. These are the registers of the distance-independent equality protocol of Protocol 2. Each execution uses the K label-register pairs of Protocol 2, with K and L determined solely by the known input length N∗ . Each node reserves n path slots, each of 2K⌈log L⌉ qubits, and its at most n measured records select distinct active slots. Unused slots and the slots of length-zero paths are 2/3 ignored. This gives a fixed O(nN∗ (log(N∗ + 2))5/3 )-qubit budget even on no-instances. A local record (c, t, j, pred, succ) determines whether the node acts as the starting vertex (j = 0), an internal vertex (0 < j < t), or the endpoint (j = t), and determines the outgoing port. It does not determine a repetition count in this protocol. Verification Before communication, every node measures the classical part of its certificate in the computational basis. It checks every record’s local ranges and ports and its prescribed quantum register format before any pre-communication quantum operation. A malformed record or an incompatible block count or width causes rejection, and no dimension-dependent operation is applied to that slot. Valid slots execute strictly according to their own measured records, before neighboring records are known. In the single communication round, it sends its measured classical data and true identifier to every neighbor, including the sending port as described above. At the same time, it performs the operations prescribed before communication by each equality execution and sends the designated quantum registers through that path’s successor port. These operations are independent of Xv and Yτ (v) . Registers and random coins for different paths are separate, and no quantum register is copied. A node that records a quantum rejection still carries out the remaining prescribed operations and communication, and rejects at the end. 48

After reception, every node performs verification checks (L2)–(L4). In particular, (L4) deterministically detects any discrepancy between adjacent records in the path identifier, length, positions, or predecessor/successor data. It also checks that the quantum registers prescribed for each path arrived through its predecessor port, with the required sizes and path identifiers. A failed structural, routing, or register-dimension check causes rejection without applying the affected final quantum test. If all such checks pass, Lemma 30 identifies the paths, and the quantum registers have followed them as required. The nodes now construct their strings from the received classical data. On each positive-length path, the endpoints perform the remaining input-dependent tests with Xv and Yτ (v) , and the internal vertices complete their local tests. On a length-zero path, its sole vertex checks Xv = Yv directly. Each node accepts if and only if all its classical, routing, and quantum checks accept. All operations fit in one communication round. Completeness. Suppose G ∈ SYM, and choose a nontrivial automorphism α. Choose a vertex v ∗ moved by α, supply correct spanning-tree data rooted there, and set σ(v) := id(α−1 (v)).

π(v) := id(α(v)),

For each v, choose a shortest path from v to α(v) and supply its correct certificates and ports. Its length is at most n−1. All classical checks pass, and the automorphism identities give Xv = Yα(v) for every v. Honest quantum certificates make every positive-length comparison accept with certainty by perfect completeness of the equality protocol. Length-zero comparisons also accept. Soundness. Consider a no-instance of SYM and any joint quantum certificate. Condition on all outcomes of the initial measurements of the classical parts. For these fixed outcomes, the classical and routing checks are deterministic. If any fails, some node rejects with certainty. Otherwise, the certified paths and τ are well defined by Lemma 30. Since G is asymmetric, the same lemma implies that some vertex v satisfies Xv ̸= Yτ (v) . If this path has length zero, its local comparison rejects with certainty. Otherwise, consider the registers and tests assigned to this path. Conditioned on the classical outcomes, their initial reduced state is arbitrary: it may be mixed and entangled across nodes and repetitions, and with the registers of other paths. The equality protocol’s soundness guarantee applies to every such state, so the probability that all tests on this path accept is at most 1/3. The prescribed operations on other paths act on separate registers and do not control the operations on this path. Ignoring their outcomes therefore leaves exactly the marginal execution just analyzed. Since acceptance of the network requires this path to accept, the network accepts with probability at most 1/3. Averaging over the initial classical outcomes gives the same bound for the original certificate. Complexity. Each node receives O(log n) certificate bits for each of the at most n paths passing through it. The remaining classical data use O(log n) bits per node. Thus, each classical certificate and each individual classical message have size O(n log n) bits. The equality protocol uses     2/3 O N∗ (log(N∗ + 2))5/3 = O n2/3 (log n)7/3 certificate qubits at each vertex of a path and qubits per message on each of its edges. By Lemma 30, at most n paths pass through any vertex or edge. Including the classical certificates e 5/3 ) certificate qubits per node and qubits per message. gives O(n5/3 (log n)7/3 ) = O(n 49

We next consider SYMD , where the graph is also required to have radius at most D. The classical certification of Lemma 30 verifies this bound and limits the comparison paths to length at most 2D. We can therefore use the O (r log N )-qubit equality protocol of Theorem 5 along these paths, obtaining the following improved upper bound. Corollary 3. For every known integer D ≥ 1, the property SYMD admits a one-round dQMA protocol with perfect completeness, soundness error 1/3, and O(nD log n) certificate qubits per node. Proof. We use the construction of Theorem 2, including the radius certificate fields and verification checks (L1) from Lemma 30, and requiring all certified paths to have length at most h = min{2D, n− 1}. On each positive-length path, we replace the distance-independent protocol by the O (r log N )qubit equality protocol of Theorem 5. All positive-length paths use the common repetition count mh := ⌈70(h + 1) ln 3⌉, which is at least the count required for any 1 ≤ t ≤ h. Fix a common fingerprint width ℓfp = O(log(N∗ + 2)) = O(log n). A node reserves n slots of at most 2mh ℓfp qubits each, with fingerprints padded to this width. Its local measured record fixes its role and successor port; terminal roles use only one block per repetition and ignore padding. Before communication it validates the local record and block format, then performs only the operations prescribed by that record. After communication, verification check (L4) confirms agreement of the records, and incoming widths and block counts are checked before any SWAP test. A failure causes rejection without an incompatible quantum operation. Thus inconsistent claims cannot invalidate the pre-communication schedule or increase its register budget. Its operations before receiving messages do not depend on the endpoint strings, so the same scheduling argument applies: the endpoints construct their strings during the communication round and then perform the tests that depend on them. Length-zero paths are checked directly as before. Completeness. Suppose G ∈ SYMD . Choose a nontrivial automorphism and the corresponding classical certificates as in Lemma 30, using true distance labels from a center for (L1). Since every vertex is within distance D of this center, any two vertices are at distance at most 2D. Thus the shortest paths to the automorphism images have length at most h. All classical verifications pass, and all endpoint strings agree. Perfect completeness of the fingerprint equality protocol therefore makes every node accept with certainty. Soundness. Condition on the initial measurements of the classical certificates, as in the proof of Theorem 2. If a classical or routing check fails, some node rejects with certainty. Otherwise, Lemma 30 guarantees rad(G) ≤ D. A no-instance must therefore be asymmetric, and the same lemma gives a path with unequal endpoint strings. A length-zero comparison rejects directly. For a positive-length path, Theorem 5 bounds its acceptance probability by 1/3. The argument of Theorem 2 applies also here, including when certificates are entangled across paths. Averaging over the classical outcomes gives soundness error at most 1/3. Complexity. The classical certificates and individual classical messages use O(n log n) bits by Lemma 30. The common count mh = O(h) gives O(h log(N∗ + 2)) = O(D log n) certificate qubits per reserved path slot and qubits per path-edge message, and at most n paths pass through any vertex. Including the classical certificates therefore gives O(nD log n) certificate qubits per node and qubits per individual message, including the unused-slot padding. 50

5.2

A hard family for symmetry

We use one family to prove both classical lower bounds of Theorem 4. The instances will be graphs denoted as Bρ (H, H ′ ), consisting of two asymmetric graphs H and H ′ joined by a central path of length ρ. Technically, the two graphs will have a minimum degree at least 3, so an automorphism must preserve the degree-2 internal vertices of the central path. This will ensure that a nontrivial automorphism exists exactly when the two attached graphs agree, and we will apply a fooling-set argument. Before describing the lower bound argument, we define these graphs formally and state some useful properties. Given a positive integer k, consider the isomorphism classes of connected asymmetric graphs on k vertices with diameter at most 2 and minimum degree at least 3. Let Fk denote a family containing exactly one representative from each of these classes. For each H ∈ Fk , fix an ordering of V (H) and let aH denote its first vertex. The following Fact holds. Fact 2. As k → ∞, we have log2 |Fk | ≥ (1 − o(1))k 2 /2. Proof. Let G ∼ G(k, 1/2) be an Erdős–Rényi random graph, i.e., its vertex set is {1, . . . , k} and each possible edge is present independently with probability 1/2. We first show that, with probability 1 − o(1) as k → ∞, G is isomorphic to a graph in Fk , and then use this estimate to count the corresponding isomorphism classes. We begin with connectivity and diameter. For two distinct vertices u, v, each other vertex ω ̸= u, v is adjacent to both with probability 1/4, independently of the others. The probability that u, v have no common neighbor is therefore (3/4)k−2 . By a union
bound, the probability that there exists a pair of vertices with no common neighbor is at most k2 (3/4)k−2 = o(1). Otherwise, every pair is joined by a path of length at most 2, so G is connected and has diameter at most 2. For the minimum-degree condition, a fixed vertex has degree less than 3 exactly when 0, 1, or 2 of its k − 1 possible incident edges are present. Counting these choices and applying a union bound over the vertices gives    k−1 −(k−1) 1 + (k − 1) + = o(1). Pr[some vertex has degree less than 3] ≤ k 2 2 Finally, G is asymmetric with probability 1 − o(1) by [ER63]. Combining these three conditions, another union bound shows that all the required properties hold simultaneously with probability 1 − o(1). Thus, with this probability, G is isomorphic to a member of Fk . k To turn this probability estimate into a count, observe that all 2(2) labeled graphs on {1, . . . , k} k are equally likely. Hence at least (1 − o(1))2(2) of them satisfy the requirements. Each isomorphism class contains at most k! such graphs, since there are only k! ways to assign the vertex labels. Dividing by this number gives a lower bound on |Fk |. Taking logarithms and using log2 (k!) ≤ k log2 k = o(k 2 ), we obtain   k k2 log2 |Fk | ≥ − log2 (k!) + log2 (1 − o(1)) = (1 − o(1)) . 2 2

Definition 31. Given H, H ′ ∈ Fk and ρ ≥ 3, the graph Bρ (H, H ′ ) consists of disjoint copies of H and H ′ whose distinguished vertices are joined by the central path aH , p1 , · · · , pρ−1 , aH ′ of ρ edges. Its number of vertices is n = 2k + ρ − 1. 51

We can characterize when each graph Bρ (H, H ′ ) belongs to SYM. Lemma 32. For H, H ′ ∈ Fk and ρ ≥ 3, the graph Bρ (H, H ′ ) has a nontrivial automorphism if and only if there is an isomorphism H → H ′ mapping aH to aH ′ . In particular, Bρ (H, H ′ ) ∈ SYM if and only if H = H ′ . Proof. A rooted isomorphism extends to a nontrivial automorphism by applying the isomorphism and its inverse on the two copies and reversing the central path. Conversely, let φ be an automorphism of Bρ (H, H ′ ). Its degree-2 vertices are exactly p1 , . . . , pρ−1 , since every vertex of either copy has degree at least 3. Thus φ preserves this set. Its induced graph is a path, so φ either fixes its vertices pointwise or reverses their order. If it fixes them pointwise, it fixes both attachment vertices: aH is the neighbor of p1 outside the path interior, and similarly for aH ′ . Removing the path interior leaves the two connected copies, each of which must then be preserved. Their asymmetry forces the restriction of φ to each copy to be the identity, so φ is the identity on the entire graph. If it reverses the path, it exchanges the attachment vertices and restricts to an isomorphism H → H ′ mapping aH to aH ′ . Distinct representatives in Fk are not isomorphic, while for H = H ′ the identity between the two copies preserves their distinguished vertices. This proves the characterization. Finally, the following direct observation holds, which implies that Bρ (H, H ′ ) belongs to SYMD when it belongs to SYM and the conditions of the below fact hold. Fact 3. Every graph Bρ (H, H ′ ) has radius at most ⌈ρ/2⌉ + 2. In particular, if ρ ∈ {2µ + 2, 2µ + 3} and µ ≤ D − 4, every such graph has radius at most D. Proof. A vertex in the middle of the central path between the nodes aH and aH ′ is at distance at most ⌈ρ/2⌉ from both aH and aH ′ . Every vertex of either graph H or H ′ is within distance 2 of its respective vertex aH or aH ′ , because the copy has diameter at most 2. Hence this vertex in the middle has eccentricity at most ⌈ρ/2⌉ + 2. For either value of ρ, this is at most µ + 4 ≤ D.

5.3

Classical lower bounds for symmetry

Fraigniaud et al. [FMO+ 19, Corollary 3.2] established an Ω(n2 ) certificate lower bound for one-round dMA protocols for unrestricted symmetry. The following theorem extends this bound to multiple verification rounds and shows that the hardness persists under a radius bound. Theorem 4. Let µ = µ(n) ≥ 1 satisfy µ = o(n). Every µ-round dMA protocol for SYM with fixed completeness c and soundness error s satisfying 2c − 1 > s has worst-case certificate size Ω(n2 /µ) bits. The same bound holds for SYMD whenever D ≥ 5 and µ ≤ D − 4. Proof. Fix such a protocol Π, for either property. For each sufficiently large n, define k := n−ρ+1 2 and ( 2µ + 2, n odd, ρ := 2µ + 3, n even. Then k is an integer, and µ = o(n) gives k = Θ(n). Consider the n-vertex graphs Bρ (H, H ′ ) with H, H ′ ∈ Fk . By Lemma 32, these belong to SYM exactly when H = H ′ . For SYMD , Fact 3 ensures that every graph in the family satisfies the radius condition, so membership in SYMD is also equivalent to H = H ′ .

52

We apply the same fooling-set argument as for TreeEQµ , following [FLNP21, Theorem 9]. As there, identifiers and ports must be chosen consistently so that combining the left copy of one instance with the right copy of another preserves the relevant local views. Assign identifiers 1, . . . , k to the left copy in its fixed vertex order, and k + 1, . . . , 2k to the right copy. In particular, the two attachment vertices always have identifiers 1 and k + 1. Give pj identifier 2k + j. Fix the central-path ports, including port 1 at each attachment vertex. At aH and aH ′ , assign ports 2, . . . , degH (aH )+1 and 2, . . . , degH ′ (aH ′ )+1, respectively, to the neighbors inside their copy in increasing identifier order. Every other vertex u in a copy uses ports 1, . . . , deg(u) in increasing neighbor identifier order. Thus the identifiers and ports within a copy depend only on that copy and its side, and the path identifiers and ports are the same throughout the family. All instances also have the same known parameters, including n. Let b = b(n) be the worst-case certificate size of Π. For each H ∈ Fk , choose a certificate assignment ΓH under which all nodes of Bρ (H, H) accept with probability at least c. Such an assignment exists by completeness, and is fixed before the random coins are sampled. Claim D. For distinct H, H ′ ∈ Fk , it holds

ΓH (p1 ), . . . , ΓH (p2µ ) = ̸ ΓH ′ (p1 ), . . . , ΓH ′ (p2µ ) . Proof of Claim D. Suppose the tuples agree. Consider the no-instance Bρ (H, H ′ ). Partition its vertices into a left group L consisting of the vertices in H plus p1 , . . . , pµ , and a right group R containing the remaining vertices. Give to the nodes in L their certificates from ΓH and to the nodes in R their certificates from ΓH ′ . Notice that on p1 , . . . , p2µ , the assignments agree by assumption. The remaining internal vertices p2µ+1 and, when present, p2µ+2 are at distance at least µ + 1 from L and lie in R with certificates from ΓH ′ , so they need not appear in the common tuple. Every node in L has the same radius-µ initial view as in Bρ (H, H) with ΓH . Indeed, the vertex aH ′ is at distance at least ρ − µ ≥ µ + 2 from the nodes in this set, and every certificate on the path visible across the cut has index at most 2µ, so belongs to the common tuple. The nodes in H and their identifiers and ports agree by construction. Similarly, by an analogous argument, every node in R has the same radius-µ initial view as in Bρ (H ′ , H ′ ) with ΓH ′ . We compare the executions on Bρ (H, H ′ ), Bρ (H, H), and Bρ (H ′ , H ′ ) using the same public random bits in all three and the same private random bits at nodes with the same identifier. Each execution still has the prescribed distribution of randomness. By locality, every node in L makes the same decision on Bρ (H, H ′ ) as its counterpart on Bρ (H, H). Likewise, every node in R makes the same decision on Bρ (H, H ′ ) as its counterpart on Bρ (H ′ , H ′ ). By completeness of Π, and the fact that Bρ (H, H) is a yes-instance, the probability that all nodes in L accept in the execution of Bρ (H, H ′ ) is therefore at least c, and the same holds for the nodes in R. Therefore,   Pr all nodes accept on Bρ (H, H ′ ) ≥ 1 − (1 − c) − (1 − c) = 2c − 1 > s. This contradicts the soundness error s of Π: Bρ (H, H ′ ) is a no-instance and therefore all the nodes should accept with probability at most s. A binary certificate of length at most b has 2b+1 − 1 possible values, including its length. By Claim D, the |Fk | instances of the form Bρ (H, H) require distinct tuples of 2µ such certificates. Hence |Fk | ≤ (2b+1 − 1)2µ < 22µ(b+1) ,

53

and therefore b>

log2 |Fk | − 1. 2µ

By Fact 2, log2 |Fk | = Ω(k 2 ). Since k = Θ(n) and µ = o(n), the term k 2 /µ tends to infinity, so the additive constant is negligible. It follows that b(n) = Ω(k 2 /µ) = Ω(n2 /µ). The proof applies to both properties SYM and SYMD . Combining Theorem 2, Corollary 3, and Theorem 4, for every fixed classical round budget µ ≥ 1, graph symmetry has a quantum protocol using O(n5/3 (log n)7/3 ) qubits per node, whereas every classical protocol with the stated completeness and soundness requires Ω(n2 ) certificate bits. For fixed D ≥ 5 and 1 ≤ µ ≤ D − 4, the corresponding bounds for SYMD are O(n log n) qubits and Ω(n2 ) bits. The quantum upper bounds also apply to individual message sizes. The bounded-radius comparison also applies to growing D = D(n) and µ = µ(n) = o(n) with D ≥ 5 and µ ≤ D − 4. It gives a strict quantum advantage whenever nD log n = o(n2 /µ), equivalently µD log n = o(n). Acknowledgements Masayuki Miyamoto was supported by JSPS KAKENHI Grant Number JP25K24383 and MEXT Supporting Pioneering Research through AI for 1,000 Discovery challenges Program (SPReAD) Japan Grant Number JPMXP1726277558. AI disclosure We used GPT-5.6 Sol to assist with constructing the protocol described in Section 3.2. ChatGPT with GPT-6 Astra and GPT-6.1 Sol were used to assist with the writing. The authors verified the correctness and originality of all content, including references, and take full responsibility for them.

References [AAV16]

Anurag Anshu, Itai Arad, and Thomas Vidick. Simple proof of the detectability lemma and spectral gap amplification. Phys. Rev. B, 93:205142, May 2016.

[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 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1295–1306. ACM, 2025.

[BBCR+ 25]

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, MarcOlivier 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), pages 451–462. ACM, 2025.

[BC25]

Dan Alden Baterisna and Yi-Jun Chang. Optimal local certification on graphs of bounded pathwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 99–109, 2025.

54

[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), pages 1268–1308. SIAM, 2026.

[BCF+ 24]

Nicolas Bousquet, Linda Cook, Laurent Feuilloley, Théo Pierron, and Sébastien Zeitoun. Local certification of forbidden subgraphs. arXiv preprint arXiv:2402.12148, 2024.

[BCWDW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical review letters, 87(16):167902, 2001. [BdW01]

Harry Buhrman and Ronald de Wolf. Communication complexity lower bounds by polynomials. In Proceedings 16th Annual IEEE Conference on Computational Complexity, pages 120–130. IEEE, 2001.

[BFP22]

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. What can be certified compactly? Compact local certification of MSO properties in tree-like graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 131–140, 2022.

[BFP24]

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. Journal of Parallel and Distributed Computing, 193:104954, 2024.

[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), pages 3298–3312. SIAM, 2026.

[BZ25]

Nicolas Bousquet and Sébastien Zeitoun. A subquadratic certification scheme for P5 -free graphs. Theoretical Computer Science, 1033:115091, 2025.

[CHPP20]

Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112–124, 2020.

[CKM25]

Linda Cook, Eun Jung Kim, and Tomáš Masařík. A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 110– 120, 2025.

[CLT26]

Yi-Jun Chang, Yi-Xuan Lee, and Meng-Tsung Tsai. Local certification of vertex and edge connectivity. arXiv preprint arXiv:2607.13677, 2026.

[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 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1901–1910, 2024.

55

[DEL+ 24]

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.

[DW01]

Ronald De Wolf. Quantum computing and communication complexity. University of Amsterdam, 2001.

[EL22]

Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. Theoretical Computer Science, 909:68–75, 2022.

[ER63]

Paul Erdős and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar, 14(3–4):295–315, 1963.

[Feu21]

Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(Distributed Computing and Networking), 2021.

[FFM+ 21]

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83(7):2215–2244, 2021.

[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 43rd ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2024.

[FLNP21]

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), 2021.

[FLS26]

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

[FMO+ 19]

Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. On distributed Merlin–Arthur decision protocols. In Structural Information and Communication Complexity, volume 11639 of Lecture Notes in Computer Science, pages 230–245. Springer, 2019.

[FMZ27]

Pierre Fraigniaud, Frédéric Magniez, and Isabella Ziccardi. No distributed quantum advantage for 3-coloring rooted trees and 2-coloring even cycles. In Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2027. To appear. Preprint arXiv:2607.04852.

[FNW92]

M. Fannes, B. Nachtergaele, and R. F. Werner. Finitely correlated states on quantum spin chains. Communications in Mathematical Physics, 144(3):443–490, 1992.

[GM18]

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), pages 337–346. ACM, 2018.

56

[GMN23]

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), volume 272 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1– 63:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.

[GNR19]

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), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.

[GS16]

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

[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.

[JMRRR25]

Benjamín Jauregui, Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport. Compact distributed certification of geometric graph classes. Journal of Computer and System Sciences, 154:103661, 2025.

[KKP10]

Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010.

[Kna88]

Stefan Knabe. Energy gaps and elementary excitations for certain VBS-quantum antiferromagnets. Journal of Statistical Physics, 52(3-4):627–638, 1988.

[LGMN23]

François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed quantum interactive proofs. In 40th International Symposium on Theoretical Aspects of Computer Science, 2023.

[Lin92]

Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992.

[Miy25]

Masayuki Miyamoto. Distributed complexity of Pk -freeness: Decision and certification. In 36th International Symposium on Algorithms and Computation (ISAAC 2025), pages 51:1–51:21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.

[Nac96]

Bruno Nachtergaele. The spectral gap for some spin chains with discrete symmetry breaking. Communications in Mathematical Physics, 175(3):565–606, 1996.

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010.

[vAdV22]

Joran van Apeldoorn and Tijn de Vos. A framework for distributed quantum queries in the CONGEST model. In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2022.

[WY22]

Xudong Wu and Penghui Yao. Quantum complexity of weighted diameter and radius in CONGEST networks. In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2022. 57

A

Proof of Claim A

The following lemma gives an inequality for two adjacent terms of Ht that we will use to prove Claim A. Lemma 33. H3 = (I−Π1,2 )+(I−Π2,3 ) has no eigenvalue in the open interval (0, 1/2). Equivalently, (I − Π1,2 )(I − Π2,3 ) + (I − Π2,3 )(I − Π1,2 ) ⪰ − 12 H3 . √ P Proof. Recall from the proof of Lemma 13 that |Ω⟩ = L−1/2 a P |aa⟩ and |sab ⟩ = (|ab⟩ + |ba⟩)/ 2, a < b, form an orthonormal basis of WL , so that ΠL = |Ω⟩⟨Ω| + a<b |sab ⟩⟨sab |. Hence ΠL |aa⟩ = L−1/2 |Ω⟩ =

1X |bb⟩, L

√ ΠL |ab⟩ = |sab ⟩/ 2 = 12 (|ab⟩ + |ba⟩) (a ̸= b).

(9)

b

To study the eigenvalues of H3 , we decompose (CL )⊗3 into orthogonal subspaces that H3 maps into themselves. For 1 ≤ a < b < c ≤ L, define the subspace Eabc of (CL )⊗3 by Eabc = span{|abc⟩, |acb⟩, |bac⟩, |bca⟩, |cab⟩, |cba⟩}, and for an index k define the subspace Ek of (CL )⊗3 by Ek = span{|kkk⟩, |aak⟩, |aka⟩, |kaa⟩ with a ̸= k}. Every basis vector |xyz⟩ lies in exactly one of these subspaces: in Eabc for some a < b < c if x, y, z are distinct, and otherwise in Ek for the index k that occurs once or three times among x, y, z. Thus we have the orthogonal decomposition   ! L M M L ⊗3 (C ) =  Eabc  ⊕ Ek . 1≤a<b<c≤L

k=1

P By (9), Π1,2 maps a basis vector |xyz⟩ to 12 (|xyz⟩ + |yxz⟩) if x ̸= y and to L1 b |bbz⟩ if x = y. Hence Π1,2 maps each of the subspaces Eabc and Ek into itself, and the same argument applied to registers 2 and 3 shows that Π2,3 does too. Therefore H3 = 2I − Π1,2 − Π2,3 maps each of the subspaces Eabc , Ek into itself, and since the subspaces form an orthogonal decomposition of (CL )⊗3 , the eigenvalues of H3 are the eigenvalues of the restrictions of H3 to the subspaces. It therefore suffices to show that the restriction of H3 to each of the subspaces Eabc and Ek has no eigenvalue in (0, 12 ). Eigenvalues on Eabc . On Eabc the three registers carry distinct symbols, so (9) gives Π1,2 |xyz⟩ = 1 1,2 = 1 (I + F ) on E 1,2 abc , where F1,2 exchanges the 2 (|xyz⟩ + |yxz⟩) for every basis vector, that is, Π 2 1 2,3 first two registers, and likewise Π = 2 (I + F2,3 ). Hence H3 = 12 (2I − F1,2 − F2,3 ) on Eabc . Write |w1 ⟩, . . . , |w6 ⟩ for |abc⟩, |bac⟩, |bca⟩, |cba⟩, |cab⟩, |acb⟩ in this order, and consider the index modulo 6. Then F1,2 exchanges |w1 ⟩ with |w2 ⟩, |w3 ⟩ with |w4 ⟩, and |w5 ⟩ with |w6 ⟩, while F2,3 exchanges |w2 ⟩ with |w3 ⟩, |w4 ⟩ with |w5 ⟩, and |w6 ⟩ with |w1 ⟩. Consequently (F1,2 + F2,3 )|wℓ ⟩ = |wℓ−1 ⟩ + |wℓ+1 ⟩ (1 ≤ ℓ ≤ 6), P and for 0 ≤ j ≤ 5 and ω = e2πi/6 the vector 6ℓ=1 ω jℓ |wℓ ⟩ is an eigenvector of F1,2 + F2,3 with eigenvalue ω −j + ω j = 2 cos(πj/3), because X X (F1,2 + F2,3 ) ω jℓ |wℓ ⟩ = ω jℓ (|wℓ−1 ⟩ + |wℓ+1 ⟩) ℓ

ℓ

58

=

X (ω j(ℓ+1) + ω j(ℓ−1) )|wℓ ⟩ ℓ

= (ω j + ω −j )

X

ω jℓ |wℓ ⟩.

ℓ

P ′ These six vectors { ℓ ω jℓ |wℓ ⟩}0≤j≤5 are pairwise orthogonal, since 6ℓ=1 ω (j −j)ℓ = 0 for j ̸= j ′ , so they form an eigenbasis of Eabc . The eigenvalues of F1,2 + F2,3 on Eabc are therefore 2 cos(πj/3) for 0 ≤ j ≤ 5, namely 2, 1, −1, −2, −1, 1, and those of H3 = 21 (2I − F1,2 − F2,3 ) are 0, 12 , 32 , 2, 32 , 12 . Thus, none of them lies in (0, 12 ). P

Eigenvalues on Ek . We first compute the action of H3 on the basis vectors of Ek . By (9), for every a ̸= k, L 3 1 1X H3 |aak⟩ = |aak⟩ − |aka⟩ − |bbk⟩, 2 2 L b=1

1 1 H3 |aka⟩ = |aka⟩ − |aak⟩ − |kaa⟩, 2 2 L 3 1 1X |kbb⟩, H3 |kaa⟩ = |kaa⟩ − |aka⟩ − 2 2 L

(10)

b=1

H3 |kkk⟩ = 2|kkk⟩ − The sums difference:

b |bbk⟩ and

P

1 L

L X

L

|bbk⟩ −

b=1

1X |kbb⟩. L b=1

b |kbb⟩ are independent of a. Let |Σ⟩ and |∆⟩ be their sum and their

P

|Σ⟩ =

|∆⟩ =

L X b=1 L X

|bbk⟩ + |kbb⟩ ,
X
|bbk⟩ − |kbb⟩ = |aak⟩ − |kaa⟩ .

b=1

a̸=k

Thus, L X b=1

L X

1 |bbk⟩ = |Σ⟩ + |∆⟩ , 2

|kbb⟩ =

b=1

1 |Σ⟩ − |∆⟩ . 2

To cancel the terms proportional to |Σ⟩ in the calculation in (13) below, define

We show below that

H ′ = H3 +

1 |Σ⟩⟨Σ|. 2L

H ′ ⪰ 12 I

on Ek .

(11)

We first derive from (11) that H3 has no eigenvalue in (0, 21 ) on Ek . By the definition of H ′ , every |ϕ⟩ ∈ Ek with ⟨Σ|ϕ⟩ = 0 satisfies ⟨ϕ|H3 |ϕ⟩ = ⟨ϕ|H ′ |ϕ⟩ ≥ 21 ∥|ϕ⟩∥2 .

(12)

Suppose that |ψ1 ⟩, |ψ2 ⟩ ∈ Ek are two orthonormal eigenvectors of H3 , both with eigenvalues less than 12 . If either eigenvector is orthogonal to |Σ⟩, take that eigenvector as |ϕ⟩. Otherwise, set |ϕ⟩ =

|ψ1 ⟩ |ψ2 ⟩ − . ⟨Σ|ψ1 ⟩ ⟨Σ|ψ2 ⟩ 59

In this case, ⟨Σ|ϕ⟩ =

⟨Σ|ψ1 ⟩ ⟨Σ|ψ2 ⟩ − = 1 − 1 = 0, ⟨Σ|ψ1 ⟩ ⟨Σ|ψ2 ⟩

and |ϕ⟩ ̸= 0 because |ψ1 ⟩ and |ψ2 ⟩ are linearly independent. Thus, in either case, |ϕ⟩ is a nonzero vector in Ek orthogonal to |Σ⟩. Since it is a linear combination of eigenvectors of H3 with eigenvalues less than 21 , ⟨ϕ|H3 |ϕ⟩ < 12 ∥|ϕ⟩∥2 , contradicting (12). Therefore, at most one eigenvalue of H3 on Ek is less than 21 . On the other hand, 0 is an eigenvalue of H3 on Ek : adding the first three lines of (10) gives H3 (|aak⟩ + |aka⟩ + |kaa⟩) = |aak⟩ + |kaa⟩ − L1 |Σ⟩ for every a ̸= k, and together with the last line of (10),  X X

|Σ⟩ = |Σ⟩ − |Σ⟩ = 0. H3 |kkk⟩ + |aak⟩ + |aka⟩ + |kaa⟩ = 2|kkk⟩ + |aak⟩ + |kaa⟩ − 1+(L−1) L a̸=k

a̸=k

Hence H3 has no eigenvalue in (0, 12 ) on Ek . This completes the proof. Proving (11). It remains to prove (11). By (10) and the definitions of H ′ and |Σ⟩, for every a ̸= k we can find the following five eigenvectors of H ′ whose eigenvalues are all at least 1/2. In the |kkk⟩ calculation, ⟨Σ|kkk⟩ = 2, since the two terms |bbk⟩ and |kbb⟩ both equal |kkk⟩ when b = k; this explains the coefficient 2/(2L) below.

2 H ′ |aak⟩ + 2|aka⟩ + |kaa⟩ = 12 |aak⟩ + 2|aka⟩ + |kaa⟩ − L1 |Σ⟩ + 2L |Σ⟩
1 = |aak⟩ + 2|aka⟩ + |kaa⟩ ,
2
′ 2 H |aak⟩ − |aka⟩ + |kaa⟩ = 2 |aak⟩ − |aka⟩ + |kaa⟩ − L1 |Σ⟩ + 2L |Σ⟩
= 2 |aak⟩ − |aka⟩ + |kaa⟩ , 2 H ′ |kkk⟩ = 2|kkk⟩ − L1 |Σ⟩ + 2L |Σ⟩ = 2|kkk⟩,

′ L−1 1 3 H |∆⟩ = 2 − L |∆⟩ = 2 + L1 |∆⟩,  
|∆⟩ 1 ′ H |aak⟩ − |kaa⟩ − = 32 |aak⟩ − |kaa⟩ − L1 |∆⟩ − L−1 L−1   |∆⟩ = 23 |aak⟩ − |kaa⟩ − . L−1

(13) 1 1 2 + L

|∆⟩

We now check that the eigenvectors in (13) span Ek . For every a ̸= k, a linear combination of the fourth and fifth eigenvectors in (13) gives   |∆⟩ |∆⟩ |aak⟩ − |kaa⟩ = |aak⟩ − |kaa⟩ − + . L−1 L−1 Then, all of |aak⟩, |aka⟩, |kaa⟩ can be reconstructed by linear combinations of |aak⟩ + 2|aka⟩ + |kaa⟩,

|aak⟩ − |aka⟩ + |kaa⟩,

|aak⟩ − |kaa⟩.

Since |kkk⟩ is also included in (13), these eigenvectors span Ek . Therefore, (11) follows. Claim A (Restated). For every integer t ≥ 2, Ht ⪰

60

4 (I − Gt ). t2

Proof of Claim A. Let hi = I − Πi,i+1 for 1 ≤ i < t, so that Ht = 1 ≤ i < t, with κ0 = κt = 0, and define D=

t−1 X

Pt−1

i=1 hi .

Set κi = i(t − i) for

κi hi .

i=1

Let P be the projector onto ker D. We first prove D ⪰ I − P . Expanding the square, D2 =

t−1 X

κ2i hi +

i=1 t−1 X

t−2 X

κi κi+1 (hi hi+1 + hi+1 hi ) +

i=1

X

κi κj hi hj

1≤i,j<t |i−j|≥2

t−2

1X κi κi+1 (hi + hi+1 ) 2 i=1 i=1   t−1 X κi−1 + κi+1 = κi κi − hi 2 ⪰

=

i=1 t−1 X

κ2i hi −

(14)

κi hi = D.

i=1

Here, the inequality uses Lemma 33, applied to registers i, i + 1, i + 2 for each 1 ≤ i ≤ t − 2, and the fact that hi hj ⪰ 0 when |i − j| ≥ 2, since hi and hj act on disjoint pairs of registers. Since D is positive semidefinite, it has an orthonormal basis |z1 ⟩, |z2 ⟩, . . . of eigenvectors, say D|zj ⟩ = λj |zj ⟩ 2 2 with λj ≥ 0, and (14) gives P λj = ⟨zj |D |zj ⟩ ≥ ⟨zj |D|zj ⟩ = λj , so λj = 0 or λj ≥ 1. Expanding an arbitrary vector as |x⟩ = j cj |zj ⟩, ⟨x|D|x⟩ =

X

λj |cj |2 ≥

X

|cj |2 = ⟨x|(I − P )|x⟩,

j:λj ̸=0

j

that is, D ⪰ I − P . Since κi > 0 for 1 ≤ i < t, ker D = ker

X

κi hi = ker

i

X

hi = ker Ht .

i

Hence, by Lemma 13, ker Ht = St , meaning I − P = I − Gt . Finally, i(t − i) ≤ t2 /4 for 1 ≤ i < t, so t2 X t2 Ht = hi ⪰ D ⪰ I − P = I − Gt . 4 4 i

This proves Claim A.

B

Proof of Claim B

Claim B (Restated). For 1 ≤ j ≤ s − 2, the operator γj + γj+1 has no eigenvalue in the open interval (0, 3/4).

61

Fix 1 ≤ j ≤ s − 2. The operator γj + γj+1 acts only on the three consecutive blocks j, j + 1, j + 2. 2,3 Thus, we relabel these blocks as 1, 2, 3, and write this operator as A = (I − G1,2 2m ) + (I − G2m ). To prove Claim B, it suffices to show that, for every vector |ψ⟩ on blocks 1, 2, 3, 9 ∥(I − G3m )|ψ⟩∥2 . 11

⟨ψ|A|ψ⟩ ≥

(15)

Indeed, A vanishes on S3m , so any eigenvector of the Hermitian operator A with a nonzero eigenvalue is orthogonal to S3m . Applying (15) to such an eigenvector shows that its eigenvalue is at least 9/11 > 3/4, as required in Claim B. The following lemma will be used to prove (15). Lemma 34. Let Z = {u ∈ {0, 1}L : u1 = 0}. Fix a finite-dimensional Hilbert space of arbitrary dimension. For each u ∈ Z, let |au ⟩ be a vector in that space. Then X 9 X ∥|au ⟩∥2 ≤ |ϕu ⟩⊗m ⊗ |au ⟩ 10 u∈Z

u∈Z

2

≤

11 X ∥|au ⟩∥2 . 10 u∈Z

In particular, the vectors {|ϕu ⟩⊗m }u∈Z are linearly independent.
Proof of Lemma 34. For a fixed u ∈ Z, there are L−1 strings v ∈ Z that differ from u in exactly ℓ ℓ
L−1

bits, and ⟨ϕu |ϕv ⟩ = 1−2ℓ/L. Combining the terms indexed by ℓ and L−ℓ uses L−1 + L−ℓ = Lℓ . ℓ When L is even, the middle term ℓ = L/2 vanishes because 1 − 2ℓ/L = 0. Thus X

m

|⟨ϕu |ϕv ⟩|

=

v∈Z v̸=u

L−1 X ℓ=1

L−1 ℓ

X

=

1≤ℓ<L/2 L ℓ

Here, the inequalities use

2ℓ m L

 1−

  
ℓ 1 L 2ℓ m X ≤ Le−2m/L ≤ . 1− L 10 ℓ ℓ≥1

≤ Lℓ , 1 − x ≤ e−x , and Le−2m/L ≤ e−12/5 < 1/11. We now have 2

X

⊗m

|ϕu ⟩

⊗ |au ⟩

−

u∈Z

=

X

∥|au ⟩∥2

u∈Z

X

⟨ϕu |ϕv ⟩m ⟨au |av ⟩

u,v∈Z u̸=v

≤

X

|⟨ϕu |ϕv ⟩|m ∥|au ⟩∥ ∥|av ⟩∥

(triangle inequality and Cauchy–Schwarz)

u,v∈Z u̸=v

≤

1 X |⟨ϕu |ϕv ⟩|m ∥|au ⟩∥2 + ∥|av ⟩∥2 2 u,v∈Z u̸=v

=

X u∈Z

∥|au ⟩∥2

X

|⟨ϕu |ϕv ⟩|m

v∈Z v̸=u

62

(2ab ≤ a2 + b2 )

(16)

≤

1 X ∥|au ⟩∥2 10

(by (16)).

u∈Z

The two inequalities in Lemma 34 follow. Taking |au ⟩ ∈ C in the lower bound proves that {|ϕu ⟩⊗m : u ∈ Z} is linearly independent. We are now ready to prove Claim B. Proof of (15). It suffices to construct |χ⟩ ∈ S3m with ∥|ψ⟩ − |χ⟩∥2 ≤ (11/9)⟨ψ|A|ψ⟩ since ∥|ψ⟩ − |χ⟩∥2 ≥ ∥(I − G3m )|ψ⟩∥2 . We write 2,3 2 2 ⟨ψ|A|ψ⟩ = ∥|ψ⟩ − G1,2 2m |ψ⟩∥ + ∥|ψ⟩ − G2m |ψ⟩∥ . ⊥ on To bound these two squared norms from below, we first decompose |ψ⟩ according to Sm and Sm their common block 2. Complementing all bits of u negates |ϕu ⟩, and Z contains one string from each complementary pair, so Sm = span{|ϕu ⟩⊗m : u ∈ Z}. We can therefore write X ⊗ |au ⟩1,3 , |au ⟩ ∈ (CL )⊗2m , |ψ⟩ = |ψ⊥ ⟩ + |ϕu ⟩⊗m 2 u∈Z ⊥ |ψ⊥ ⟩ ∈ (CL )⊗m ⊗ Sm ⊗ (CL )⊗m .

The vector |ψ⊥ ⟩ is orthogonal to every sum of vectors with a factor from Sm on block 2. To obtain |χ⟩ ∈ S3m , we project blocks 1 and 3 of each |au ⟩ onto the span of |ϕu ⟩⊗m . Let Qu = (|ϕu ⟩⟨ϕu |)⊗m be the orthogonal projector onto that span, and set X
⊗ (Qu ⊗ Qu )|au ⟩ 1,3 . |χ⟩ = |ϕu ⟩⊗m 2 u∈Z

Each summand is a scalar multiple of |ϕu ⟩⊗3m , so |χ⟩ ∈ S3m . Subtracting |χ⟩ from |ψ⟩ and applying Lemma 34 gives the following upper bound:
∥(I − G3m )|ψ⟩∥2 = ∥(I − G3m )(|ψ⟩ − |χ⟩)∥2 G3m |χ⟩ = |χ⟩
≤ ∥|ψ⟩ − |χ⟩∥2 ∥I − G3m ∥ ≤ 1 2 2

= ∥|ψ⊥ ⟩∥ +

X

⊗ |ϕu ⟩⊗m 2

(I − Qu ⊗ Qu )|au ⟩ 1,3

(orthogonality)

(17)

u∈Z

11 X ≤ ∥|ψ⊥ ⟩∥2 + ∥(I − Qu ⊗ Qu )|au ⟩∥2 10

(Lemma 34).

u∈Z

For each u ∈ Z, using I − Qu ⊗ Qu = (I − Qu ) ⊗ I + Qu ⊗ (I − Qu ), ∥(I − Qu ⊗ Qu )|au ⟩∥2 = ∥((I − Qu ) ⊗ I)|au ⟩∥2 + ∥(Qu ⊗ (I − Qu ))|au ⟩∥2 ≤ ∥((I − Qu ) ⊗ I)|au ⟩∥2 + ∥(I ⊗ (I − Qu ))|au ⟩∥2 .

(18)

2,3 The projectors G1,2 2m and G2m project blocks 1, 2 and 2, 3, respectively, onto S2m and act as the identity on the remaining block. By the spanning description of S2m above, there are |bu ⟩, |cu ⟩ ∈ (CL )⊗m with X G1,2 |ϕu ⟩⊗m ⊗ |ϕu ⟩⊗m ⊗ |bu ⟩3 , 2m |ψ⟩ = 1 2 u∈Z

G2,3 2m |ψ⟩ =

X

|cu ⟩1 ⊗ |ϕu ⟩⊗m ⊗ |ϕu ⟩⊗m 2 3 .

u∈Z

63

Subtract the two displayed expansions from that of |ψ⟩: 2,3 I−G1,2 2m , I−G2m are orthogonal projectors 2
⊗m |au ⟩ − |ϕu ⟩ ⊗ |bu ⟩ 1,3

2,3 2 2 ⟨ψ|A|ψ⟩ = ∥(I − G1,2 2m )|ψ⟩∥ + ∥(I − G2m )|ψ⟩∥

= 2∥|ψ⊥ ⟩∥2 +

X

|ϕu ⟩⊗m ⊗ 2

u∈Z 2

+

X

|ϕu ⟩⊗m ⊗ 2

⊗m

|au ⟩ − |cu ⟩ ⊗ |ϕu ⟩

1,3

(orthogonality)

u∈Z

 9 X ∥|au ⟩ − |ϕu ⟩⊗m ⊗ |bu ⟩∥2 + ∥|au ⟩ − |cu ⟩ ⊗ |ϕu ⟩⊗m ∥2 (Lemma 34) 10 u∈Z  (I−Qu )|ϕu ⟩⊗m =0 9 X ∥(I−Qu )⊗I∥≤1 ≥ 2∥|ψ⊥ ⟩∥2 + ∥((I − Qu ) ⊗ I)|au ⟩∥2 + ∥(I ⊗ (I − Qu ))|au ⟩∥2 10 ∥I⊗(I−Qu )∥≤1 u∈Z 9 X by (18) ∥(I − Qu ⊗ Qu )|au ⟩∥2 ≥ 2∥|ψ⊥ ⟩∥2 + 10 u∈Z !
9 11 X 2 2 ≥ ∥|ψ⊥ ⟩∥ + ∥(I − Qu ⊗ Qu )|au ⟩∥ 2 ≥ 9/11 11 10 ≥ 2∥|ψ⊥ ⟩∥2 +

u∈Z

9 9 ≥ ∥|ψ⟩ − |χ⟩∥2 ≥ ∥(I − G3m )|ψ⟩∥2 11 11

64

by (17).

Related documents

• AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates#1013761
• DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing#985277
• Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth#1144009
• No Size-Preserving Amplification with Quantum Advice#1188055
• Perfect non-local quantum computation is impossible#1154491