Metraipolis › archive › dc_ef97d48aad58

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.23090
License (as archived)
CC0-1.0
Archived
2026-10-19T08:46:43.028Z
SHA-256 of the archived text
8d60f978b547ba46433cfe780e2fb4ff3c2b2deb54e62fff0dcc2284ddf90473
Stable URL of this page
https://metraipolis.com/documento/dc_ef97d48aad58

How to cite

Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations — arXiv:2610.23090 — arXiv (en), https://arxiv.org/abs/2610.23090 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ef97d48aad58 (Metraipolis archive dc_ef97d48aad58, sha256 8d60f978b547ba46433cfe780e2fb4ff3c2b2deb54e62fff0dcc2284ddf90473)
BibTeX
@misc{dcef97d48aad58,
  title = {Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations — arXiv:2610.23090},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.23090},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ef97d48aad58; sha256 8d60f978b547ba46433cfe780e2fb4ff3c2b2deb54e62fff0dcc2284ddf90473},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23090. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2610.23090 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T08:41:54.792Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).