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

Kenny Chen · 2026

Read Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification by Kenny Chen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31753.txt.

Introduction

Chen studies distributed quantum state certification, where many separated nodes each hold one copy of an unknown state. A central referee knows the target state completely but receives only limited one-way messages. The question is how many nodes are needed before the referee can tell whether the unknown state matches the target or sits far from it.

Earlier work by Doosti and others gave conditional lower bounds when only quantum messages were allowed. Chen proves unconditional lower bounds that hold when classical and quantum communication are both permitted. The public-coin lower bound is matched by an explicit algorithm, making it tight. For the private-coin setting with quantum-only messages, Chen gives an almost tight upper bound as well.

Catalog record

CREATORKenny Chen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.31753

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification Kenny Chen Abstract Recently, Doosti et al. introduced the problem of distributed quantum state verification, where m m distributed nodes are given a copy of an unknown state ρ \rho , and can send limited one way communication to a central node, who has a complete description of a known state σ \sigma . They ask how many distributed nodes m m are required, before the central node can succeed at distinguishing whether ρ = σ \rho=\sigma or ‖ ρ − σ ‖ 1 ≥ ε \|\rho-\sigma\|_{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. 1 Introduction This paper is concerned with the task of (quantum) state certification: that is, the task of checking whether an unknown state \rho is identical to a known state \sigma , or whether it is “far” from it. Formally, it is defined as follows: Definition 1.1 (Quantum State Certification) . Given \varepsilon,\delta\in(0,1] , a complete classical description of a quantum state \sigma , an algorithm is said to (\varepsilon,\delta) -certify \sigma if, given multiple copies of an unknown state \rho , it satisfies the following: 1. If \rho=\sigma , the algorithm outputs “ accept ” with probability at least 1-\delta ; 2. If \|\rho-\sigma\|_{1}\geq\varepsilon , the algorithm outputs “ reject ” with probability at least 1-\delta . When \delta is set to 1/3 , we simply say that the algorithm \varepsilon -certifies \sigma . The number of copies of the unknown state \rho (in the worst case over \rho,\sigma ) is said to be the sample complexity of the algorithm. The distance measure above is the trace distance, and while the computational complexity of the algorithm is important in its own right, the main focus is typically the sample complexity of the task as a function of \varepsilon,\delta and the dimension d (defined as the minimum sample complexity of any algorithm for (\varepsilon,\delta) -certification). This quantity is indeed of particular importance in the quantum setting, since, due to the no cloning theorem, obtaining a large number of a state \rho is generally very difficult, so algorithms should aim to be very efficient in the number of copies required. This problem has been very well studied in a variety of settings, with tight bounds known, see [ 21 ] and [ 4 ] , establishing that this task needs \Theta\left(\frac{d}{\varepsilon^{2}}\right) copies of \rho . However, these settings assume the tester themselves have access to the unknown state \rho . In practice, the verifier, who has \sigma , may be physically separated from the party, or parties, that have \rho . In this sense, it is not possible for the certifier themselves to perform operations on \rho , and they need to rely on other parties to do that processing for them. The results are then sent to the central node by the other parties, which then allows them to perform the certification. There is also nuance in this communication though, being that specifically quantum communication is difficult. Indeed, states are delicate and easily disturbed, and our quantum carrier pigeons may need to travel large distances, so we ought not burden them with more communications than is necessary. This raises the main question of this paper: Given several parties, each holding one copy of \rho and located away from the main certifier, who has \sigma , with limited information being able to be transmitted to the central certifier, how many copies of \rho are needed for them to perform quantum state certification successfully? Aiming to formalize this type of questions, Doosti et al. [ 9 ] recently introduced the setting of distributed quantum property testing . Here copies of an unknown quantum state are given to multiple distributed nodes, all of which can process the quantum state, then communicate to a central referee node whose task is, after obtaining the information from the distributed nodes, to run a learning or testing algorithm to determine some property of the unknown quantum state. Definition 1.2 (Distributed Quantum Inference) . The (n_{c},n_{q},R) 1 1 1 Doosti et al. actually define an even more general model where entanglement is allowed between distributed nodes, with an extra parameter E quantifying the number of entangled qubits shared among distributed nodes. However, we never deal with entanglement in this paper, and hence omit it in this definition. model of distributed quantum inference is the model where no communication is allowed between distributed nodes, one-way communication is allowed from distributed nodes to the central node, and: 1. Each of the distributed nodes may communicate at most n_{c} classical bits and n_{q} qubits to the central node. 2. R\in\{\text{public, private}\} denotes whether all nodes only have access to a private source of randomness (private-coin protocols), or if all nodes have access to a shared public source of randomness (public-coin protocols). The resource we seek to minimize is the number of distributed nodes m to solve the prespecified task at hand. It is worth discussing here the parameter regimes of n_{q} and n_{c} that make this problem interesting and nontrivial. We paraphrase this discussion from that of Doosti et al. [ 9 ] : • If n_{q}\geq n , then each distributed node can simply send the entire quantum state to the central node. Then, this is equivalent to the regular problem of quantum state certification, which is fully characterized by Badescu et al. [ 4 ] . • If n_{q}=0 but n_{c}\geq n , each distributed node can perform a single copy measurement, and send it to the classical node to postprocess. Then, this is equivalent to state certification with nonadaptive single-copy measurements, which is fully characterized by Chen et al. [ 6 ] • If n_{q}=0 and n_{c}<n , this setting is equivalent to the above single copy measurement setting, with additional communication restrictions. Namely, the measurement operators can only have 2^{n_{c}} outcomes. This setting is also fully characterized by Liu et al. [ 15 ] . Hence, the interesting parameter regime is the one where n_{c}+n_{q}<n , which is the one we focus on. More broadly, this problem is the quantum analogue of classical distributed property testing, and the quantum generalization of the framework of Acharya et al. [ 1 ] . This model, quite natural to consider in view of the increased interest in distributed quantum computing [ 5 ] , aligns with the motivation outlined above: and indeed, the flagship problem Doosti et al. focused on to illustrate this distributed model is that of quantum state certification, as introduced above (and which itself is the quantum generalization of distributed identity testing for classical probability distributions). Translating state certification into the distributed quantum inference setting, the m distributed nodes each

Read the complete text