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 $\|\rho-\sigma\|_1\geq \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 \leq \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 $\textit{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

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)

arXiv:2609.08864 [quant-ph]

(or arXiv:2609.08864v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.08864 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.