Distributed Quantum Property Testing with Communication Constraints

• URL: http://arxiv.org/abs/2604.05962v1
• Date: Tue, 07 Apr 2026 14:56:27 GMT
• Title: Distributed Quantum Property Testing with Communication Constraints
• Abstract summary: 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.
• Score: 0.0
• 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 [COLT2019], 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 quantum communication between distributed nodes and the central node. We show that when each communication channel is limited to only $n_q\leq \log d$ qubits, then the sample complexity of distributed state certification is $\mathcal{O}(\frac{d^2}{2^{n_q}ε^2})$ when public randomness is available to all nodes. Moreover, under the assumption that the channels used by the distributed nodes are mixedness-preserving, we prove a matching lower bound. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} ε^2})$ lower bound in the private-coin setting under the same assumption as above. Our lower bounds leverage a recently introduced quantum analogue of the celebrated Ingster-Suslina method and generalize arguments from the classical setting. Together, our work provides the first characterization of distributed quantum state certification in the regime of limited quantum communication and establishes a general framework for distributed quantum inference with communication constraints.

Related papers

• Distributed Quantum Property Testing with Quantum Carrier Pigeons [2.764897610820182]
  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)$.
  arXiv  Detail & Related papers  (2026-09-08T15:09:45Z)
• A lower bound on the classical simulation cost of star-network correlations [0.0]
  We study the quantum communication complexity of correlations arising from joint measurements on quantum systems distributed across a star network.<n>We show that no finite-size classical description of a qubit suffices to reproduce the statistics of a joint measurement on sufficiently many qubits.
  arXiv  Detail & Related papers  (2026-08-04T17:51:05Z)
• 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)
• Asymptotic Limits of Entanglement Distribution [43.748379918040854]
  We investigate the limits of entanglement distribution across quantum networks utilizing intermediate stations and local operations.<n>We establish a strict dichotomy: the preservation of entanglement over arbitrarily long distances is possible if the underlying quantum channel admits a correctable subspace.<n>We derive a fundamental lower bound on the physical resource requirements, proving that for channels without a correctable subspace, the number of parallel channels per link must scale at least logarithmically with the number of intermediate stations to sustain a non-zero amount of entanglement.
  arXiv  Detail & Related papers  (2026-05-22T09:56:38Z)
• Hysteretic squashed entanglement in many-body quantum systems [42.085941481155295]
  Entanglement in many-body quantum systems is distributed across spatial regions.<n>We propose hysteretic entanglement $T_sq$, a conditional entanglement that measures the genuine quantum correlations between two subregions.<n>We show that $T_sq$ can detect genuine quantum correlations across both adjacent and long-range subsystems.
  arXiv  Detail & Related papers  (2026-03-10T17:00:49Z)
• Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model [0.5074812070492739]
  We present new distributed quantum algorithms for fundamental distributed computing problems.<n>These problems include leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks.<n>The message complexity of our algorithms is $tildeO(n)$ for leader election, broadcast, and MST, and $tildeO(sqrtmn)$ for BFS.
  arXiv  Detail & Related papers  (2026-02-17T12:10:12Z)
• Extendible quantum measurements and limitations on classical communication [4.7846581583644525]
  Unextendibility of quantum states and channels is inextricably linked to the no-cloning theorem of quantum mechanics.<n>We define $k$-extendible measurements for every integer $kge 2$.
  arXiv  Detail & Related papers  (2024-12-24T17:12:45Z)
• Quantum Homogenization as a Quantum Steady State Protocol on NISQ Hardware [42.52549987351643]
  Quantum homogenization is a reservoir-based quantum state approximation protocol.<n>We extend the standard quantum homogenization protocol to the dynamically-equivalent ($mathttSWAP$)$alpha$ formulation.<n>We show that our proposed protocol yields a completely positive, trace preserving (CPTP) map under which the code subspace is correctable.
  arXiv  Detail & Related papers  (2024-12-19T05:50:54Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
  We propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem.<n>We provide unified proofs for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-08-03T14:41:49Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)
• 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.