Skip to content
Preprint

Distributed Quantum Property Testing with Quantum Carrier Pigeons

Sep 2026 · 1 citation
Physics Computer Science

TL;DR

It is demonstrated that shared randomness is necessary to achieve the complexity of distributed state certification with limited communication, and an $\Omega$ lower bound in the $\textit{private-coin}$ setting is proved.

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.

View source

Similar papers

Preprint Oct 2026

Efficient Quantum State Identity Testing

This work presents two quantum algorithms with complementary guarantees on circuit depth and sample complexity and proves a matching sample complexity lower bound of $\Omega(\log(n/\delta))$ for any quantum algorithm with failure probability at most $\delta\le 1/2-c$.

Shih-Han Hung, Ming-Hsien Tsai · 0 citations
Preprint Sep 2026

On the Limits of Quantum Multiparty Simultaneous Communication

The results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k, and prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.

Pedro Montealegre, I. Rapaport, Jorge Valenzuela · 0 citations
Sep 2026

Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games

Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with er...

F. Holler, Anand Natarajan · 0 citations
Preprint Aug 2026

Classical Commitment over Quantum Channels with Limited Entanglement Assistance

We study classical string commitment over quantum channels with limited preshared entanglement. For noninteractive protocols, we determine the commitment capacity of a class of channels with input dimension $d$ that, at each use, sample a pair of classical random variables $(F,Z)$, apply one of the $d^2$ Heisenberg--We...

Re-Mi A. Chou · 0 citations
Preprint Oct 2026

Optimal and Verifiable Quantum Advantages in Communication Complexity

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $\Omega(2^n)$ bits of communication. We...

Ryan A. Anselm, Michelle Ding, D. Gilboa et al. · 1 citation
Preprint Oct 2026

On State Distinguishing Without Inverse Queries

In the quantum state distinguishing problem, an algorithm is given copies of a state $|\psi\rangle$ or $|\phi\rangle$ separated by trace distance $\varepsilon$, and tasked with deciding which is the case. It is a standard result that $\Theta(\varepsilon^{-2})$ copies are required, while having access to a unitary state...

Emma Wang, Joseph Carolan, Andrew M. Childs · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.