Distributed Quantum Property Testing with Quantum Carrier Pigeons

1 Introduction

• The work frames distributed quantum inference as a natural analogue of classical distributed inference and asks how communication constraints affect state-certification copy complexity.The motivation includes inference over developing quantum networks and distributed data settings; communication is identified as a central network bottleneck.Source: §1 · p. 3

1.1 Framework

• The framework models one-copy nodes sending one-way messages of at most n_c classical bits and n_q qubits, with public or private randomness and no communication among nodes.The paper focuses on the (n_c, n_q, R) model without shared entanglement, and on total per-node communication n_c + n_q ≤ log2(d).Source: §1.1 · pp. 4–6
• Quantum state certification tests whether ρ = σ against alternatives satisfying ‖ρ − σ‖_1 ≥ ε, and the framework counts the minimum number of single-copy nodes needed.The target state σ has a complete classical description, and certification requires accept and reject outputs with probability at least 2/3 on the respective cases.Source: §1.1 · p. 5

1.2 Our Results

• Shared randomness yields a quadratic communication advantage for distributed certification, while private coins require a stronger lower bound and admit an algorithm that nearly matches it.For constant communication parameters, the public- versus private-coin bounds have a dimension-dependent gap of order d; the shared seed is independent of the hypothesis state.Source: §1.2 · p. 6

1.3 Technical Overview

• Each node’s action is modeled as a quantum instrument producing a classical-quantum message, after which the central node may perform fully coherent measurements on received states.In the public-coin setting, the instruments share a random string; in the private-coin setting, each node chooses its instrument independently.Source: §1.3 · p. 7

1.3.1 Testing without classical communication

• With quantum-only messages, nodes can apply a random unitary and retain a d_q-dimensional subspace, achieving quadratically better distance preservation than a generalization of prior pure-state compression.The distance-preservation analysis uses Weingarten calculus to bound second and fourth moments, followed by the Paley–Zygmund inequality.Source: §1.3.1 · p. 8

1.3.2 Testing with classical and quantum communication

• Random-unitary instruments and a tailored estimator exploit well-spread classical labels to reduce variance and obtain the public-coin upper bound.For private coins, a fixed set of O(d_q^2 d_c) unitaries is shown to satisfy the compression and label-spread properties, yielding the private-coin upper bound.Source: §1.3.2 · p. 9

1.3.3 Lower bound ideas

• The lower bounds lift Ingster–Suslina reasoning to quantum messages, using a generalized quantum χ² divergence to compare product states with mixtures over far alternatives.For private coins, the alternative mixture is minimized after the channels are fixed; the analysis uses a hard mixture of random perturbations and bounds a quadratic-form moment generating function. The bounds recover the centralized Ω(d/ε^2) lower bound when d_c=1 and d_q=d.Source: §1.3.3 · p. 10

1.4 Prior Work

• The framework generalizes the classical simultaneous-message-passing model of, while prior distributed inner-product-estimation results do not immediately imply bounds for this model.The discussion also relates the setting to classical distributed inference, centralized state certification, and quantum learning and testing; it distinguishes this work from DIPE, which uses two unknown states and only two distributed nodes.Source: §1.4 · pp. 11–12

1.5 Discussion

• The public-coin algorithm is tight, while the private-coin algorithm is tight up to a log d factor arising from the matrix Chernoff bound.The discussion identifies state tomography, shared entanglement, richer communication, multiple copies per node, limited shared randomness, privacy, untrusted parties, and multi-state inference as directions; it notes that the certification algorithm can be adapted to closeness testing.Source: §1.5 · pp. 12–13

Organization

• The paper presents background, public-coin and private-coin algorithms, and then lower bounds that are tight publicly and tight up to log factors privately.The algorithm sections begin with quantum-communication-only warmups before presenting the general upper bounds.Source: Organization · p. 13

2 Preliminaries

