跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 Ω~(n)\tildeΩ(\sqrt n) randomized communication with two quantum messages, and versus Ω(n1−ε)Ω(n^{1-\varepsilon}) for every fixed 0<ε<10<\varepsilon<1 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

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 Ω~(n)\tildeΩ(\sqrt n) randomized communication with two quantum messages, and versus Ω(n1−ε)Ω(n^{1-\varepsilon}) for every fixed 0<ε<10<\varepsilon<1 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.

查看此版本解读 →查看此版本原文 ↗