Quantum protocols cut communication for equality, majority, and AND
Original title: Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Entanglement-assisted three-party equality uses about 1.633n qubits, versus at least 3n without it.
A theory paper analyzes communication for concrete functions under private simultaneous quantum messages. For three-party equality, an entanglement-assisted protocol uses asymptotically about 1.633n qubits, while every perfectly correct protocol without prior entanglement needs at least 3n qubits. Three-bit majority falls from six classical bits to three qubits with one GHZ state. Three-bit AND has no perfect one-qubit-each protocol on an arbitrary three-qubit shared state, but a three-qutrit construction uses 3 log2 3 communication.
- Three-bit majority uses one shared GHZ state and one transmitted qubit per player.
- A three-qutrit GHZ protocol gives a strict quantum advantage over the six-bit classical bound.
- For every k at least 3, k-bit AND uses one qudit of dimension at most k per player.
- Total communication for that construction is at most k log2 k qubits.
From the original article
1 min read at arxiv.orgPrivate 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.
By Harumichi Nishimura · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.