• The symmetrized quantum chi-square divergence uses α=1 and upper-bounds trace distance.The section states that the symmetry follows from an equality that collapses the trace into a square.Source: §2 · p. 14
• A classical–quantum state has classical and quantum registers of dimensions d_c and d_q, with component operators whose traces sum to one.Each component operator is positive semidefinite with trace at most one, although it need not itself be a valid quantum state.Source: §2 · p. 14

2.1 Quantum Channels and Quantum Instruments

• A quantum channel is completely positive and trace-preserving, while a quantum instrument outputs a classical–quantum state encoding outcomes and conditional quantum states.For an instrument, outcome i occurs with probability Tr(E_i(ρ)); the overall map preserves trace even though an individual E_i need not.Source: §2.1 · pp. 14–15
• When no classical communication is allowed, an instrument reduces to a quantum channel; it can also encode a classical string alongside a channel output.The examples illustrate both a single fixed classical string and a uniformly sampled string paired with a quantum output.Source: §2.1 · p. 15

2.2 Haar-measure moments

• The section states a second-order Haar integral for arbitrary matrices and notes that higher moments can be computed using Weingarten calculus.The second-order result is presented as a corollary of a standard Haar-random-unitary moment lemma.Source: §2.2 · p. 16

3 Public-Coin Upper Bound

• The compression must preserve enough distance between ρ and σ for certification to remain tractable.For quantum-only communication, the section uses a randomized channel that preserves an optimal amount of distance up to constant factors.Source: §3 · p. 16
• Randomized dimensionality reduction followed by Hilbert–Schmidt testing yields a tight upper bound with only quantum communication.The approach uses the Bădescu, O’Donnell, and Wright estimator and tester.Source: §3 · pp. 16–17
• For mixed communication, the proof generalizes compression to quantum instruments and tightens the estimator’s variance analysis for classical–quantum states.The tighter variance bounds support the main public-coin upper bound; the proof also uses the Paley–Zygmund inequality.Source: §3 · p. 17

3.1 Warmup 1: Public-Coin Testing with Only Quantum Communication

• O(d^2/(d_q ε^2)) copies suffice for public-coin certification with d_q-dimensional quantum messages and no classical bits.The algorithm uses O(1) repetitions, each with O(d^2/(d_q ε^2)) copies.Source: §3.1 · pp. 17–18
• Each batch uses shared randomness to choose a Haar-random unitary, sends the reduced d_q-dimensional state, and applies Hilbert–Schmidt certification centrally.The reduction traces out the unused subsystem; the test compares the compressed unknown state with the compressed hypothesis state.Source: §3.1 · pp. 17–18
• The algorithm repeats the batch test and rejects when “Far” occurs more than a threshold number of times.The proof uses the difference in “Far” probabilities between identical and ε-far states, with Hoeffding’s inequality to obtain success probability at least 2/3.Source: §3.1 · p. 18

3.2 Main Proof Outline

• Separate tests of classical and quantum marginals can both accept even when the joint instrument outputs are far in trace distance.The example motivates testing the classical and quantum registers together rather than in isolation.Source: §3.2 · p. 20
• The BOW estimator’s variance can depend on d_c for classical–quantum states whose probability mass is roughly O(1/d_c) across labels.When mass concentrates on one or a few labels, the variance improvement is not obtained.Source: §3.2 · p. 20
• The proposed instrument applies a Haar-random unitary, measures a classical register, traces out an unused register, and sends the remaining quantum state.The design aims to use each classical string with probability O(1/d_c), supporting the estimator’s well-spread-label condition.Source: Quantum Instrument Design · p. 20, §3.2 · p. 20

Quantum Instrument Design.

• The instruments must also preserve enough Hilbert–Schmidt distance to distinguish identical states from states that are ε-far in trace distance.The section presents this compression step as a generalization of the quantum-only argument.Source: Quantum Instrument Design · p. 21
• The estimator analysis and instrument design feed into the mixed-communication Algorithm 2 and the proof of Theorem 1.3.The section also identifies these two ingredients as key to the private-coin algorithm analysis.Source: Quantum Instrument Design · p. 21

