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

Distributed quantum certification with Clifford encoders

HyunHo Cha

Published Sep 16, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.22788376

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•1 citation

Distributed Quantum Property Testing with Communication Constraints

Mina Doosti, Ryan Sweke, Chirag Wadhwa

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.

quant-pharXiv:2604.05962•Apr 8, 2026•4 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•1 citation

Quantum Encodings, Private Messages, and Communication Complexity

Tom Gur, Miryam Mi-Ying Huang, Er-Cheng Tang

We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping $n$ to $m$ qubits, we give a QPSM protocol with quantum communication $m$, using exponential pre-shared entanglement. In particular, constant-output channels have $O(1)$ quantum communication, and classical-output channels require no quantum communication. (2) With $O(n)$ pre-shared entanglement, every one-qubit-output channel has an $O(n)$-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant $c>0$ for which any protocol with at most $cn$ pre-shared entanglement requires $Ω(n)$ quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with $O(n)$ pre-shared entangled qubits and only $O(1)$ quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.

quant-pharXiv:2609.17690•Sep 17, 2026•1 citation

New bounds on private simultaneous quantum message passing

Uma Girish, Alex May, Natalie Parham +1 more

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then each send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $ε$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones.

quant-pharXiv:2606.12557•Jun 12, 2026•3 citations

On communication over an entanglement-assisted quantum channel. (arXiv:quant-ph/0206122v1 CROSS LISTED)

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

•Mar 21, 2018•0 citations
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.
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.
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.
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.
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping nnn to mmm qubits, we give a QPSM protocol with quantum communication mmm, using exponential pre-shared entanglement. In particular, constant-output channels have O(1)O(1)O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n)O(n)O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)O(n)O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0c>0c>0 for which any protocol with at most cncncn pre-shared entanglement requires Ω(n)Ω(n)Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n)O(n)O(n) pre-shared entangled qubits and only O(1)O(1)O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.
In the private simultaneous message (PSM) setting, kkk players obtain inputs xi∈{0,1}nx_i\in\{0,1\}^nxi​∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk)f(x_1,...,x_k)f(x1​,...,xk​) but no other information about (x1,...,xk)(x_1,...,x_k)(x1​,...,xk​). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for kkk-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2)f(x_1,x_2)f(x1​,x2​) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting sss be the size of a quantum circuit computing fff, dfd_fdf​ be the circuit depth, kkk the number of players, nnn the number of bits received by each player, and εεε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅log⁡O(df)(s/ε)\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)PSMk∗​(f)≤(kn+s)⋅logO(df​)(s/ε). 2) The square of the Fourier 1 norm of fff, ∥f^∥12\Vert \hat{f}\Vert_1^2∥f^​∥12​, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12)\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)PSM(f)≤O(∥f^​∥12​). In proving the first upper bound, we generalize existing TTT-depth based techniques for NLQC from 222 to k≥2k\geq 2k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.