Distributed Quantum Property Testing with Quantum Carrier Pigeons

Abstract

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $\rho$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $\rho$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $\sigma$, decide whether $\rho =\sigma$ or $\Vert \rho -\sigma {\Vert }_1\ge \epsilon$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c+n_q\le \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $\Theta (\frac{d^2}{2^{n_q}{2}^{n_c/2}{\epsilon }^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $\Omega (\frac{d^3}{4^{n_q}{2}^{n_c}{\epsilon }^2})$ lower bound in the $\text{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

Merges and subsumes arXiv:2604.05962 and arXiv:2606.31753, and includes additional/improved results. 67 pages, 1 figure, 1 table