Technical Summary: Distributed Property Testing with (Quantum) Carrier Pigeons

1. Problem Statement

This paper addresses the problem of distributed quantum state certification. In this setting, a central referee node possesses a complete classical description of a known quantum state $\sigma$, while $m$ distributed nodes each hold a single copy of an unknown quantum state $\rho$. The distributed nodes are spatially separated and cannot communicate with one another; they can only send limited one-way communication to the central node.

The goal is to determine the minimum number of distributed nodes $m$ (sample complexity) required for the central node to distinguish, with high probability, between two cases:

1. Identity: $\rho = \sigma$.
2. Farness: $\|\rho - \sigma\|_1 \geq \varepsilon$, where $\|\cdot\|_1$ denotes the trace distance.

The communication model is defined by the $(n_c, n_q, R)$ framework, where:

• $n_c$: The number of classical bits each node can send.
• $n_q$: The number of qubits (or dimension of qudits) each node can send.
• $R \in \{\text{public}, \text{private}\}$: Whether nodes share a public source of randomness or possess only private randomness.

The paper focuses on the regime where $n_c + n_q < \log d$ (where $d$ is the dimension of the state), as the problem is trivial if nodes can send the full state ($n_q \geq \log d$) or perform full measurements ($n_c \geq \log d$).

2. Methodology and Techniques

Lower Bound Techniques

The authors extend the framework introduced by Doosti et al. [DSW26], which utilized $\chi^2$-divergence to establish conditional lower bounds under the assumption of "mixedness preservation" (i.e., the channel maps the maximally mixed state to a maximally mixed state).

To remove this restrictive assumption and handle general protocols, the paper introduces several key technical innovations:

• Symmetrized $\chi^2$-Divergence: Instead of the standard $\chi^2$-divergence used in prior work, the authors employ a symmetrized version ($\alpha = 1/2$). This variant possesses more amenable properties for the proof and allows for the removal of the mixedness-preserving assumption.
• Quantum Instruments: To model the simultaneous transmission of classical and quantum information, the authors utilize quantum instruments rather than simple quantum channels. A quantum instrument maps an input state to a classical-quantum (CQ) state, outputting both a classical string and a quantum state.
• Augmented Channels/Instruments: A central technical hurdle in prior work was evaluating the inverse of the output state of the maximally mixed state under a channel. The authors define an "augmented" map $\Psi(X) = \tau^{-1/4}\Phi(X)\tau^{-1/4}$ (where $\tau$ is the output of the maximally mixed state). This transformation allows the analysis to proceed without requiring $\tau$ to be maximally mixed.
• Hard Instance Construction: The lower bounds rely on constructing "almost-$\varepsilon$ perturbations" of the maximally mixed state. The authors show that distinguishing these perturbations from the maximally mixed state is information-theoretically hard unless $m$ is sufficiently large.

Upper Bound Techniques

The paper provides matching (or near-matching) upper bounds through the design of specific algorithms:

• Private-Coin (No Classical Communication): The algorithm utilizes the Hilbert-Schmidt (HS) estimator (from Badescu et al. [BOW19]) as a subroutine. The core challenge in the private-coin setting is that nodes cannot agree on unitaries using public randomness. The authors prove the existence of a "good" set of unitaries that preserve the HS distance between $\rho$ and $\sigma$ up to constant factors. Nodes pre-agree on this deterministic set, and the central node estimates the distance after the states have been rotated by these unitaries.
• Public-Coin (Mixed Communication): The algorithm leverages Haar instruments. These instruments are constructed by sampling a Haar-random unitary, conjugating the state, tracing out a register, and measuring a classical register.
  • Variance Reduction: The authors analyze the BOW (Badescu-O'Donnell-Wright) estimator for CQ states. They show that if the quantum instrument spreads the probability mass uniformly over the classical labels (i.e., the probability of each classical string is $O(1/K)$), the variance of the estimator improves significantly, depending inversely on the number of classical strings $K = 2^{n_c}$.
  • Compression Property: The authors prove that Haar instruments do not contract the Hilbert-Schmidt distance too much, ensuring that the distinction between $\rho = \sigma$ and $\|\rho - \sigma\|_1 \geq \varepsilon$ remains detectable.

3. Key Results

The paper establishes tight or near-tight bounds on the sample complexity $m$ for $\varepsilon$-certification of $d$-dimensional states. Let $d_q = 2^{n_q}$ and $K = 2^{n_c}$.

Lower Bounds (Unconditional)

The authors prove unconditional lower bounds, removing the "mixedness-preserving" assumption required in previous work:

• Public-Coin: $m = \Omega\left(\frac{d^2}{2^{n_q} \cdot 2^{n_c/2} \cdot \varepsilon^2}\right)$.
• Private-Coin: $m = \Omega\left(\frac{d^3}{2^{2n_q} \cdot 2^{n_c} \cdot \varepsilon^2}\right)$.

These results confirm the conjecture by Doosti et al. that the previous conditional bounds were tight for all protocols.

Upper Bounds

• Public-Coin (General): The paper presents an algorithm achieving $m = O\left(\frac{d^2}{2^{n_q} \cdot 2^{n_c/2} \cdot \varepsilon^2}\right)$. This matches the lower bound exactly, establishing the optimal sample complexity for the public-coin setting with both classical and quantum communication.
• Private-Coin (Quantum Only): The paper presents an algorithm achieving $m = O\left(\frac{d^3}{2^{2n_q} \cdot \varepsilon^2} \log d\right)$. This matches the lower bound up to a single logarithmic factor.

Summary Table of Bounds

Setting	Lower Bound	Upper Bound
Public-Coin (Quantum + Classical)	$\Omega\left(\frac{d^2}{2^{n_q + n_c/2}\varepsilon^2}\right)$	$O\left(\frac{d^2}{2^{n_q + n_c/2}\varepsilon^2}\right)$ (Tight)
Private-Coin (Quantum Only)	$\Omega\left(\frac{d^3}{2^{2n_q}\varepsilon^2}\right)$	$O\left(\frac{d^3}{2^{2n_q}\varepsilon^2} \log d\right)$ (Near-Tight)

4. Significance and Claims

The paper claims to essentially settle the question of sample complexity for distributed quantum state certification in all settings except one.

1. Resolution of Conjectures: The work confirms the conjecture by Doosti et al. that their lower bounds are tight even without the mixedness-preserving assumption.
2. Optimality in Public-Coin: The paper provides the first optimal algorithm for the public-coin setting with mixed communication, demonstrating that classical bits can significantly reduce the sample complexity (by a factor of $2^{n_c/2}$) when combined with quantum communication.
3. Novelty of Quantum Instruments: The authors highlight that this is the first application of quantum instruments in the learning/testing setting. They establish novel results regarding the properties of these instruments (e.g., the "augmented" map and compression properties) which may be of independent interest.
4. Limitations and Open Problems: The authors modestly note that the private-coin algorithm with mixed communication remains an open problem. Their public-coin approach relies on sampling unitaries based on public randomness to ensure "good" spreading of probability mass; this does not directly generalize to the private-coin setting where unitaries must be fixed beforehand and work uniformly for all states. Additionally, the logarithmic factor in the private-coin quantum-only upper bound is attributed to the Matrix Chernoff bound used to prove the existence of good unitaries, and it is unclear if this can be removed.