Distributed Quantum Property Testing with Quantum Carrier Pigeons

• URL: http://arxiv.org/abs/2609.08864v1
• Date: Tue, 08 Sep 2026 15:09:45 GMT
• Title: Distributed Quantum Property Testing with Quantum Carrier Pigeons
• Abstract summary: We introduce a framework for distributed quantum inference under communication constraints.<n>We focus on the fundamental problem of quantum state certification.<n>We show that the copy complexity of distributed state certification is $(fracd22n_q 2n_c/22)$.
• Score: 2.764897610820182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
  We establish a multiparty exponential separation through $nameIC_k,n$, a natural $k$-party generalization of textscIndex Coordination.<n>We show that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$.
  arXiv  Detail & Related papers  (2026-09-09T15:07:22Z)
• Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification [4.010371060637209]
  We show conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting.<n>We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.
  arXiv  Detail & Related papers  (2026-06-30T14:43:49Z)
• Optimal GHZ-State Distribution in LOSR Quantum Networks via Local Decoding from Information Sets [40.76168869865134]
  We prove the conjecture for regular and uniform networks of arbitrary size.<n>By identifying the hyperedges of the network with the coordinates of a linear code, we show that whenever the edges incident to each node form an information set, a fixed collection of local unitaries transforms the source state into an (N)-party GHZ state with fidelity (dm-M)<n>These results demonstrate that multipartite sources, together with shared randomness, can replace real-time classical communication for entanglement distribution.
  arXiv  Detail & Related papers  (2026-06-19T14:53:28Z)
• Distributed Quantum Property Testing with Communication Constraints [0.0]
  We introduce a framework for distributed quantum inference under communication constraints.<n>In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $$.<n>We show that when each communication channel is limited to only $n_qleq log d$ qubits, the sample complexity of distributed state certification is $mathcalO(fracd22n_q2)$ when public randomness is available to all nodes.
  arXiv  Detail & Related papers  (2026-04-07T14:56:27Z)
• Universal Nested Quantum Switch [0.15293427903448023]
  We show that the same functionality can be achieved with a different geometry that does not rely on a powerful and large central unit.<n>We provide a nested construction with logarithmically many qubits per node and a total of $O(nlog n)$ Bell pairs.<n>We also present a graph state variant with just one qubit per node, which allows one to generate $O(n/log2 n)$ Bell pairs.
  arXiv  Detail & Related papers  (2026-02-27T19:00:10Z)
• Scalable Multi-QPU Circuit Design for Dicke State Preparation: Optimizing Communication Complexity and Local Circuit Costs [13.575071625377097]
  The number of qubits available on a single quantum processing unit (QPU) is limited.<n>We investigate the distributed preparation of large-qubit Dicke states $D(n,k)$ across a general number $p$ of QPUs.<n>To the best of our knowledge, this is the first construction to simultaneously achieve logarithmic communication complexity and circuit size and depth.
  arXiv  Detail & Related papers  (2026-01-28T09:00:38Z)
• Coherence in Property Testing: Quantum-Classical Collapses and Separations [42.44394412033434]
  We show that no tester can distinguish subset states of size $2n/8$ from $2n/4$ with probability better than $2-Theta(n)$.<n>We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
  arXiv  Detail & Related papers  (2024-11-06T19:52:15Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Rank lower bounds on non-local quantum computation [0.0]
  A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement.<n>We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
  arXiv  Detail & Related papers  (2024-02-28T19:00:09Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.