Improved Separations between Quantum and Classical Communication Complexity of Total Functions

1 Introduction

• Earlier work established separations up to R(f) ≥ Q(f)^(3−o(1)) for total Boolean functions, while Gavinsky's construction achieved Q2(f) = polylog(n) and R(f) = eΩ(n^1/6).Gavinsky's construction combines communication lookup with efficient polynomial-certificate verification based on fully linear PCPs.Source: §1 · p. 1
• Q2(f) = polylog(n) and R(f) = eΩ(√n) for a total function, improving the earlier exponent from 1/6 to 1/2.The earlier result had Q2(f) = polylog(n) and R(f) = eΩ(n^1/6).Source: §1 · p. 1
• Theorem 4 converts an r-message quantum protocol for a partial function into an (r+1)-message protocol for a total function, with N = eO(n + s), R(Ftot) = eΩ(R(F)), and Qr+1(Ftot) = eO(q).The partial function's domain indicator has circuit size at most s, and its protocol has cost q.Source: §1 · p. 2
• A seeded linear extractor replaces the lookup table with one compressed cell holding candidate certificates of length eO(n + s).The certificate at address L is EL(U + V); extractor near-uniformity lets the lookup lower-bound proof retain its force up to polylogarithmic factors despite correlations among certificates.Source: §1 · p. 2
• For Shapem, reducing the promise-checking circuit from O(m2) to eO(m) changes the resulting exponent from 1/4 to 1/2.The O(m2)-size circuit already gives exponent 1/4; Proposition 10 supplies the smaller circuit and proves Theorem 2.Source: §1 · p. 2

• The text defines mutual information and conditional mutual information using Shannon entropy, measured in bits.Source: §2 · pp. 2–3
• Randomized complexity allows public randomness and arbitrarily many messages, while quantum complexity is defined without prior entanglement and protocols have worst-case cost and error at most 1/3.Source: §2 · p. 3
• The extractor is a strong seeded extractor whose fixed-seed maps are binary-linear and surjective, with an explicit construction and seed length O(log^2 b).Source: §2 · p. 3
• The circuit-to-certificate construction gives certificates of length O(S log S) and a perfect-completeness randomized test with soundness error at most 1/64.On additively shared inputs and certificates, a party can send a challenge and four affine-answer shares using O(log S) bits.Source: §2 · p. 4

3.1 Definition of the total function

• The construction applies the certificate predicate to extractor outputs for a tuple of inputs, with the tuple-domain predicate requiring every pair to lie in dom(F).The certificate is padded to b bits; when the tuple is in the domain, valid and invalid certificates both exist, and otherwise none is valid.Source: §3.1 · p. 5

3.2 Lower bound statement and proof of Theorem 4

• Under s ≤ poly(n), the construction has b ≤ poly(n) and c = O(log^2 n), and the section identifies a main technical lower bound proved in Section 4.The theorem is concluded by combining the bounds with N = eO(n + s).Source: §3.2 · pp. 5–6
• The resulting quantum protocol has Q_{r+1}(Ftot) = eO(q), with parallel amplification across the c slots and a final certificate test.The proof bounds the address error by 1/64 when the tuple is in the domain and uses the test's soundness when it is not.Source: §3.2 · p. 5

4 Proof of the Compressed Lookup Lower Bound

• Theorem 4.1 states that for every 1/3-error randomized protocol Π for Ftot, there is a randomized protocol Π′ for F; the proof adapts [3, Theorem 6].Source: §4 · p. 6

4.1 Proof of Theorem 4.1

• For each input distribution on dom(F), the proof constructs protocols by sampling the other tuple coordinates and source shares publicly, then running the original protocol.It rules out distributions that are easy to predict from one party's input and protocols that reveal too much about individual output bits.Source: §4.1 · pp. 6–7
• Under assumptions (A2) and (A3), Lemma 9 bounds how much fixing the extractor outputs changes transcript distributions, enabling the contradiction argument.The proof uses minimax and independent repetition with majority voting to obtain a protocol that works on all promised inputs.Source: §4.1 · pp. 7–8, §4.2 · p. 9

4.2 Proof of Lemma 9

• Lemma 9's proof combines transcript/source independence estimates with information bounds and averaging to control the probability of large transcript-distance deviations.Source: §4.2 · pp. 9–11

5.1 Application 1: total function from Shape

• The Shape application computes its domain predicate with a Boolean circuit of size O(m log^2 m), enabling its use in the total-function conversion.The underlying partial function distinguishes cyclic shifts within distance 2m/5 from shifts whose distances lie between 7m/15 and 8m/15.Source: §5.1 · p. 11
• A polylogarithmic quantum protocol using two messages is obtained for the total function built from Shape, alongside a randomized lower bound of eΩ(√m).The conversion applies Theorem 4 using the domain-circuit bound O(m log^2 m).Source: §5.1 · pp. 11–12

5.2 Application 2: total functions from k-Forrelation

• For fixed k, a Walsh–Hadamard butterfly computation and exact integer threshold tests construct a Boolean-circuit domain test for the gadget-composed k-forrelation function.The integer tests avoid approximating the threshold m^(k+1)/2, even when it is irrational.Source: §5.2 · pp. 12–13
• eΩ_k(m^(1−1/k)) randomized communication and polylogarithmic quantum communication with 2⌈k/2⌉ + 1 messages are obtained for functions with eO_k(m) input bits per party.The construction applies for fixed k ≥ 2.Source: §5.2 · p. 13

AI disclosure

• ChatGPT-6 Astra helped explore and refine proof ideas and draft and revise the text; the author says it proposed Theorem 4’s core proof idea and takes full responsibility for the paper.The author subsequently verified, simplified, and organized the argument.Source: AI disclosure · p. 14