Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
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…)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 3log2 3. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥ 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 klog2 k qubits in total.
Related
- Unveiling the structural evolution of metastable supported Ag-Ni nanoalloys during sequential or simultaneous growth
- Communication Advantages from Quantum Dense Network Coding
- Spatiotemporal quantum advantages for rare-event sampling
- The Compendium of Super-Quadratic Computational Quantum Advantages
- The advantages of extended nonreciprocal quantum batteries
BibTeX
@misc{nishimura2026concrete,
title = {{Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations}},
author = {Harumichi Nishimura},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23090},
eprint = {2610.23090},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23090},
}
RIS
TY - UNPB
TI - Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
AU - Harumichi Nishimura
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23090
UR - https://arxiv.org/abs/2610.23090
AB - 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…)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 3log_2 3. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥ 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 klog_2 k qubits in total.
ER -