3.3.1 Analysis of the BOW Estimator

• The CQ-adapted BOW estimator has a finer variance bound, but gives no improvement when classical labels concentrate on one value.The stated variance gain applies in the regime where the classical marginals are sufficiently spread out.Source: §3.3.1 · p. 21

3.3.2 Quantum Instrument Design

• With probability at least 3/4 over public-coin Haar U, both states’ label marginals have squared 2-norm at most 16/d_c.The Haar instrument is designed to spread probability mass across classical labels.Source: §3.3.2 · pp. 22–23

3.3.3 Quantum Instrument Compression

• The section extends Lemma 3.4 to quantum instruments, with the stated target bound applying to traceless Hermitian X.The proof relies on generalized supporting lemmas.Source: §3.3.3 · p. 24

3.3.4 A Public Coin Algorithm

• With public coins, nodes share Haar-random instruments, send resulting CQ states, and the central node estimates squared Hilbert–Schmidt distance across groups to certify.The protocol checks label spread and accepts when a majority of groups accept.Source: §3.3.4 · p. 25

4 Private-Coin Upper Bound

• Theorem 4.1 gives a private-coin protocol for ε-certification with mixed communication when 1 ≤ n_c + n_q ≤ ceil(log2 d).The theorem sets d_c = 2^n_c and d_q = 2^n_q; the supplied passage does not include its copy-complexity expression.Source: §4 · p. 26

4.1 Warmup 2: Private-Coin Testing with Only Quantum Communication

• For quantum-only communication, the protocol uses pre-agreed good unitaries instead of sampling shared random unitaries and applies the BOW estimator to transformed states.The central node aggregates estimates and compares them with a threshold to certify the state.Source: §4.1 · p. 27

4.1.1 Proof of Theorem 4.3

• A finite good set of unitaries exists: the proof uses Haar-random unitaries, projector averaging, and matrix Chernoff concentration.The probabilistic method establishes existence of a set that can be fixed in advance for the protocol.Source: §4.1.1 · pp. 29–30

4.2 Classical and Quantum Communication

• For mixed classical and quantum communication, the algorithm derandomizes the public-coin protocol using finitely many fixed unitaries and classical-quantum BOW estimates.Nodes send instrument outputs to the central node, which estimates transformed distances and compares their average with a threshold.Source: §4.2 · pp. 32–33
• Matrix Chernoff concentration controls the average of the matrices M(U_i) around their mean, supporting the first required inequality.The proof applies the bound to independently Haar-random unitaries.Source: §4.2 · p. 35
• Lemma 4.17 bounds the empirical averaged projector for independently Haar-random unitaries.The result is used with linearity of expectation and a matrix Chernoff bound.Source: §4.2 · p. 37
• Corollary 4.18 extends the projector bound to any traceless Hermitian operator X, establishing the second required inequality with high probability.Its proof conditions on the high-probability event in Lemma 4.17.Source: §4.2 · pp. 37–38
• A union bound shows that Haar-random unitaries satisfy both required inequalities with positive probability, so a deterministic choice exists.The proof concludes Theorem 4.12 by combining the two bounds.Source: §4.2 · p. 38

5 Lower Bounds

• The lower-bound framework reduces certification to mixedness testing and uses a χ²-divergence game in which private-coin adversaries choose hard mixtures after seeing the instruments.The minimax/maximin divergence framework adapts methods of Acharya et al. and Liu et al. to quantum instruments.Source: §5 · pp. 38–39
• The proof bounds these divergences using an almost-ε perturbation family and a generalized quantum Ingster-Suslina method.The family is used with the symmetrized method to upper-bound the divergences in Lemma 5.2 and derive the required node count.Source: §5 · pp. 39–40

5.1 Main Lower Bounds

