{"ID":5443788,"CreatedAt":"2026-07-01T02:07:11.383974684Z","UpdatedAt":"2026-07-03T14:41:59.01997188Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31753","arxiv_id":"2606.31753","title":"Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification","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.","short_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 r...","url_abs":"https://arxiv.org/abs/2606.31753","url_pdf":"https://arxiv.org/pdf/2606.31753v1","authors":"[\"Kenny Chen\"]","published":"2026-06-30T14:43:49Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[]","has_code":false}