{"id":"arxiv/2609.16726","url":"https://arxiv.org/abs/2609.16726","tags":["quant-ph","cs.CC"],"score":0,"title":"Improved Separations between Quantum and Classical Communication Complexity of Total Functions","domain":"quant-ph","source":"arxiv","authors":["François Le Gall"],"reviews":0,"subject":"quant-ph","summary":"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 $\\tildeΩ(\\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\\varepsilon})$ for every fixed $0<\\varepsilon<1$ with more quantum messages.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}