• For d ≥ 6 and 0 < ε < ε0, certification requires distributed nodes in both public- and private-coin settings; the private-coin setting has a stronger lower bound.Source: §5.1 · p. 41

5.2 Proof of Lemmas 5.9, 5.10 and 5.11

• The technical lemmas relate χ²-divergence to augmented channel norms and bound those norms, using Kadison–Schwarz; instruments also cannot map inputs outside the support of their maximally mixed-state output.The proof also invokes a random-bit moment-generating-function bound.Source: §5 · p. 40, §5.1 · p. 41, §5.2 · p. 43
• The classical portion of the quantum channel has d_c basis vectors, and therefore rank(M_Λ) ≤ d_c d^2.Source: §5.2 · p. 46

• High-order Haar integrals are handled with Weingarten calculus, relating k-order random-unitary moments to symmetric-group elements [Mel24].Source: A Intermediate lemmas for compression… · p. 50
• Lemma A.1 introduces the permutation operator Pπ and Weingarten coefficient Wg(π, d) for a matrix M.Source: A Intermediate lemmas for compression… · p. 50
• The section focuses on fourth-order moments and bounds for real Weingarten coefficients that depend on dimension d.Source: A Intermediate lemmas for compression… · p. 50
• Lemma A.2 identifies id4 as the identity permutation in S4 and cites [BB96, Tables II & III].Source: A Intermediate lemmas for compression… · p. 50

A.1 Second-moment bounds

• The expected squared distance after applying Φ_U is rewritten using Δ = ρ−σ and evaluated as an averaged trace involving the channel output.Linearity and the partial-trace representation of Φ_U reduce the expression to a trace involving paired copies of UΔU†.Source: §A.1 · p. 51
• For each classical label c, the generalized calculation defines B_c(U) and expresses the squared branch norm through a Q-register swap and an identity on A.Pulling back the partial trace gives the equivalent trace on the full registers.Source: §A.1 · p. 51
• The operator R combines matching classical-label projectors with a Q-register swap and an A-register identity; its trace and swap-trace are computed by factoring registers.The calculation sums the fixed-label traces over all classical labels.Source: §A.1 · pp. 51–52
• The final bound uses q ≥ 2 and the stated relation between d_A, d_c, and d_q to control the remaining dimension terms.The proof first bounds the operators and then applies these dimension inequalities.Source: §A.1 · p. 52

A.2 Fourth-moment bounds

• The proof represents the fourth moment as a trace of the paired operator R against four copies of UΔU†, then averages over U.The permutation expansion uses γ = SWAP_1,2 ⊗ SWAP_3,4.Source: §A.2 · pp. 53–55
• The largest contribution to the fourth-moment bound comes from the case where π has cycle type (2, 2).The proof separates the permutation sum by cycle type before identifying this dominant case.Source: §A.2 · pp. 53–54
• The Weingarten coefficients are bounded by a dimension-dependent inverse power, and summing the finite nonzero terms yields the stated constant factor.The proof counts nine nonzero π choices and 24 τ choices; it gives C = 9 · 24 · C_W.Source: §A.2 · pp. 54, 56
• Because X is traceless, only permutations without singleton cycles contribute; the two surviving cycle types are (2, 2) and (4).Their trace terms are bounded using the second and fourth powers of X.Source: §A.2 · pp. 53, 56

B BOW Estimator Analysis

• The CQ estimator is designed to be unbiased for ||ρ−σ||_2^2 using m copies of ρ and full knowledge of σ.The estimator averages pairwise observables for Tr(ρ^2) and Tr(ρσ), and adds the known scalar Tr(σ^2).Source: B BOW Estimator Analysis · pp. 56, 57, 59
• The variance analysis separates disjoint, identical, and once-overlapping pairs; disjoint pairs have zero covariance, while once-overlapping pairs contribute A_1.The section sums the contributions from these three cases to bound the estimator variance.Source: B BOW Estimator Analysis · p. 60
• Lemma B.10 gives A1 ≤ ||p||∞Γ; combining four estimates with operator Jensen’s inequality gives A2 ≤ O(||p||2^2 + ||q||2^2), and Theorem 3.8 follows from Lemmas B.8–B.11.Source: B BOW Estimator Analysis · pp. 60–62
• The estimator’s partial expectation over one register yields ρ−σ plus a scalar identity term, which does not affect the variance.This form is used to bound A_1 for CQ states.Source: B BOW Estimator Analysis · p. 61

