Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.05962

Distributed Quantum Property Testing with Communication Constraints

Mina Doosti, Ryan Sweke, Chirag Wadhwa

quant-phcs.DSSubmitted Apr 7, 2026• Announced Apr 8, 2026• 0 citations
arXivHTMLPDF

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.

Comments
33 pages, 1 figure, 1 table

Related papers

Distributed Quantum Property Testing with Quantum Carrier Pigeons

Kenny Chen, Mina Doosti, Ryan Sweke +1 more

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.

quant-pharXiv:2609.08864•Sep 9, 2026•0 citations

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

Kenny Chen

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.

quant-pharXiv:2606.31753•Jul 1, 2026•0 citations

Optimal Quantum State Testing Even with Limited Entanglement

Chirag Wadhwa, Sitan Chen

In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $ρ$, test whether it matches some target state $σ$ or is $ε$-far from it. For certifying $d$-dimensional states, $Θ(d/ε^2)$ copies of $ρ$ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all $O(d/ε^2)$ copies of $ρ$. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on $t$ copies at once, for some $1 < t \ll d/ε^2$. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d^2$. In the high-precision regime, i.e., for $ε< \frac{1}{\sqrt{d}}$, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d^2$ as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take $t \geq Ω(d^2)$ to achieve the optimal rate for certification.

quant-pharXiv:2604.07460•Apr 10, 2026•0 citations

Distributed quantum certification with Clifford encoders

HyunHo Cha

Quantum state certification concerns a resource-efficient way to verify whether a quantum device produces a prescribed target state without reconstructing the state in full, making it a fundamental primitive for validating quantum systems. We consider the private-coin model with only quantum communication, where the parties have no shared randomness or preshared entanglement, and no additional classical communication is allowed. We establish the optimal sample complexity, thereby closing the logarithmic gap between the previously established upper and lower bounds in this model. Remarkably, our upper bound attains the log-free optimum using a fixed family of Clifford encoders. Thus, optimal distributed state certification under private coins and quantum-only communication does not require general quantum encoders.

•Sep 16, 2026•0 citations

The role of shared randomness in quantum state certification with unentangled measurements

Liu, Yuhan, Jayadev Acharya

