{"id":"arxiv/2611.07318","url":"https://arxiv.org/abs/2611.07318","tags":["cs.CC","quant-ph"],"score":0,"title":"Asymptotic advantage of quantum one-way and SMP communication for total functions","domain":"cs.CC","source":"arxiv","authors":["Dmytro Gavinsky"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}