On the quantum communication complexity of total functions

arXiv:2608.18784 · cs.CC, quant-ph · Submitted 2026-08-19 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "On the quantum communication complexity of total functions".

Mira: The gist The authors present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So we're looking at this paper now called "On the quantum communication complexity of total functions." It sounds pretty technical, but basically they’re talking about how much communication it takes for a quantum computer to solve certain kinds of problems.

Mira: Yeah, it’s about the complexity of total functions. And you know how those functions are just mapping inputs to outputs, and this paper is looking at the communication cost for that when you use quantum protocols.

Lev: What's interesting here is they are combining a few different things: they’re using something called the shifted approximate equality problem from one reference, and then adding in a communication cheat-sheet construction from another work, plus this multiplication-gate fully linear PCP from Boneh et al.

Kai: Right. So they are building up this new total function family called Cheat-Shapen that has some specific properties related to Hamming weights, and they’re showing how their quantum protocol handles it in a polylogarithmic communication way.

Mira: That’s the core idea, right? They aren't just looking at one simple problem; they are defining a whole class of functions and proving that for this specific family, the quantum cost is relatively low compared to what classical methods demand.

Lev: It’s important because it sets a benchmark. The paper shows that for this specific function family Cheat-Shapen, the quantum communication complexity is in O(log3 Nn log log Nn).

The paper's summary: Kai: So what does this result actually mean when you break down the function definition? They define di of x and y based on some cyclic shifts σi of their input bits, and Shapen is defined by checking a minimum of those differences against a threshold involving n.

Mira: It's complex because they are using these shifts, which suggests they are probing structural properties related to permutations or symmetries within the inputs, but the actual check involves finding a minimum distance condition.

Lev: The certificate construction is where things get dense. They use something called multiplication-gate fully linear PCP from Boneh et al., which is a non-zero-knowledge proof setup, and they build this certificate VDn,k based on that structure.

Kai: So the certificate itself isn't just a simple string; it’s this complex arithmetic circuit over a characteristic two field K, where the nonlinear gates are multiplication gates and the rest are affine operations like addition and negation.

Mira: That means they’re using a very specific algebraic structure to encode the necessary information about Shapen, allowing them to check all those Hamming weights efficiently.

Lev: And the size of that certificate is bounded by Sn, which is in O(kn2), where k is related to the number of base pairs they are testing.

The paper's improvements: Kai: The main improvement they’re highlighting here is moving from randomized protocols, even those with many rounds, which classically require polynomial communication, down to a quantum protocol that only needs polylogarithmic communication for Cheat-Shapen.

Mira: That contrast is key. They show that while a randomized protocol might use polynomial bits to be absolutely sure about the answer in many rounds, this specific quantum approach achieves its goal with Q1/three(Cheat-Shapen) which is O(k log k log2 n plus k plus log Sn) <ref:2608.18784#pg1>.

Lev: And they tie this complexity back to the classical lower bound analysis derived from one <ref:2608.18784#pg1>. They show that the randomized lower bound for Shapen and k copies is in Omega R1/three(Shapen) times something related to n, specifically Omega sqrt(n) log2 n <ref:2608.18784#pg1>.

Kai: So they are showing that the quantum communication complexity is strictly better than what you'd expect from a simple randomized analysis when you account for the structure of Cheat-Shapen.

Mira: And this leads them to conclude that for this function family, the quantum communication complexity is contained within O(log3 n log log n), which they see as being quite efficient.

Conclusion: Kai: So wrapping up on "On the quantum communication complexity of total functions," it boils down to proving that for Cheat-Shapen, you can get a quantum protocol with polylogarithmic communication. This is achieved by using a specific certificate structure built from multiplication gates and linear PCPs.

Mira: What this means practically is that we’ve found a way to verify these complex structural properties across massive datasets with very limited communication overhead, specifically O(log3 Nn log log Nn).

Lev: From an engineering standpoint, this result suggests that if you had to run this on real hardware, the overhead lands in a way that makes the protocol feasible, especially when you consider how the certificate size Sn scales.

Kai: And Lev is right. The fact that they can bound the communication complexity using these tools is what makes it sound plausible for actual implementation on systems like superconducting qubits.

Mira: It’s about leveraging those succinct proof systems to verify membership in these complex function classes with minimal communication overhead, which points toward how we might secure distributed computations using this framework.

Lev: The work shows that the classical lower bound is much larger than what the quantum protocol needs, which indicates a genuine efficiency gain for this specific problem structure.

Kai: So yeah, to summarize "On the quantum communication complexity of total functions," they’ve shown that Cheat-Shapen has a polylogarithmic quantum protocol with O(log3 Nn log log Nn) communication complexity.

Mira: It's a concrete result linking function structure to quantum communication cost. We should keep an eye on how this certificate construction can be adapted for other total functions.

cs.CC, quant-ph

Submitted: 2026-08-19

Updated: 2026-10-17

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: The gist The authors present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial

Key concepts

