On the quantum communication complexity of total functions

Dmytro Gavinsky

REVIEW

On the quantum communication complexity of total functions

Dmytro Gavinsky

Computational Complexity · Submitted 19 Aug 2026

Pith's verdict: A clever totalization construction that likely yields a super-polynomial two-message quantum vs. randomized separation, but the proof currently hinges on an unverified instantiation of a fully linear PCP—worth refereeing, not publishing yet.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 27, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2608.18784 (version 2)

Pith IDN65QX3DW, Pith's permanent record of this paper and its review

CitationDmytro Gavinsky. "On the quantum communication complexity of total functions." arXiv:2608.18784 (2026). https://pith.science/paper/N65QX3DW

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper claims a genuine result: a total Boolean function with polylogarithmic two-message quantum communication and polynomial randomized communication, even with many rounds. The high-level construction is clever, and the new mathematical step is real. The certificate-based totalization that turns the Shape promise problem into a total Cheat-Shape_n, while preserving both the quantum upper and classical lower bounds, is not in [1], [2], or [3]. That is the paper's actual contribution, and it works cleanly at the level of the high-level proof. The quantum protocol has the right structure—use Shape's one-way protocol to select a drawer, then a fresh challenge for that drawer—and the lower-bound normalization via the cheat-sheet framework checks out (equations 16–17). The algebra is sound, and the reliance on the author's earlier work is not circular; [1] is a published external result.

The soft spot is exactly where the stress-test flags it: the instantiation of the fully linear PCP from [3] in equations (6)–(10). The protocol's correctness and the O(log S_n) message bound depend on four properties holding together: certificate length O(S_n log S_n), perfect completeness, a single random-point test with error ≤ 1/64, and—critically—that the four queried values p(t), f_p(t), g_p(t), p(τ_q) are affine functions of the input and the certificate. That last condition is what turns XOR-shared certificate bits into additive field shares. The paper asserts these properties, and points to [3], but does not verify that the theorem's hypotheses are met over a characteristic-two field with additive-share evaluation. It also does not spell out the interpolation step that makes f_p and g_p affine in the certificate. This is a missing proof, not a known contradiction, but it is load-bearing. If [3] requires a larger field or more than one query, the quantum upper bound (12) and the input-size identity (5) both collapse.

The paper is explicitly a preliminary version, and the FLPCP gap is the kind of thing that is likely fixable by a careful derivation. But as written, the central theorem is not fully proven. There are no other serious red flags; the exposition is clear, and the totalization idea deserves attention.

This paper should go to peer review. A serious referee can check the FLPCP instantiation, and if it holds, the result is a strong within-field contribution. If not, the author needs to patch or replace that step. My own verdict would be conditional: accept only after the certificate construction is written out in full.

Who should read it: communication complexity researchers interested in quantum-classical separations. I would bring it to a reading group to discuss the totalization trick and the PCP gap, but I would not yet cite it as a proven separation.

Referee report

Significance

If the PCP instantiation can be rigorously verified, the result is significant: it would provide the first explicit separation between two-message quantum communication and randomized communication for a total Boolean function, with a polynomial gap (1/6 vs. 1 in the exponent). The paper's use of the cheat-sheet framework together with a fully linear PCP is a substantive and novel combination, and the explicit totalization via certificates is an original step that goes beyond prior partial-function separations. The result also highlights a connection between communication complexity and fully linear PCPs, which may have further applications. However, the current manuscript is preliminary and the PCP step is not yet a complete proof; the main theorem should be regarded as conditional on that verification. The paper also benefits from building on established results [1,2,3] and from presenting an explicit construction, which are strengths.

Major objections (2)

