Quantum messaging cuts communication in key secure computations
Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Computational ComplexityCryptography and Security
Summary
Some basic tasks in secure communication need a lot of information shared between multiple people. This paper shows that using quantum messages, these tasks can require less communication than classical messages, thanks to quantum properties like entanglement. However, for certain functions, there are limits on how well quantum methods can reduce communication. The authors demonstrate this balance by studying specific functions like equality and majority, finding quantum advantages and fundamental restrictions.
What this means in practice
- •For quantum communication engineers: Enable more bandwidth-efficient secure multiparty quantum communication protocols based on entanglement-assisted messaging for functions like equality and majority.
- •For quantum cryptography system designers: Design secure distributed systems with reduced quantum communication costs by leveraging low-dimensional quantum states for function-specific protocols.
A theory result. No direct application yet.
Authors
Harumichi Nishimura
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.