CS Paper Radar

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

Harumichi Nishimura

cs.CC quant-phcs.CR ·submitted 2026-10-16 07:59 UTC · v1
theory

Abstract

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.

Comment
45 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On the Limits of Quantum Multiparty Simultaneous Communication

cs.CC quant-ph ·2026-09-09 ·Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
theory similarity 0.72
Abstract · 27 pages, 1 figure

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$.

0.25

Asymptotic advantage of quantum one-way and SMP communication for total functions

cs.CC quant-ph ·2026-11-05 ·Dmytro Gavinsky
hot direction similarity 0.71
Abstract

We exhibit a total Boolean function on n input bits whose bounded-error quantum simultaneous-message (and hence one-way) communication complexity is in O(\sqrt n), whereas its randomised one-way (and hence simultaneous-message) communication complexity is in Ω(n). The same function admits a classical simultaneous-message protocol of cost O(\sqrt n) when the players share O(\sqrt n) EPR pairs.

0.23

Private communication via zero-private-capacity quantum channels

cs.IT quant-ph ·2026-09-09 ·Chengkai Zhu, Xin Wang
similarity 0.71
Abstract · 14 pages

Private communication over a noisy quantum channel requires reliable transmission to the receiver and secrecy from the environment. Whether two channels with zero private capacity can jointly enable private communication is a longstanding open problem in quantum information theory. Here we resolve this problem by exhibiting a four-level channel and a qubit erasure channel with half erasure probability, each with zero private capacity, whose joint use achieves more than 0.0001903 private bits per product use. The encoding gives the receiver a linear information gain with at most quadratic environmental leakage, enabling privacy through a fixed joint measurement and classical coding. This superactivation, impossible for independent classical memoryless wiretap channels, shows that a channel's private capacity alone does not determine its value for secure communication. The initial activation example was identified through interactions with large language models, and the result has been formalized in Lean 4.

0.50

A Cheat-Sensitive Primitive for Destination-Private Quantum Routing

cs.CR quant-ph ·2026-10-03 ·S. F. E. Oliviero, S. Onofri, V. Giovannetti
similarity 0.69
Abstract

Quantum networks will rely on intermediate nodes to distribute entanglement, but the same nodes may learn which users are being connected. We introduce a minimal two-call routing primitive in which a user, Alice, establishes an entangled link with one of several clients while testing whether the provider, Bob, has disturbed a coherently encoded request. The construction adapts the hidden-order mechanism of quantum private queries: one call contains a direct request, the other a coherent superposition of the desired and null addresses, and Alice keeps their order secret. A private matching qubit held by the selected client restores the coherent test state after a favorable Bell-measurement outcome, so that Alice can test the returned query without any further operation by Bob. The claim is deliberately limited. The protocol shows that a routing request can carry a physical cheating test, and it detects an explicit destination-reading attack with nonzero probability. It does not yet provide a quantitative information-disturbance tradeoff, composable security, or certification of an unmeasured output against arbitrary attacks. We also characterize the exact perfect-pass limit, in which Bob's residual state, averaged over the private matching states, is independent of the destination.

0.30

Quantum-State Oblivious Transfer over Quantum Erasure Channels

cs.IT quant-ph ·2026-10-03 ·Remi A. Chou
hot direction similarity 0.68
Abstract

We study quantum-state oblivious transfer over the quantum erasure channel under information-theoretic security guarantees. Specifically, Alice holds two quantum systems, Bob wishes to recover one of them, and the parties have access to independent channel uses and authenticated public classical communication, with no initial shared entanglement. We consider both honest-but-curious and malicious behavior. We establish finite-blocklength converse and achievability bounds, which match in the honest-but-curious setting. The malicious setting construction combines interactive hashing with tests of whether Bob received selected channel outputs, and distributes each input across several qubits so that erasures conceal an entire input from a dishonest receiver, even when the inputs are entangled with an external reference. We also derive fixed-error asymptotic expansions and show that both malicious and honest-but-curious settings have the same capacity.

0.24

Quantum Advantage for Two-Party Differential Privacy

cs.CR quant-phcs.IT ·2026-10-01 ·Daniel Alabi, Emil T. Khabiboulline
similarity 0.67
Abstract · 15 + 7 pages, 2 figures. Also on ePrint

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $Ω(\sqrt{n})$ error under pure differential privacy and $Ω(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+γ$, for every $γ>0$. For approximate $(\varepsilon, δ)$ QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the $O(1)$-versus-$Ω(\sqrt{n}/\log n)$ separation for $δ=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy.

0.29

Constant-round quantum advantage in communication complexity for total functions

cs.CC quant-ph ·2026-08-20 ·Atsuya Hasegawa, François Le Gall
similarity 0.67
Abstract · 13 pages

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

0.39

An exponential strong converse for private communication over degradable quantum channels

cs.IT quant-ph ·2026-09-26 ·Mark M. Wilde
theory similarity 0.67
Abstract · 49 pages, 8 figures

We prove an exponential strong converse for the unassisted private capacity of every finite-dimensional degradable quantum channel. We use a single error criterion: the infidelity between the actual message-estimate-environment state and an ideal state consisting of uniformly distributed, perfectly correlated messages that are independent of the environment. At every rate strictly above the channel's maximum coherent information, the optimized fidelity to this ideal state decays exponentially in the number of channel uses. The same bound holds when the ideal environment state is fixed to the actual environment marginal. The proof applies to arbitrary mixed-state encoders and arbitrary collective decoders. Its main operator ingredient is an overlap bound for privacy tests: two receiver placements with a common subsystem of dimension $d_C$ have overlap at most $d_C/M$, where $M$ is the key size, independently of both shield dimensions. We combine this bound with the signed averaging construction presented in arXiv:2608.01308 and a single-filter reduction to symmetric states. A Gaussian filter replaces the common receiver subsystem by a system of controlled dimension from which the original correlations can be approximately recovered using quantum side information. The filter preserves exact exchange symmetry, and a uniform smooth-entropy estimate bounds its output dimension for arbitrary correlated channel inputs. We also obtain an exponential strong converse at zero for antidegradable channels under the same joint criterion and, consequently, for the private capacity of the quantum erasure channel throughout its parameter range.

0.32