Quantum state checking across networks with limited communication
Distributed Quantum Property Testing with Quantum Carrier Pigeons
Data Structures and Algorithms
Summary
Figuring out properties of quantum states shared across many locations is tricky when communication is limited. The authors introduce a way to tell if a quantum state matches a known one by sending only a small amount of information between nodes and a central hub. They show how the use of shared randomness and a combination of classical bits and quantum bits influences how many copies of the state are needed. Their results give clear limits on what can be done with or without shared randomness, helping to understand distributed quantum testing better.
quantum statedistributed inferencequantum communicationshared randomnesscopy complexitystate certificationprivate-coin protocolquantum bits (qubits)classical bitscommunication constraints
Authors
Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa
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 $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. 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 $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. 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 $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^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.