Given $n$ copies of an unknown quantum state $ρ\in\mathbb{C}^{d\times d}$, quantum state certification is the task of determining whether $ρ=ρ_0$ or $\|ρ-ρ_0\|_1>\varepsilon$, where $ρ_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $ρ$ at a time. When there is a common source of shared randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $Θ(d^{3/2}/\varepsilon^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that $Θ(d^2/\varepsilon^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without shared randomness. We develop a unified lower bound framework for both fixed and randomized measurements, under the same theoretical framework that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.

arXiv:2401.09650•Jan 17, 2024•0 citations

Strong converse bounds in quantum network information theory: distributed hypothesis testing and source coding

Hao–Chung Cheng, Nilanjana Datta, Cambyse Rouzé

We consider a distributed quantum hypothesis testing problem with communication constraints, in which the two hypotheses correspond to two different states of a bipartite quantum system, multiple identical copies of which are shared between Alice and Bob. They are allowed to perform local operations on their respective systems and send quantum information to Charlie at limited rates. By doing measurements on the systems that he receives, Charlie needs to infer which of the two different states the original bipartite state was in, that is, which of the two hypotheses is true. We prove that the Stein exponent for this problem is given by a regularized quantum relative entropy. The latter reduces to a single letter formula when the alternative hypothesis consists of the products of the marginals of the null hypothesis, and there is no rate constraint imposed on Bob. Our proof relies on certain properties of the so-called quantum information bottleneck function. The second part of this paper concerns the general problem of finding finite blocklength strong converse bounds in quantum network information theory. In the classical case, the analogue of this problem has been reformulated in terms of the so-called image size characterization problem. Here, we extend this problem to the classical-quantum setting and prove a second order strong converse bound for it. As a by-product, we obtain a similar bound for the Stein exponent for distributed hypothesis testing in the special case in which the bipartite system is a classical-quantum system, as well as for the task of quantum source coding with compressed classical side information. Our proofs use a recently developed tool from quantum functional inequalities, namely, the tensorization property of reverse hypercontractivity for the quantum depolarizing semigroup.

arXiv:1905.00873•May 2, 2019•9 citations
We introduce a framework for distributed quantum inference under communication constraints. In our model, mmm distributed nodes each receive one copy of an unknown ddd-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≥ε\|ρ-σ\|_1\geq ε∥ρ−σ∥1​≥ε. 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 nq≤log⁡dn_q\leq \log dnq​≤logd qubits, then the sample complexity of distributed state certification is O(d22nqε2)\mathcal{O}(\frac{d^2}{2^{n_q}ε^2})O(2nq​ε2d2​) 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 Ω(d34nqε2)Ω(\frac{d^3}{4^{n_q} ε^2})Ω(4nq​ε2d3​) 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.
We introduce a framework for distributed quantum inference under communication constraints. In our model, mmm distributed nodes each receive one copy of an unknown ddd-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≥ε\|ρ-σ\|_1\geq ε∥ρ−σ∥1​≥ε. 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 ncn_cnc​ bits and nqn_qnq​ qubits with nc+nq≤log⁡dn_c + n_q \leq \log dnc​+nq​≤logd. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is Θ(d22nq2nc/2ε2)Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})Θ(2nq​2nc​/2ε2d2​). We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(d34nq2ncε2)Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})Ω(4nq​2nc​ε2d3​) lower bound in the private-coin\textit{private-coin}private-coin setting. Moreover, we develop a private-coin algorithm that matches this bound up to a log⁡d\sqrt{\log d}logd​ 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.
Recently, Doosti et al. introduced the problem of distributed quantum state verification, where mmm 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 mmm are required, before the central node can succeed at distinguishing whether ρ=σρ=σρ=σ or ∥ρ−σ∥1≥ε\|ρ-σ\|_1\geq\varepsilon∥ρ−σ∥1​≥ε 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.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state ρρρ, test whether it matches some target state σσσ or is εεε-far from it. For certifying ddd-dimensional states, Θ(d/ε2)Θ(d/ε^2)Θ(d/ε2) copies of ρρρ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/ε2)O(d/ε^2)O(d/ε2) copies of ρρρ. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on ttt copies at once, for some 1<t≪d/ε21 < t \ll d/ε^21<t≪d/ε2. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of ttt, which achieves a near-optimal rate at t=d2t = d^2t=d2. In the high-precision regime, i.e., for ε<1dε< \frac{1}{\sqrt{d}}ε<d​1​, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at t=d2t = d^2t=d2 as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take t≥Ω(d2)t \geq Ω(d^2)t≥Ω(d2) to achieve the optimal rate for certification.
Quantum state certification concerns a resource-efficient way to verify whether a quantum device produces a prescribed target state without reconstructing the state in full, making it a fundamental primitive for validating quantum systems. We consider the private-coin model with only quantum communication, where the parties have no shared randomness or preshared entanglement, and no additional classical communication is allowed. We establish the optimal sample complexity, thereby closing the logarithmic gap between the previously established upper and lower bounds in this model. Remarkably, our upper bound attains the log-free optimum using a fixed family of Clifford encoders. Thus, optimal distributed state certification under private coins and quantum-only communication does not require general quantum encoders.
Given nnn copies of an unknown quantum state ρ∈Cd×dρ\in\mathbb{C}^{d\times d}ρ∈Cd×d, quantum state certification is the task of determining whether ρ=ρ0ρ=ρ_0ρ=ρ0​ or ∥ρ−ρ0∥1>ε\|ρ-ρ_0\|_1>\varepsilon∥ρ−ρ0​∥1​>ε, where ρ0ρ_0ρ0​ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of ρρρ at a time. When there is a common source of shared randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that Θ(d3/2/ε2)Θ(d^{3/2}/\varepsilon^2)Θ(d3/2/ε2) copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that Θ(d2/ε2)Θ(d^2/\varepsilon^2)Θ(d2/ε2) copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without shared randomness. We develop a unified lower bound framework for both fixed and randomized measurements, under the same theoretical framework that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.
We consider a distributed quantum hypothesis testing problem with communication constraints, in which the two hypotheses correspond to two different states of a bipartite quantum system, multiple identical copies of which are shared between Alice and Bob. They are allowed to perform local operations on their respective systems and send quantum information to Charlie at limited rates. By doing measurements on the systems that he receives, Charlie needs to infer which of the two different states the original bipartite state was in, that is, which of the two hypotheses is true. We prove that the Stein exponent for this problem is given by a regularized quantum relative entropy. The latter reduces to a single letter formula when the alternative hypothesis consists of the products of the marginals of the null hypothesis, and there is no rate constraint imposed on Bob. Our proof relies on certain properties of the so-called quantum information bottleneck function. The second part of this paper concerns the general problem of finding finite blocklength strong converse bounds in quantum network information theory. In the classical case, the analogue of this problem has been reformulated in terms of the so-called image size characterization problem. Here, we extend this problem to the classical-quantum setting and prove a second order strong converse bound for it. As a by-product, we obtain a similar bound for the Stein exponent for distributed hypothesis testing in the special case in which the bipartite system is a classical-quantum system, as well as for the task of quantum source coding with compressed classical side information. Our proofs use a recently developed tool from quantum functional inequalities, namely, the tensorization property of reverse hypercontractivity for the quantum depolarizing semigroup.