← 研踪 PaperTrailarXiv:2611.07318 · v1
Asymptotic advantage of quantum one-way and SMP communication for total functions
首次提交 2026-11-05 10:05
版本更新 2026-11-05 10:05
雷达观测 2026-11-06 10:04
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 10:05 · 最新观测版本
Asymptotic advantage of quantum one-way and SMP communication for total functions
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.
查看此版本解读 →查看此版本原文 ↗