Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification

• URL: http://arxiv.org/abs/2606.31753v2
• Date: Fri, 03 Jul 2026 08:32:33 GMT
• Title: Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification
• Abstract summary: 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.
• Score: 4.010371060637209
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, Doosti et al. introduced the problem of distributed quantum state verification, where $m$ distributed nodes are given a copy of an unknown state $ρ$, and can send limited one way communication to a central node, who has a complete description of a known state $σ$. They ask how many distributed nodes $m$ are required, before the central node can succeed at distinguishing whether $ρ=σ$ or $\|ρ-σ\|_1\geq\varepsilon$ with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.

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 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)
• Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy [4.843542453440025]
  We study one-way quantum communication lower bounds for search problems.<n>For collision finding, we prove a tight $(N1/4)$ one-way quantum communication lower bound.<n>For triangle finding, we prove a one-pass quantum streaming space lower bound of $left(sqrt_Vright)$ for graphs with $m$ edges, $(m)$ triangles, and constant $_E$.
  arXiv  Detail & Related papers  (2026-07-09T14:11:09Z)
• 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)
• The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the multimode extreme bosonic Gaussian channels [53.253900735220796]
  Inequality determines the minimum conditional von Neumann entropy of the output of the most general linear mixing of bosonic quantum modes.<n>Bosonic quantum systems constitute the mathematical model for the electromagnetic radiation in the quantum regime.
  arXiv  Detail & Related papers  (2024-10-18T13:59:50Z)
• 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)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Two instances of random access code in the quantum regime [0.09545101073027092]
  We consider two classes of quantum generalisations of Random Access Code (RAC) First class is based on a random access code with quantum inputs and output known as No-Signalling Quantum RAC (NS-QRAC) Second class is based on a random access code with a quantum channel and shared entanglement.
  arXiv  Detail & Related papers  (2022-08-30T17:43:37Z)
• Quantum secure direct communication with private dense coding using general preshared quantum state [59.99354397281036]
  We study secure direct communication by using a general preshared quantum state and a generalization of dense coding. For a practical application, we propose a concrete protocol and derive an upper bound of information leakage.
  arXiv  Detail & Related papers  (2021-12-30T16:12:07Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• 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)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  A general attenuator $Phi_lambda, sigma$ is a bosonic quantum channel that acts by combining the input with a fixed environment state. We show that for any arbitrary value of $lambda>0$ there exists a suitable single-mode state $sigma(lambda)$. Our result holds even when we fix an energy constraint at the input of the channel, and implies that quantum communication at a constant rate is possible even in the limit of arbitrarily low transmissivity.
  arXiv  Detail & Related papers  (2020-03-19T16:50:11Z)

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.