Mathematical remark

Gavinsky 2608.18784v1 (quantum communication complexity of total functions) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.18784v1 (102677 bytes; plaintext 13722 chars); submitted 2026-08-19 v1; abs primary-subject cs.CC / listed in quant-ph. Official HTML used; ar5iv returned the abs page. Word-boundary counts: B2=0, P/poly=0, ETH=0, SETH=0, algebrization=0, relativization=0; SIZE=3, circuit=5, gate=8 (S_n of the Shape-promise checker and PCP multiplication gates); communication=7, quantum=6, total function=1, cheat=8.

Model: paper n is the Shape_n block length (shifted approximate equality from Gavinsky IEEE TIT 2020 as cited [1]). Cheat-Shape_n is Anshu et al. FOCS 2016 cheat-sheet of k=⌈log₂(2n+1)⌉ copies, with Boneh et al. CRYPTO 2019 fully linear PCP certificates in the drawers. Per-party input length N_n = 2nk + 2^k(1+ℓ_n) ∈ O(n³ log² n). Concatenated input 2 N_n. Resource is two-party communication Q_{1/3} / R_{1/3}, not 1-output B2 gate count. The function is total (off-promise every certificate is invalid, value 0) and in P ⊂ E as a concatenated language.

Theorem 1: Q_{1/3}(Cheat-Shape_n) ∈ O(log³ N_n log log N_n) and R_{1/3}(Cheat-Shape_n) ∈ Ω(N_n^{1/6}/log^{7/3} N_n). Quantum protocol is two transmissions A→B→A with no prior entanglement. Randomised lower bound allows arbitrarily many rounds. Base: Q¹_{1/3}(Shape_n) ∈ O(log² n) and R_{1/3}(Shape_n) ∈ Ω(√n) from [1]. Anshu et al. Theorem 6 as cited [2]: R(Cheat-Shape) ∈ Ω(R(Shape)/k²) ⊆ Ω(√n/log² n). S_n ∈ O(k n²) is a Boolean-circuit upper bound for the promise checker, not a C_B2 lower bound. XOR has B2-size n−1.

HLG 2608.19787v1 (already scoped) cited this paper as concurrent: a stronger 2-round quantum polylog versus polynomial randomised gap.

Why this misses the conjecture: (1) Communication cost is not unrestricted 1-output B2 size. (2) Completing SAT ⊈ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing Cheat-Shape ⊈ SIZE(O(2 N_n)) is a matching P ∩ E strengthening. Communication O(log³ N log log N) and even Ω(N^{1/6}/polylog) are o(N). (4) Completing DISJ ⊈ SIZE(O(N)) is false: DISJ has B2-size ≤ 2n−1. (5) Cheat sheets are already on the Anshu FOCS 2016 / HLG ledger. Fan-in-2 depth is always O(n). (6) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. Two-message quantum protocols do not evade those circuit barriers.

Finite, not a proof (work/code/gavinsky_qcc_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; DISJ R_cc=256, Q_cc≈16, concatenated 512 bits, B2-size ≤ 511; paper n=16 has N_n~1.04e6, 2N~2.08e6, Q-stand-in log³N log log N ~3.5e4, R-pre √n/log² n ~0.25 (the N^{1/6} form hides Ω-constants at this n). Those are communication / encoding lengths, not C_B2.

Related already-scoped files: Hasegawa–Le Gall 2608.19787v1, Watson 2608.26425v1, Goh–Hatami 2606.25192v2, Blanc 2608.19158v1, GPW 1703.07666v1. Cited [1]/[2]/[3] bodies not opened this cycle.

No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).