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:2609.17690

Quantum Encodings, Private Messages, and Communication Complexity

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

quant-phSubmitted Sep 15, 2026• Announced Sep 17, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations

Harumichi Nishimura

Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on $n$-bit inputs, which determines whether the players' $n$-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication $(1.633\ldots)n$ qubits, whereas every perfectly correct protocol without prior entanglement requires at least $3n$ qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication $3\log_2 3$. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every $k\geq 3$, we construct a perfectly correct and perfectly private one-shot protocol for $k$-bit AND using one qudit of dimension at most $k$ per player, and hence at most $k\log_2 k$ qubits in total.

quant-pharXiv:2610.23090•Oct 19, 2026•0 citations

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•0 citations

On the Limits of Quantum Multiparty Simultaneous Communication

Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

cs.CCCross-listedarXiv:2609.10289•Sep 10, 2026•0 citations

Trade-Offs Between Entanglement and Communication

Srinivasan Arunachalam, Uma Girish

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$: $Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tildeΘ(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. $R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tildeΘ(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. $R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tildeΘ(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.

arXiv:2306.01233•Leibniz international proceedings in informatics•Jan 1, 2023•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

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Atsuya Hasegawa, François Le Gall, Augusto Modanese

We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.

arXiv:2505.16457•May 22, 2025•0 citations
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.
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on nnn-bit inputs, which determines whether the players' nnn-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n(1.633\ldots)n(1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n3n3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log⁡233\log_2 33log2​3. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3k\geq 3k≥3, we construct a perfectly correct and perfectly private one-shot protocol for kkk-bit AND using one qudit of dimension at most kkk per player, and hence at most klog⁡2kk\log_2 kklog2​k qubits in total.
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.
We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of kkk players receives an unrestricted string xj∈{0,1}nx_j\in\{0,1\}^nxj​∈{0,1}n, and the referee must decide whether x1⊕⋯⊕xk=0nx_1\oplus\cdots\oplus x_k=0^nx1​⊕⋯⊕xk​=0n. For k≥8k\ge8k≥8 and worst-case error at most 1/31/31/3, we prove quantum lower bounds of Ω(min⁡{n,k2})Ω(\min\{n,k^2\})Ω(min{n,k2}) on total communication and Ω(min⁡{n/k,k})Ω(\min\{n/k,k\})Ω(min{n/k,k}) on maximum message length. A classical public-coin protocol uses two bits per player with error at most 1/41/41/4. For n=k2n=k^2n=k2 and worst-case error at most 1/31/31/3, we prove that quantum protocols require maximum message length Ω(n)Ω(\sqrt n)Ω(n​) qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a kkk-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of Ω(n1−1/k)Ω(n^{1-1/k})Ω(n1−1/k) on maximum message length, matched by a classical private-coin protocol. For any fixed error ε∈(0,1/8)\varepsilon\in(0,1/8)ε∈(0,1/8), we also prove a bounded-error quantum lower bound of Ω(n(k−1)/(k+1))Ω(n^{(k-1)/(k+1)})Ω(n(k−1)/(k+1)) while we show that public-coin protocols solve the relation unambiguously with maximum message length O(log⁡n)O(\log n)O(logn), giving exponential separations in both regimes. The implicit constants are independent of kkk, and both quantum lower bounds become linear when k≥clog⁡nk\ge c\log nk≥clogn for any fixed c>0c>0c>0.
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on nnn bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k≥1k\ge 1k≥1: Q∥∗Q\|^*Q∥∗ versus R2∗R2^*R2∗: We show that quantum simultaneous protocols with Θ~(k5log⁡3n)\tildeΘ(k^5 \log^3 n)Θ~(k5log3n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k)O(k)O(k) qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. R∥∗R\|^*R∥∗ versus Q∥∗Q\|^*Q∥∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k \log n)Θ~(klogn) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k)O(k)O(k) qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. R∥∗R\|^*R∥∗ versus R1∗R1^*R1∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k\log n)Θ~(klogn) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k)O(k)O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.
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 present relation problems whose input size is nnn such that they can be solved with no communication for entanglement-assisted quantum communication models, but require Ω(n)Ω(n)Ω(n) qubit communication for 222-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.