← 研踪 PaperTrailarXiv:2609.16726 · v3
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
首次提交 2026-09-15 14:56
版本更新 2026-11-19 15:33
雷达观测 2026-11-20 19:58
摘要
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus randomized communication with two quantum messages, and versus for every fixed with more quantum messages. Our main technical contribution is a general conversion from quantum versus randomized communication separations for partial functions to separations for total functions. Our construction combines the communication lookup construction of Anshu, Belovs, Ben-David, Göös, Jain, Kothari, Lee, and Santha (FOCS 2016), the fully linear PCPs of Boneh, Boyle, Corrigan-Gibbs, Gilboa, and Ishai (CRYPTO 2019), and a linear seeded extractor with a short seed based on the construction of Raz, Reingold, and Vadhan (JCSS 2002). The key idea is to use the extractor to compress the lookup table into a single cell, thereby reducing the input length.
作者备注:17 pages; v3: minor edits
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-19 15:33 · 最新观测版本
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus randomized communication with two quantum messages, and versus for every fixed with more quantum messages. Our main technical contribution is a general conversion from quantum versus randomized communication separations for partial functions to separations for total functions. Our construction combines the communication lookup construction of Anshu, Belovs, Ben-David, Göös, Jain, Kothari, Lee, and Santha (FOCS 2016), the fully linear PCPs of Boneh, Boyle, Corrigan-Gibbs, Gilboa, and Ishai (CRYPTO 2019), and a linear seeded extractor with a short seed based on the construction of Raz, Reingold, and Vadhan (JCSS 2002). The key idea is to use the extractor to compress the lookup table into a single cell, thereby reducing the input length.
查看此版本解读 →查看此版本原文 ↗