Cheat-Shapen
This is a specific family of total Boolean functions introduced by the authors. It is defined based on a condition involving Hamming weights of input pairs (x, y) and Shapen(x, y), which involves checking the minimum of these conditions across multiple indices.
Quantum Protocol Mechanism
The quantum protocol uses two transmissions between Alice and Bob without prior entanglement. Alice amplifies a consequence related to the function for each base pair, and Bob measures the results to determine a 'k-bit address' (J). This allows them to efficiently test the function by sampling field points and reconstructing necessary evaluations.
Multiplication-Gate Fully Linear PCP
This is a specific type of certificate construction used in the paper. It checks if a polynomial identity holds, meaning p(T) equals fp(T)gp(T), which is equivalent to checking if p(τq) equals zero. This allows for succinct proof verification related to the function's structure.
Communication Complexity
This measures the minimum number of bits Alice and Bob must exchange to compute a specific function correctly. The paper shows that for Cheat-Shapen, a quantum protocol achieves O(log3 Nn log log Nn), contrasting sharply with classical randomized protocols which require polynomial communication.

Terminology

Summary

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

Function Definition and Complexity

The paper introduces an explicit family of total Boolean functions called Cheat-Shapen: 0, 1 Nn × 0, 1 Nn −→ 0, 1 such that the quantum protocol achieves a communication complexity of Q1/3(Cheat-Shapen) ∈ O(log3 Nn log log Nn), while the randomized lower bound requires polynomial communication. The function is defined based on the condition di(x, y) = σi(x1) ⊕ x2 ⊕ σi(y1) ⊕ y2, where · denotes Hamming weight. Shapen(x, y) is defined based on the minimum of di(x, y) and a condition involving every i. The total address L is determined by Dn,k(x, y), which checks if (x(r), y(r)) ∈ dom(Shapen) for every r in [k].

Certificate Construction

The function Cheat-Shapen is defined using a certificate structure involving tables U and V, where each drawer j offers the candidate output value oj accompanied by the certificate string cj. The exact number of input bits held by either party is Nn = 2nk + M(1 + ln). The certificate VDn,k is constructed using the multiplication-gate fully linear PCP from Boneh et al. [3], where it checks a polynomial identity p(T) ≡ fp(T)gp(T) in K[T] and requires p(τq) = 0. This certificate length satisfies ln ∈ O(Sn log Sn).

Quantum Protocol Mechanism

The quantum protocol uses two transmissions A → B → A and no prior entanglement. Alice amplifies the established one-way consequence of the quantum protocol for Shapen to error 1/(64k) for each of the k base pairs and sends all messages in one transmission. Bob measures them to obtain the k-bit address J, namely the k measured answers, thereby fixing the drawer to be tested. He then samples a fresh field point used in (10). Bob sends Alice J, his share of oJ, the field point, and his four linear-answer shares. Alice reconstructs oJ and the four evaluations and applies the test above.

Classical Lower Bound Analysis

The classical lower bound is derived using the lookup lower bound of [2, Theorem 6] applied to Shapen and k copies. This leads to R1/3(Cheat-Shapen) ∈ omega R1/3(Shapen)k2 ⊆ omega √n log2 n. Furthermore, the certificate length implies that k ∈ Θ(log n). This results in log Nn ∈ Θ(log n) and √n log2 n ∈ omega Nn 1/6 n log7/3 Nn! These equations collectively prove Theorem 1.

Quantum Communication Complexity Result

The quantum communication complexity for Cheat-Shapen is shown to be Q1/3(Cheat-Shapen) ∈ O(k log k log2 n + k + log Sn) which is contained in O(log3 n log log n). This result is supported by the combination of the quantum protocol analysis and the classical lower bound derived from [1]. The paper concludes that equations (12), (15), and (17) prove Theorem 1.

Improvements for AI systems

  1. Based on Cheat-Shapen function, an AI system could efficiently verify complex structural properties across massive datasets with polylogarithmic quantum communication complexity of O(log3 Nn log log Nn). This allows for rapid, highly efficient verification of data integrity or structural consistency in large distributed systems.

  2. The system can perform exact verification of a function family where the certificate length is bounded by ln ∈ O(Sn log Sn), which implies an AI capable of utilizing succinct proof systems to verify membership in complex function classes with minimal communication overhead.

  3. By leveraging the multiplication-gate fully linear PCP, the AI can utilize non-zero-knowledge proofs for secret-shared data, enabling secure computation and verifiable computations where inputs are distributed between parties (Alice and Bob).

  4. The system can implement a quantum protocol with a communication complexity of Q1/3(Cheat-Shapen) ∈ O(k log k log2 n + k + log Sn) ⊆ O(log3 n log log n), suggesting an AI capable of executing complex verification tasks using highly restricted, low-round quantum communication.

  5. The system can achieve classical lower bounds of R1/3(Cheat-Shapen) ∈ omega R1/3(Shapen) k squared ⊆ omega √n log2 n, indicating an AI that can efficiently solve problems requiring high communication complexity in a randomized setting, potentially improving the efficiency of distributed algorithms or search procedures.

Sources

Related papers