[The certificate in the drawers, Eqs. (6)-(10)] The construction and soundness of the certificate predicate V_{D_{n,k}} rest on an unverified instantiation of [3, Theorem 4.3]. The paper states that the "multiplication-gate fully linear PCP" is used in its non-zero-knowledge form with additive-share evaluation, but it does not state the theorem's precise hypotheses nor verify them for a characteristic-two field K, the specific arithmetic circuit for 1-D_{n,k}, or the requirement that certificate bits become additive field shares. In particular, the claims that (i) the certificate has length O(S_n log S_n), (ii) the randomized test uses a single random point with error at most 1/64, and (iii) the four queried values p(t), f_p(t), g_p(t), p(τ_q) are affine functions of the input and certificate are all asserted without a proof or a detailed mapping to [3]. If, for example, the theorem requires a larger field or more than one query, the O(log S_n) message bound (12) and the input-size identity (5) would both fail. This is load-bearing for both the upper and lower bounds; the authors should either give a self-contained derivation of (7)-(10) from [3] or state and check the hypotheses of [3, Theorem 4.3] in detail, including the interpolation step for f_p and g_p.
[Eq. (10) and the quantum protocol] The soundness constant 1/64 in Eq. (10) is obtained by taking |K| to be a "sufficiently large constant times q", but the constant is not quantified and the compatibility of this field size with the characteristic-two and additive-share requirements is not discussed. The Schwartz-Zippel bound for a nonzero polynomial of degree at most 2q-2 requires |K| ≥ 128(q-1) for error 1/64, so the paper should specify a concrete constant and verify that the field K chosen is large enough. In addition, the protocol's soundness argument should explicitly handle the quantifier over invalid certificates: for every fixed invalid certificate c, the random point t is fresh because Bob samples t after the drawer is selected, but this is not stated in the proof of (10). The current presentation leaves the impression that the constant can be tuned arbitrarily without affecting other parts of the construction.

Minor objections (4)

[Throughout] The notation Q^1_{1/3}(·) and R_{1/3}(·) is used in Theorem 1 and equations (11) and (13) without definition; please define these in the introduction or immediately before Theorem 1, including the meaning of the superscript '1'.
[Eq. (1)] In the definition of D_{n,k}, the inputs are written as x^{(r)} and y^{(r)}, but the superscripts are not typeset in the manuscript text; this may cause confusion and should be fixed in the final version.
[The certificate in the drawers] The paper should provide an intuitive explanation of how the FLPCP predicate (7) is used as a certificate, perhaps with a short example, since the algebraic definition is dense and the connection to the drawer mechanism is central to the protocol.
[References] The reference to [3, Section 6.2] should include the section title and the theorem number used, as the numbering in the preprint version may differ from the published version.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper constructs an explicit total Boolean function whose two-message quantum protocol uses polylogarithmic communication, while every randomised protocol, even with arbitrarily many rounds, needs polynomial communication.

The reading

The paper claims that quantum communication can beat classical randomised communication even when both parties must output an answer on every possible input—that is, for a total Boolean function, not a promise problem. It constructs an explicit family $\mathrm{Cheat\text{-}Shape}_n$ with a two-message, entanglement-free quantum protocol of $O(\log^3 N_n \log\log N_n)$ communication, and proves that every randomised protocol, no matter how many rounds it is allowed, needs $\Omega(N_n^{1/6}/\log^{7/3}N_n)$ communication. Total functions are a demanding setting for communication-complexity gaps because the answer is defined everywhere, so the advantage cannot hide in a promise. The construction works by building $k$ copies of a shifted approximate equality promise problem into the input, using a cheat-sheet mechanism to locate an answer, and attaching a certificate that is verified by a fully linear PCP so that illegal inputs evaluate cleanly to zero.

What carries the argument

The load-bearing mechanism is the combination of drawers with certificates. Each input contains $k$ base pairs for the Shape_n promise problem, whose $k$ answers form an address $L$; it also contains $2^k$ drawers, each holding a candidate output bit and a certificate string. The true output is the candidate in drawer $L$, but only if its certificate passes the predicate $V_{D_{n,k}}$, which is designed so that a certificate exists if and only if all $k$ base pairs satisfy the Shape_n promise. The certificate itself encodes a polynomial $p$ of degree at most $2q-2$ over a characteristic-two field, where $q$ is the number of multiplication gates in a circuit for $1-D_{n,k}$; verification checks the identity $p(T)=f_p(T)g_p(T)$ and $p(\tau_q)=0$, and a fresh random point makes the one-sided error at most $1/64$. This certificate system makes the overall function total, because off-promise inputs have no valid certificate, and lets the quantum protocol send only the address plus a short verification message.

Extended reading notes

Core claim