C Proof of Lemma 5.2

• For each distinguisher D, fixing a shared random string yields deterministic instruments that distinguish the equally likely cases with probability at least 9/16.The proof then applies the Helstrom bound and Lemma 2.3 to obtain the public-coin bound.Source: C Proof of Lemma 5.2 · p. 62
• In the private-coin setting, fixing each node’s random string gives fixed instruments, and averaging over those strings models each node by a deterministic instrument.The proof invokes Lemma 2.3 to conclude the private-coin result.Source: C Proof of Lemma 5.2 · pp. 62–63

D General Quantum Ingster-Suslina Lemma

• The proof follows O’Donnell and Wadhwa [OW26] while extending their analysis to generic α-χ²-divergences.The passage identifies this as the route to proving Lemma 5.3.Source: D General Quantum Ingster-Suslina Lemma · p. 63
• The setup fixes θ, S = σ(m), and P = E_θ[R_θ] before applying the definition of χ²-divergence.The final inequality uses 1 + x ≤ e^x for x ≥ 0.Source: D General Quantum Ingster-Suslina Lemma · pp. 63–64
• Using Δ_i,θ = ρ_i,θ − σ_i and Tr(Δ_i,θ) = 0, the proof rewrites the trace in terms of the state differences and σ_i.It then expands the terms using linearity of traces.Source: D General Quantum Ingster-Suslina Lemma · p. 63

E Centralized mixedness testing lower bound with the [LA24a] instance

• Ω(d/ε^2) copies are necessary for mixedness testing in the fully unrestricted setting.The section presents this as an alternate proof using Lemma 5.3 with α = 0 and the hard instance from Definition 5.5.Source: E Centralized mixedness testing lower… · p. 64
• The proof bounds the moment generating function of Z(z, z′) = d·tr(Δ̄_zΔ̄_z′), using N_z = min{1, 1/(d‖Δ_z‖∞)}.The passage notes that N_z equals 1 except with exponentially small probability, as shown in [LA24a, Lemma B.8].Source: E Centralized mixedness testing lower… · pp. 64–65

F Exponential separations from shared entanglement

• With two copies, Bell sampling gives constant-complexity solutions to purity testing and unsigned Pauli shadow tomography, unlike the exponentially costly non-adaptive single-copy setting.The section says this separation extends to tasks efficiently solvable via Bell sampling and hard for non-adaptive single-copy measurements.Source: F Exponential separations from shared… · p. 65
• A Bell sample is the outcome of measuring two copies of ρ in the Bell basis; the Bell states form an orthonormal basis.Bell sampling is also identified as a standard procedure for quantum learning and testing.Source: F Exponential separations from shared… · p. 65
• Two nodes can exactly sample from p_ρ by Bell-measuring each state copy with its half of shared EPR pairs, sending outcomes to the center, and having it output their XOR.The central node's output is distributed according to p_ρ.Source: F Exponential separations from shared… · pp. 65–67
• Ω(2^(n/2)) nodes are needed for purity testing with unbounded classical communication and shared randomness, while O(1) suffice with 2n-bit messages and n shared EPR pairs.The task is to distinguish a pure state from the maximally mixed state.Source: F Exponential separations from shared… · p. 65
• The nodes cannot complete teleportation because they cannot communicate corrections to each other, so they send those corrections to the central node instead.The construction is inspired by quantum teleportation, but disallows even classical communication between the two distributed nodes.Source: F Exponential separations from shared… · p. 66