The central discovery is an explicit total Boolean function $\mathrm{Cheat\text{-}Shape}_n$ whose two-message quantum communication complexity is $O(\log^3 N_n \log\log N_n)$ while its randomised communication complexity, even with arbitrarily many rounds, is $\Omega(N_n^{1/6}/\log^{7/3}N_n)$. The function is total: on inputs where the underlying promise problem is satisfied, the output is the certified answer in the drawer selected by the quantum-computed address; on inputs that violate the promise, every certificate is invalid and the function outputs zero. The proof combines the shifted approximate equality problem of [1], the cheat-sheet lookup construction of [2], and the multiplication-gate fully linear PCP of [3], which supplies short certificates whose validity can be tested at a single random field point. The paper thereby converts a promise-based quantum advantage into a total-function separation.

Load-bearing premise

The result stands on the fully linear PCP of [3] staying sound (error at most $1/64$) and compact (certificate length $O(S_n \log S_n)$) when it is instantiated for the arithmetic circuit of $1-D_{n,k}$ over a characteristic-two field with additively shared inputs; the paper cites [3] for this property rather than giving an instance-specific proof.

Editorial extensions

If this is right

Every randomised protocol for Cheat-Shape_n, regardless of the number of rounds, must send polynomially many bits, so the quantum advantage cannot be removed by adding classical interaction.
The separation is achieved with no prior entanglement and only two quantum messages (A to B to A), so the advantage is due to quantum information alone.
Because Cheat-Shape_n is a total Boolean function, the separation is not an artifact of a promise; it holds on every input in the domain.
The construction is explicit, so the function family can be implemented and the protocol run for concrete values of n, allowing the asymptotic gap to be inspected empirically.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's claims, the certificate-in-drawers trick is portable: any promise problem with a one-way quantum protocol and an efficient certifiable version of its promise can likely be lifted to a total function with a similar gap.
Beyond the paper's claims, iterating the cheat-sheet-and-certificate construction may amplify the gap further, potentially toward an exponential separation between two-message quantum and multi-round randomised communication for total functions.
Beyond the paper's claims, one could test whether the one-sided soundness constant 1/64 is tight for these arithmetic circuits; a sharper bound would tighten the polynomial lower bound.

Original abstract

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 1,613 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.09 · human participants 0.02 · controlled comparison 0.28 · randomized assignment 0.02 · states quantitative result 0.90 · compares with prior results 0.88 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.	result 0.79	0.93	0.91	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

An exponential separation between entanglement-assisted and unassisted one-way quantum communication
quant-ph 2026-10 accept novelty 8.0 of 10

For every input size there is a total Boolean function that needs O(log n) bits of one-way communication with entanglement but Omega(n^{1/3}) qubits without it.
Exponential Quantum Advantage in Numbers-on-Forehead Communication
cs.CC 2026-09 conditional novelty 8.0 of 10

The Interleaved Unitary Product problem shows an exponential gap between one-clean-qubit quantum and randomized communication in three-party Numbers-on-Forehead complexity.
Improved Separations between Quantum and Classical Communication Complexity of Total Functions
quant-ph 2026-09 accept novelty 7.0 of 10

Polylog quantum communication complexities are shown to be exponentially larger separations from randomized communication than previously known for total functions.
BQP^cc is not contained in MA^cc
cs.CC 2026-10 conditional novelty 6.0 of 10

A bipartite function with efficient quantum communication is shown to have high Merlin-Arthur communication complexity, proving BQP^cc ⊄ MA^cc.

How the literature uses it

1 arXiv paper cite this in 1 sentence

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it

Compares with it 1 paper

Independently and concurrently with our work, Gavinsky [ref] showed a total function that admits a 2-round quantum protocol with poly-logarithmic communication complexity and requires polynomial randomized communication complexity, which is stronger than our result.

Constant-round quantum advantage in communication complexity for total functions · Concurrent work · 1.00

What it cites

Uses the method or tool of 1 paper

We combine the shifted approximate equality problem  from [ref] , the communication cheat-sheet construction of Anshu et al. [ref] , and the multiplication-gate fully linear PCP of Boneh et al. [ref] .

Separations in communication complexity using cheat sheets and information complexity · Introduction · 0.98

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.