A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Wu, Xudong; Yang, Guangxu; Yao, Penghui

doi:10.4230/LIPIcs.ICALP.2026.155

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Xudong Wu

State Key Laboratory of Novel Software Technology, Nanjing University, China Guangxu Yang

University of Southern California, Los Angeles, CA, USA Penghui Yao

State Key Laboratory of Novel Software Technology, Nanjing University, China
Hefei National Laboratory, China

Abstract

We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form $f\circ G^{n}$ , where $f:\{0,1\}^{n}\to\{\pm 1\}$ and $G$ is an inner product function of $\Theta(\log n)$ bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models.

As a corollary, we show that any hybrid protocol communicating $c$ classical bits followed by $q$ qubits to compute $f\circ G^{n}$ must satisfy $c+q^{2}=\Omega\big(\max\{{\mathrm{deg}}(f),{\mathrm{bs}}(f)\}\cdot\log n\big)$ , where ${\mathrm{deg}}(f)$ is the degree of $f$ and ${\mathrm{bs}}(f)$ is the block sensitivity of $f$ . For read-once formula $f$ , this yields an almost tight trade-off: either they have to exchange $\Theta\big(n\cdot\log n\big)$ classical bits or $\widetilde{\Theta}\big(\sqrt{n}\cdot\log n\big)$ qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.

Keywords and phrases:

Hybrid communication, Generalized discrepancy bound, Dual polynomial, Query-to-communication lifting

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity ; Theory of computation

\rightarrow

Quantum communication complexity

Related Version:

Full Version: https://arxiv.org/abs/2511.17227 [60]

Funding:

Xudong Wu and Penghui Yao were supported by the National Natural Science Foundation of China (Grant No. 62332009 and 12347104), the Quantum Science and Technology-National Science and Technology Major Project (Grant No. 2021ZD0302901), the NSFC/RGC Joint Research Scheme (Grant No. 12461160276), the Natural Science Foundation of Jiangsu Province (No. BK20243060), the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No. JYB2025XDXM118), the “111 Center” (No. B26023), and the Fundamental Research Funds for the Central Universities (Grant No. 2026300376).

DOI:

10.4230/LIPIcs.ICALP.2026.155

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Hybrid quantum computation delegates part of the computation to classical processors, integrating classical control, memory, and processing alongside quantum subroutines that execute essential quantum computations. Since fully fault-tolerant quantum computers have not yet been realized, this model effectively captures the current NISQ (Noisy Intermediate-Scale Quantum) era [48], where quantum hardware remains limited and the classical resources complement and amplify the computational power. A plethora of hybrid algorithms have been proposed, including the Variational Quantum Eigensolver (VQE) [47], Quantum Approximate Optimization Algorithm (QAOA) [19]. Various hybrid quantum computation models have also been studied, demonstrating that quantum computers can achieve polynomial or even exponential advantages over classical computation, as seen the models such as $\textsf{DQC}_{k}$ [35, 45], NISQ [13].

In a parallel line of research, quantum computing has also shown polynomial and even exponential advantages in communication complexity. A substantial body of work has sought the weakest quantum communication model that still outperforms the strongest classical communication model [9, 49, 7, 23, 53, 21, 26, 20, 22, 27, 61]. Unlike time complexity, we have plenty of mathematical tools to prove lower bounds on communication complexity. Consequently, the quantum advantage in communication complexity is unconditional, which does not rely on any unproven computational assumptions.

In the NISQ era, researchers have proposed leveraging the exponential gap between classical and quantum communication to demonstrate quantum advantages. For instance, Kumar, Kerenidis, and Diamanti experimentally implemented a quantum communication protocol for Hidden-matching problem introduced by Bar-Yossef, Jayram, and Kerenidis [7]. Building on this line of work, Aaronson, Buhrman, and Kretschmer introduced the concept of quantum information supremacy [3]: an experimental demonstration in which a quantum device solves a task using significantly fewer qubits than the number of bits required by any classical algorithm. Their proposed task was again based on the classical–quantum exponential separation exhibited in the Hidden-matching problem. Most recently, quantum information supremacy has been experimentally demonstrated using a trapped-ion quantum computer [36].

In this work, we investigate the power of hybrid classical-quantum communication through the lens of communication complexity, aiming to characterize the advantages offered by combining classical and quantum communication resources. We adopt the standard model of communication complexity [62] and that of quantum communication complexity [63], both originally introduced by Yao. In the hybrid classical–quantum communication complexity model, a protocol proceeds in two stages. In the first stage, the parties exchange classical messages and perform local classical computations. In the second stage, they perform local quantum operations and exchange quantum messages. Our focus is on understanding the trade-off between classical and quantum communication costs within this hybrid framework.

1.1 Our results

In this paper, we study the trade-off between classical and quantum communication complexities within the hybrid classical–quantum communication model. A central question we address is whether it is possible to simultaneously reduce both classical and quantum communication costs compared to purely classical or purely quantum protocols. To this end, we investigate the hybrid classical-quantum communication complexity of the function family $f\circ G^{n}$ , where $f$ takes an $n$ -bit input, and $G$ is an inner product function on $\Theta(\log n)$ bits. We establish a hybrid query-to-communication lifting theorem.

Theorem 1 (Informal).

If $f\circ G^{n}$ can be computed by first communicating $c$ classical bits deterministically, followed by communicating $q$ qubits, then there is an $O\big(c/\log n)$ -depth deterministic decision tree for the outer function $f$ such that $f$ restricted to any outcome of the query has approximate degree $O\big(q/\log n\big)$ .

As an application, we prove a lower bound on the classical-quantum communication trade-off.

Theorem 2 (Informal).

If $f\circ G^{n}$ can be computed by first communicating $c$ bits deterministically, followed by communicating $q$ qubits, then $c+q^{2}=\Omega\big(\max\{{\mathrm{deg}}(f),{\mathrm{bs}}(f)\}\cdot\log n\big)$ . In particular, for a read-once formula $f$ , we have a tight trade-off: either $c=\Omega\big(n\log n\big)$ or $q=\Omega\big(\sqrt{n}\log n\big)$ .

Our results refute the possibility that classical pre-processing can reduce the number of subsequent quantum bits. This resembles the result about the trade-off between classical and quantum memory in memory-sample lower bounds for learning studied by Liu, Raz, and Zhan [42].

To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in a hybrid two-way communication model. The research about the lower bounds on classical and quantum communication complexity has a long history [38], while the underlying techniques differ substantially. Classical lower bounds are typically established via combinatorial methods [37], whereas quantum lower bounds often rely on analytic techniques [38]. Moreover, the query-to-communication lifting theorems for the two models were also developed independently. In this paper, we unify these approaches through a novel lifting mechanism, which we believe offers new insights into establishing lower bounds in hybrid communication complexity.

Our main technical tool is the following theorem, which lifts the approximate degree to quantum communication complexity for composed functions restricted to rectangles.

Theorem 3 (Informal).

Let $R=U\times V$ be a rectangle in the input domain of $f\circ G^{n}$ . If the uniform random variables on $U$ and $V$ are both $0.99$ -dense, the quantum communication cost of $f\circ G^{n}$ restricted to $R$ is $\Omega\big({\mathrm{deg}}_{\varepsilon}(f)\cdot\log n\big)$ .

1.2 Related works

Hybrid quantum computation.

Hybrid quantum communication complexity has been explored in several distinct settings. In 2008, Gavinsky, Regev, and de Wolf studied the hybrid simultaneous message passing (SMP) model, in which one party sends a quantum message to a referee, the other sends a classical message, and the referee computes the function. They established an almost tight bound on the quantum-classical communication complexity of EQUALITY in this model [24]. More recently, Arunachalam, Girish, and Lifshitz [6] investigated the one-clean-qubit model of quantum communication, inspired by the quantum circuit complexity class $\textsf{DQC}_{1}$ , where one qubit is in a pure state and all other qubits are maximally mixed. They presented an explicit example demonstrating an exponential separation between the one-clean-qubit model and classical communication. Lin, Wei, and Yao [40] examined the hybrid classical-quantum communication complexity of generating classical correlations between two players – a simpler task than computing a function – and developed several lower bound techniques based on variants of nonnegative ranks and positive semidefinite (PSD) ranks. Despite these advances, the field of hybrid classical–quantum communication complexity remains largely unexplored. In contrast to the well-developed classical and quantum communication frameworks, there currently exist few general techniques for proving lower bounds in the hybrid setting.

The power of hybrid quantum computation has also been studied across a variety of computational models. One particularly relevant line of research concerns hybrid query complexity, a close analog of communication complexity. In the query model, quantum algorithms are allowed a limited number of quantum queries, often interleaved with classical queries. Researchers have developed several powerful techniques to prove lower bounds on hybrid query complexity. Regev and Schiff initiated the study of Grover’s search with a faulty oracle [54], proving that no quantum speedup is possible when each oracle query may fail with small probability. Built on this work, Rosmanis [55] derived a tight bound for preimage search in this setting. Hamoudi, Liu, and Sinha [30] later extend the compressed-oracle framework introduced by Zhandry [64] to establish tight bounds for collision finding in a hybrid query setting. A related line of work [14, 18, 5, 31, 15] have proved lower bounds for hybrid algorithms in the so-called $d$ -QC model, where $d$ quantum queries are interleaved with a polynomial number of classical queries. Sun and Zheng [59] studied decision trees in which each node corresponds to a quantum circuit that makes at most $q$ quantum queries and ends with a measurement. They proved a quantum query complexity lower bound of $\Omega\big({\mathrm{bs}}(f)/q+\sqrt{{\mathrm{bs}}(f)})$ for any function $f$ .

In the context of quantum circuit models, several hybrid computational paradigms have been proposed and studied. Knill and Laflamme [35], followed by subsequent works [45], introduced the $\textsf{DQC}_{k}$ model, where the quantum circuits have access to $k$ clean qubits while the remaining qubits are maximally mixed, to capture the NMR approach to quantum computing. The computational power of $\textsf{DQC}_{k}$ has been extensively studied by a series of works [2, 32, 25]. Chen, Cotler, Huang, and Li have proposed the complexity class NISQ [13] consisting of all problems solvable by a polynomial-time probabilistic classical algorithm equipped with access to a noisy quantum device.

Recently, Liu, Raz, and Zhan [42] initiated the study of learning with classical-quantum hybrid memory. They have established a tight trade-off among classical memory, quantum memory, and sample complexity for several learning tasks, refuting the possibility that a small amount of quantum memory significantly reduces the size of classical memory required for efficient learning on these problems.

Query-to-communication lifting.

Query-to-communication lifting theorems are generic methods for translating query complexity lower bounds to communication complexity lower bounds using a suitable base function composed with a gadget. In classical two-party communication complexity, query-to-communication lifting theorems are known [50, 28, 29, 11, 12, 43, 44] with sufficiently large gadgets. These results have yielded diverse applications in various areas, including monotone circuit complexity, proof complexity, combinatorial optimization, and others. In contrast, for quantum complexity, obtaining a general lifting theorem that translates the lower bounds of the quantum query into the lower bounds of the quantum communication remains a major open problem [4, 10]. A related line of work lifts lower bounds from approximate degree to quantum communication complexity [56, 58, 39]. Notably, these two lines of work rely on fundamentally different techniques, so insights from one do not directly transfer to the other.

Motivated by recent research on hybrid quantum computation, we introduce a new hybrid communication model. To our knowledge, neither of the existing techniques for proving communication lower bounds in the classical or the quantum settings can be directly applied to this hybrid model.

1.3 Proof overview

To prove the trade-off between the classical and quantum communication complexity in our hybrid model, we build upon and unify two independent lines of work on lifting theorems. The first line of work lifts deterministic/randomized query complexity to communication complexity using gadgets of size $\Theta(\log n)$ , such as index functions [29], inner product functions [11], and low discrepancy functions [12]. The second line concerns lifting approximate degree to quantum communication complexity via constant-size gadgets, including index-like functions [56], inner product functions [58], and strongly balanced functions [39]. We combine these two techniques to analyze both the classical and quantum phases in a hybrid communication protocol.

More specifically, consider a protocol that first exchanges $c$ bits in the first phase. It partitions the input domain into $2^{c}$ disjoint rectangles. Suppose that thereafter the parties proceed via $q$ qubits of quantum communication and compute a function $F$ . Restricting to any one of the $2^{c}$ rectangles reduces the problem to a pure quantum communication problem of cost at most $q$ . To lower bound the quantum communication complexity, we apply the generalized discrepancy method: it is known that for any real matrix $\Psi$ supported on rectangle $R$ , we have a lower bound on the quantum communication complexity of $F$ restricted to $R$

\Omega\left(\log\frac{{\langle{F},{\Psi}\rangle}-0.1{\left\lVert{\Psi}\right% \rVert}_{1}}{{\left\lVert{\Psi}\right\rVert}\sqrt{|R|}}\right).

We follow arguments of the approximate-degree to quantum communication complexity lifting framework developed by Sherstov [56]. However, complication and challenge arises, because, in our hybrid model, the rectangle $R$ is inherited from the classical communication in the first phase and may be arbitrary, whereas prior proofs rely on more structure of the input domain.

Our main technical contribution is to introduce a generic condition on rectangles $R$ , which we call density, under which we can still prove quantum communication complexity lower bounds via the approximate degree to quantum communication complexity lifting approach. We believe that this contribution is of independent interest and anticipates further applications. Surprisingly, this “density” property turns out to coincide exactly with the property of rectangles considered in the prior query-to-communication lifting research [29, 11, 12]. Concretely, let $G$ be an inner product gadget of size $\Theta(\log n)$ . For a composed function $F=f\circ G^{n}$ , we select $\Psi=\psi\circ G^{n}$ , where $\psi$ is a dual polynomial as suggested in [56]. On a dense rectangle $R$ , the values of $G^{n}$ over $R$ are nearly uniform. Moreover, once we obtain a dense rectangle $R$ , we could prove a tight lower bound via the generalized discrepancy with more sophisticated analysis. Our analysis relies crucially on the gadget size being $\Theta(\log n)$ and on the linearity of the inner product gadget.

To argue that there exists a dense rectangle $R$ after the classical phase, we follow the framework of query-to-communication lifting to locate a dense rectangle among the $2^{c}$ rectangles, where $c$ is the classical communication cost. The general idea is as follows. We start with $R$ being the entire input domain. With each transmitted bit, $R$ is partitioned into two parts, and the larger one is selected. Whenever $R$ is not dense, we can always fix a set of coordinates $I\subseteq[n]$ such that: by choosing $z\in\{0,1\}^{I}$ arbitrarily, a rectangle $R^{\prime}\subseteq R$ can be found, which satisfies that $G^{I}$ is constant on $R^{\prime}$ (taking the value $z$ ), and $R^{\prime}$ is dense with respect to unfixed coordinates. Then we replace $R$ by $R^{\prime}$ to restore density. For any $f$ and $I\subseteq[n]$ , the coordinates in $I$ can be fixed such that the degree of $f$ decreases by at most $|I|$ . After transmitting $c$ bits, the number of fixed coordinates is at most $O(c/\log n)$ . And the outer function $f$ is equivalent to a function of degree ${\mathrm{deg}}(f)-O(c/\log n)$ (and of approximate degree $\sqrt{{\mathrm{deg}}(f)-O(c/\log n)}$ ) when restricted to $R$ . Our lifting theorem for hybrid classical-quantum communication is obtained by applying approximate degree lifting to dense rectangles.

1.4 Discussion and open problems

Given the advent of the NISQ era, hybrid quantum computation has attracted growing attention in recent years. It is therefore tempting to understand the computational power of hybrid quantum computation across different computational models, from both theoretical and experimental perspectives.

To the best of our knowledge, the trade-off between classical and quantum communication complexity for read-once formulas $f$ is the first (non-trivial) tight trade-off between classical and quantum communication in hybrid two-way communication complexity. Our results refute the possibility that classical pre-processing can substantially reduce the quantum communication required for the function $f\circ G^{n}$ .

We employ the query-to-communication lifting mechanism for both classical and quantum communication complexity – versatile techniques that have been developed over the past decades. Our results give rise to several interesting open problems for future research.

1.

Our result is obtained by combining the query-to-communication lifting theorem [28, 29, 11, 12] for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting theorem [56, 58, 39]. Is it possible to improve our results to obtain a better trade-off: if $c\ll D(f)\cdot\log n$ , then $q=\Omega\big({\mathrm{deg}}_{\varepsilon}(f)\cdot\log n\big)$ ? Is it possible to prove a general query-to-communication lifting theorem for hybrid classical-quantum communication complexity?
2.

Can trade-off analogous to Theorem 2 be established in the hybrid randomized-quantum communication model? The statement $c+q^{2}=\Omega\big({\mathrm{bs}}(f)\cdot\log n\big)$ may hold by considering the hard distribution derived from the generalized discrepancy bound, while the statement for degree is unlikely to hold since the degree can be significantly larger than the randomized query complexity. Is is possible to further prove that $q=\Omega\big({\mathrm{deg}}_{\varepsilon}(f)\cdot\log n\big)$ when $c\ll R(f)\cdot\log n$ by combining query-to-communication lifting for BPP and approximate-degree-to-generalized-discrepancy lifting?
3.

Lifting theorems for both classical and quantum communication complexity have been established for a variety of gadget functions. However, our proofs critically rely on the linearity property of the inner-product gadget. A natural question is therefore whether our results can be generalized to other gadget functions.
4.

This work studies the hybrid classical-quantum communication model, in which players exchange classical messages and quantum messages. What about the quantum-classical communication model, where quantum communication comes first? Is it possible to prove a trade-off for this model, or more generally, for any model that consists of a constant number of alternating purely classical phases and purely quantum phases?
5.

Proving a query-to-communication lifting theorem with a constant-sized gadget for classical communication complexity is a major open problem in communication complexity. Nevertheless, is it possible to prove a lifting theorem for a certain class of outer functions $f$ ? For instance, can we prove a tight trade-off for $f=\mathsf{OR}$ ? It would imply a trade-off for SET DISJOINTNESS, a central problem in communication complexity [33, 51, 8, 52, 57], whose trade-off between classical and quantum communication in hybrid communication complexity is widely open.

2 Preliminaries

Notations.

For a random variable $X\in{\mathcal{X}}$ , denote its distribution by ${\mathcal{D}_{X}}$ . So ${\mathcal{D}_{X}}(x)=\Pr[X=x]$ for $x\in{\mathcal{X}}$ . And for an event $E$ , the random variable $X\mid E$ follows the distribution ${\mathcal{D}_{X}}(\cdot\mid E)$ . For a set $U$ , we write $X\sim U$ to denote that the random variable $X$ is uniformly distributed over $U$ .

Let $n$ be a positive integer and $J\subseteq[n]=\{1,\cdots,n\}$ be a set of coordinates. We define $\bar{J}=[n]\setminus J$ . Let $f:\{0,1\}^{J}\to\{\pm 1\}$ be a Boolean function. For any $K\subseteq J$ and $z\in\{0,1\}^{J\setminus K}$ , define $f_{K,z}:\{0,1\}^{K}\to\{\pm 1\}$ such that

f_{K,z}(x)=f(x,z),\qquad\forall\ x\in\{0,1\}^{K}.

That is, the function $f_{K,z}$ is obtained by fixing the coordinates outside $K$ to be $z$ .

Basic Fourier analysis.

For a Boolean function $f:\{0,1\}^{n}\to{\mathbb{R}}$ , the Fourier expansion gives $f=\sum_{S\subseteq[n]}\widehat{f}_{S}{\chi_{S}}$ , where those ${\chi_{S}}:\{0,1\}^{n}\to\{\pm 1\}$ satisfying ${\chi_{S}}(x)=\prod_{i\in S}(-1)^{x_{i}}$ are orthogonal with respect to the inner product $\langle f,g\rangle=\sum_{x}f(x)g(x)$ . $\widehat{f}_{S}$ are Fourier coefficients of $f$ satisfying $\widehat{f}_{S}=2^{-n}{\langle{f},{{\chi_{S}}}\rangle}$ . For any $1\leq p\leq\infty$ , the $p$ -norm of $f$ is defined to be ${\left\lVert{f}\right\rVert}_{p}=(\sum_{x}|f(x)|^{p})^{1/p}$ . And ${\left\lVert{f}\right\rVert}_{\infty}=\max_{x}|f(x)|$ .

The degree of $f$ , denoted by ${\mathrm{deg}}(f)$ , is the largest size of $S\subseteq[n]$ such that $\widehat{f}_{S}\neq 0$ . For $0\leq\varepsilon<1$ , the $\varepsilon$ -approximate degree of $f$ , denoted by ${\mathrm{deg}}_{\varepsilon}(f)$ , is the smallest degree of any $p:\{0,1\}^{n}\to{\mathbb{R}}$ such that ${\left\lVert{f-p}\right\rVert}_{\infty}\leq\varepsilon$ . The block sensitivity of $f$ on input $x$ , denoted by ${\mathrm{bs}}(f,x)$ , is the largest $k$ such that there are disjoint sets $B_{1},\cdots,B_{k}\subseteq[n]$ such that $f(x)\neq f\left(x^{\oplus B_{i}}\right)$ for each $i\in[k]$ . Here for $x\in\{0,1\}^{n}$ and $S\subseteq[n]$ , $x^{\oplus S}\in\{0,1\}^{n}$ satisfies $x^{\oplus S}_{i}=x_{i}\oplus 1$ for $i\in S$ and $x^{\oplus S}_{i}=x_{i}$ for $i\notin S$ . The block sensitivity of $f$ , denoted by ${\mathrm{bs}}(f)$ , is $\max_{x\in\{0,1\}^{n}}{\mathrm{bs}}(f,x)$ .

There is a dual characterization of the approximate degree. A polynomial $p$ of degree $d$ which approximates $f$ provides a certificate that the approximate degree of $f$ is at most $d$ . Similarly, a dual polynomial for $f$ provides a certificate that the approximate degree of $f$ is at least some value. More precisely, the dual polynomial has the following properties.

Lemma 4 ([56, Theorem 3.2]).

For a function $f:\{0,1\}^{n}\to{\mathbb{R}}$ and $0\leq\varepsilon<1$ , if ${\mathrm{deg}}_{\varepsilon}(f)\geq d$ , there is a function $\psi:\{0,1\}^{n}\to{\mathbb{R}}$ such that

$\blacksquare$

${\left\lVert{\psi}\right\rVert}_{1}=1$ and ${\langle{f},{\psi}\rangle}\geq\varepsilon$ .
$\blacksquare$

$\widehat{\psi}_{S}=0$ for any $S\subseteq[n]$ of size smaller than $d$ .

We are interested in the complexity measure that satisfies: for any function, any coordinate can be fixed such that the measure decreases by at most $1$ . The formal definition is as follows.

Definition 5.

Let $C(\cdot)$ be a complexity measure of the Boolean function $f:\{0,1\}^{*}\to{\mathbb{R}}$ . We say that $C(\cdot)$ is entropic if for any set $J$ of coordinates, any function $f:\{0,1\}^{J}\to{\mathbb{R}}$ , and any coordinate $i\in J$ , there is a $z_{i}\in\{0,1\}$ such that $C\left(f_{J\setminus\{i\},z_{i}}\right)\geq C(f)-1$ .

Proposition 6.

Let $C(\cdot)$ be a complexity measure of the Boolean function $f:\{0,1\}^{*}\to{\mathbb{R}}$ . If $C(\cdot)$ is entropic, for any set $J$ of coordinates, any function $f:\{0,1\}^{J}\to{\mathbb{R}}$ , and any $K\subset J$ , there is a $z\in\{0,1\}^{J\setminus K}$ such that $C\left(f_{K,z}\right)\geq C(f)-(|J|-|K|)$ .

Proof.

Let $\ell=|J|-|K|$ and $J\setminus K=\left\{i_{1},\cdots,i_{\ell}\right\}$ . Let $K^{(0)}=J$ and $K^{(j)}=K^{(j-1)}\setminus\{i_{j}\}$ for every $j\in[\ell]$ . So $K^{(\ell)}=K$ . For any $z\in\{0,1\}^{J\setminus K}$ , let $g^{(0)}=f$ and

g^{(j)}=g^{(j-1)}_{K^{(j)},z_{i_{j}}}=f_{K^{(j)},z_{\{i_{1},\cdots i_{j}\}}}

for every $j\in[\ell]$ . So $g^{(\ell)}=f_{K,z}$ We prove that for every $j\in[\ell]$ , there exists a $z_{J\setminus K^{(j)}}$ such that $C\left(g^{(j)}\right)\geq C(f)-j$ by induction on $j$ .

The base case $j=0$ holds trivially. Assume by the induction hypothesis that there exists a $z_{\{i_{1},\cdots,i_{j-1}\}}$ such that $C\left(g^{(j-1)}\right)\geq C(f)-(j-1)$ for $j\in[\ell]$ . As $C(\cdot)$ is entropic, there exists a $z_{i_{j}}\in\{0,1\}$ such that $C\left(g^{(j)}\right)=C\left(g^{(j-1)}_{K^{(j)},z_{i_{j}}}\right)\geq C\left(g% ^{(j-1)}\right)-1\geq C(f)-j$ . $\hfill\blacktriangleleft$

Proposition 7.

The degree ${\mathrm{deg}}(\cdot)$ is entropic.

Proof.

Let $d={\mathrm{deg}}(f)$ , there is an $I\subseteq J$ such that $|I|=d$ and $\hat{f}_{I}\neq 0$ . For $i\in J$ and $z_{i}\in\{0,1\}$ , let $g=f_{J\setminus\{i\},z_{i}}$ . The Fourier expansion yields

g=\sum_{S\subseteq J\setminus\{i\}}\left(\hat{f}_{S}+\hat{f}_{S\uplus\{i\}}(-1% )^{z_{i}}\right){\chi_{S}}.

So $\hat{g}_{S}=\hat{f}_{S}+\hat{f}_{S\uplus\{i\}}(-1)^{z_{i}}$ for any $S\subseteq J\setminus\{i\}$ . We discuss by cases:

$\blacksquare$

If $i\in I$ , we have $I\setminus\{i\}\subseteq J\setminus\{i\}$ and $\hat{g}_{I\setminus\{i\}}=\hat{f}_{I\setminus\{i\}}+\hat{f}_{I}(-1)^{z_{i}}$ . As $\hat{f}_{I}\neq 0$ , there exists a $z_{i}\in\{0,1\}$ such that $\hat{g}_{I\setminus\{i\}}\neq 0$ , and ${\mathrm{deg}}(g)\geq|I\setminus\{i\}|=d-1$ .
$\blacksquare$

If $i\notin I$ , we have $I\subseteq J\setminus\{i\}$ and $\hat{g}_{I}=\hat{f}_{I}+\hat{f}_{I\uplus\{i\}}(-1)^{z_{i}}$ . As $\hat{f}_{I}\neq 0$ , there exists a $z_{i}\in\{0,1\}$ such that $\hat{g}_{I}\neq 0$ , and ${\mathrm{deg}}(g)\geq|I|=d$ .

In conclusion, there is a $z_{i}\in\{0,1\}$ such that ${\mathrm{deg}}\left(f_{J\setminus\{i\},z_{i}}\right)\geq d-1$ . $\hfill\blacktriangleleft$

Proposition 8.

The block sensitivity ${\mathrm{bs}}(\cdot)$ is entropic.

Proof.

Let $k={\mathrm{bs}}(f)$ , there is an $x\in\{0,1\}^{J}$ and disjoint $B_{1},\cdots,B_{k}$ such that $f(x)\neq f\left(x^{\oplus B_{j}}\right)$ for each $j\in[k]$ . For $i\in J$ , we choose $z_{i}=x_{i}$ , and we have $f_{J\setminus\{i\},z_{i}}\left(x_{J\setminus\{i\}}\right)=f(x)$ .

For $j\in[k]$ such that $i\notin B_{j}$ , we have $B_{j}\subseteq J\setminus\{i\}$ , and

f_{J\setminus\{i\},z_{i}}\left(x_{J\setminus\{i\}}\right)\neq f_{J\setminus\{i% \},z_{i}}\left(x^{\oplus B_{j}}_{J\setminus\{i\}}\right)

since $f(x)\neq f\left(x^{\oplus B_{j}}\right)$ . Among $j\in[k]$ , the number of $B_{j}$ that do not contain $i$ is at least $k-1$ since $B_{1},\cdots,B_{k}$ are disjoint. Therefore, ${\mathrm{bs}}\left(f_{J\setminus\{i\},z_{i}}\right)\geq k-1$ . $\hfill\blacktriangleleft$

2.1 Classical communication complexity

We will employ the model of classical communication complexity introduced by Yao [62]. Let $F:{\mathcal{X}}\times{\mathcal{Y}}\to\{\pm 1\}$ be a function with its input distributed between two parties: Alice knows $x\in{\mathcal{X}}$ and Bob knows $y\in{\mathcal{Y}}$ . Communication complexity studies the minimum number of bits they need to exchange in order to compute the function $F$ .

In the deterministic communication model, a protocol with communication cost $c$ will have Alice and Bob alternately sending $c$ classical bits by round. Alice sends a bit $m_{i}\in\{0,1\}$ in the $i$ -th round for odd $i$ , and Bob sends a bit $m_{i}\in\{0,1\}$ in the $i$ -th round for even $i$ . Therefore, $m_{i}$ is an arbitrary function of $(x,m_{1}\cdots m_{i-1})$ for odd $i$ , and of $(y,m_{1}\cdots m_{i-1})$ for even $i$ , where $(x,y)$ is the input. The string $m_{1}\cdots m_{i}$ is called the transcript of the first $i$ bits for each $i\in[c]$ . The protocol is said to compute $F$ if $(-1)^{m_{c}}=F(x,y)$ for every input $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$ . We use $D(F)$ to denote the least communication cost of a deterministic protocol that computes $F$ .

A typical characterization of a deterministic communication protocol is that it partitions the rectangle ${\mathcal{X}}\times{\mathcal{Y}}$ into disjoint sub-rectangles. That is,

{\mathcal{X}}\times{\mathcal{Y}}=\biguplus_{m\in\{0,1\}^{c}}R_{m}=\biguplus_{m% \in\{0,1\}^{c}}{\mathcal{X}}_{m}\times{\mathcal{Y}}_{m}

such that for each $m\in\{0,1\}^{c}$ , the transcript of the $c$ bits is $m$ on any input $(x,y)\in R_{m}$ .

2.2 Quantum communication complexity

Since Yao introduced quantum communication complexity in 1993 [63], there have been several equivalent ways to describe a $2$ -party quantum communication protocol. Our description follows Lee and Shraibman [38]. The state of a quantum communication protocol can be represented as a vector in a Hilbert space $H_{A}\otimes C\otimes H_{B}$ . Here, $H_{A},H_{B}$ are Hilbert spaces of arbitrary finite dimension that represent workspaces of Alice and Bob, respectively. The Hilbert space $C$ is $2$ -dimensional, and it stands for a $1$ -qubit channel. We assume that $H_{A}$ contains a register to hold the input of Alice, and similarly for $H_{B}$ .

In the model without prior entanglement, the initial state of a quantum communication protocol on input $(x,y)$ is the vector $\ket{x,0}_{H_{A}}\ket{0}_{C}\ket{y,0}_{H_{B}}$ . With prior entanglement, the initial state is a vector of the form $\sum_{w}\alpha_{w}\ket{x,w}_{H_{A}}\ket{0}_{C}\ket{y,w}_{H_{B}}$ , where the coefficients $\alpha_{w}$ are arbitrary complex numbers satisfying $\sum_{w}|\alpha_{w}|^{2}=1$ .

We assume that Alice and Bob speak alternately. On Alice’s turn, she applies an arbitrary unitary transformation of the form $U_{H_{A}C}\otimes I_{B}$ , which acts as the identity on $H_{B}$ . Similarly, on Bob’s turn, he applies a transformation of the form $I_{A}\otimes U_{H_{B}C}$ . At the end of a $t$ -round protocol, we project the final state onto the subspace $H_{A}\otimes\ket{1}\otimes H_{B}$ . Denoting the length of this projection by $p$ , the protocol outputs $-1$ with probability $p^{2}$ , and outputs $1$ otherwise. We say that the communication cost of the protocol is $t$ .

We assume that Alice and Bob exchange quantum messages through a quantum channel, with no intermediate measurements are allowed. It is worth noting that when prior entanglement is allowed, the players can exchange classical bits to teleport quantum states, doubling the total communication cost. This setting is referred to as the Cleve-Buhrman model [17].

For a $2$ -argument function $F:{\mathcal{X}}\times{\mathcal{Y}}\to\{\pm 1\}$ and $0\leq\varepsilon<1$ , a quantum communication protocol is said to compute $F$ with error $\varepsilon$ if it outputs $F(x,y)$ with probability at least $1-\varepsilon$ on any input $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$ . Let $Q_{\varepsilon}(F)$ denote the least communication cost of a quantum protocol without prior entanglement that computes $F$ with error $\varepsilon$ . Define $Q^{*}_{\varepsilon}(F)$ analogously for protocols with prior entanglement.

Generalized discrepancy bound.

The generalized discrepancy method is a useful technique for proving lower bounds on quantum communication complexity, regardless of prior entanglement. This technique is originally discovered by Klauck [34] and Razborov [52]. The generalized discrepancy bound can be established through multiple approaches, including methods based on factorization norms [41] and XOR games [38, Section 5.3]. The following is an adaptation by Sherstov [56].

Theorem 9 ([56, Theorem 2.8]).

Let $U, V$ be finite sets and $F:U\times V\to\{\pm 1\}$ be a given function. Let $\Psi=(\Psi_{uv})_{u\in U,v\in V}$ be any real matrix. For each $\varepsilon>0$ ,

Q^{*}_{\varepsilon}(F)=\Omega\left(\log\frac{{\langle{F},{\Psi}\rangle}-2% \varepsilon{\left\lVert{\Psi}\right\rVert}_{1}}{3{\left\lVert{\Psi}\right% \rVert}\sqrt{|U|\cdot|V|}}\right).

2.3 Hybrid classical-quantum communication

In this work, we are concerned with hybrid classical-quantum communication protocols. A hybrid classical-quantum communication protocol consists of two phases: a classical phase followed by a quantum phase. The protocol begins with the classical phase, during which Alice and Bob alternately and deterministically send classical bits and implement classical local computation. In the subsequent quantum phase, Alice and Bob exchange qubits and implement quantum computation. We assume that the players are allowed to share prior entanglement. It is worth noticing that, in the first phase, both players are implementing classical computation. They do not touch shared entanglement and thus cannot exchange quantum messages via quantum teleportation.

Let ${\mathcal{P}}(c,q)$ be a hybrid protocol with a $c$ -bit classical communication in the first phase followed by a $q$ -qubit quantum communication in the second phase. Without loss of generality, we may assume that $q=o(c)$ since otherwise we may simulate the classical communication by the quantum communication, which only doubles the communication cost.

Suppose that the input to ${\mathcal{P}}$ is drawn from ${\mathcal{X}}\times{\mathcal{Y}}$ . For a function $F:{\mathcal{X}}\times{\mathcal{Y}}\to\{\pm 1\}$ and $0\leq\varepsilon<1$ , ${\mathcal{P}}$ is said to compute $F$ with error $\varepsilon$ if it outputs $F(x,y)$ with probability at least $1-\varepsilon$ on any input $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$ .

After the classical communication phase of $c$ bits, as discussed in Section 2.1, ${\mathcal{X}}\times{\mathcal{Y}}$ is partitioned into disjoint rectangles in the form of ${\mathcal{X}}\times{\mathcal{Y}}=\biguplus_{m\in\{0,1\}^{c}}R_{m}$ , where $R_{m}$ contains all inputs on which the transcript is $m$ for each $m\in\{0,1\}^{c}$ . Let $F_{m}$ denote the function $F$ with its input restricted to $R_{m}$ . The following proposition follows by the definition.

Proposition 10.

If ${\mathcal{P}}(c,q)$ computes $F$ with error $\varepsilon$ , $Q^{*}_{\varepsilon}(F_{m})\leq q$ for each $m\in\{0,1\}^{c}$ .

2.4 Composed functions

An important family of communication functions are composed functions of the form

f\circ G^{n}(x,y)=f\left(G^{n}(x,y)\right)=f\left(G(x_{1},y_{1}),\cdots,G(x_{n% },y_{n})\right),

where $f:\{0,1\}^{n}\to\{\pm 1\}$ is the outer function, and $G:{\mathcal{X}}\times{\mathcal{Y}}\to\{0,1\}$ is the inner function, also known as the gadget. The size of the gadget is defined as $\log\min\{|{\mathcal{X}}|,|{\mathcal{Y}}|\}$ . Lifting theorems typically establish lower bounds of $D(f\circ G^{n})$ , $R_{\varepsilon}(f\circ G^{n})$ , or $Q_{\varepsilon}(f\circ G^{n})$ in terms of some complexity measure of $f$ , such as the deterministic/randomized query complexity and the approximate degree.

In this work, we choose the gadget $G:\Lambda\times\Lambda\to\{0,1\}$ as the inner product function over the Boolean domain, where $\Lambda=\{0,1\}^{b}$ and $b=20\log n$ . We may focus on a set $J\subseteq[n]$ of coordinates, then $x_{J}=(x_{i})_{i\in J}$ and $G^{J}(x,y)=\left(G(x_{i},y_{i})\right)_{i\in J}$ .

Definition 11 (Block-wise density).

Let $J$ be a set of coordinates and $0<\delta\leq 1$ . A random variable $X\in\Lambda^{J}$ is $\delta$ -dense if for every $I\subseteq J$ , it holds that

H_{\infty}(X_{I})=\log\frac{1}{\max_{x\in\Lambda^{I}}{\mathcal{D}_{X_{I}}}(x)}% \geq\delta\cdot b\cdot|I|.

That is, ${\mathcal{D}_{X_{I}}}(x)\leq 2^{-\delta b|I|}$ for all $I\subseteq J$ and $x\in\Lambda^{I}$ .

Lemma 12 ([28, Lemma 13]).

Let $J$ be a set of coordinates and $X,Y\in\Lambda^{J}$ be independent random variables which are $\delta_{X}$ -dense and $\delta_{Y}$ -dense, respectively. If $\delta_{X}+\delta_{Y}\geq 1.4$ , it holds

{\mathcal{D}_{G^{J}(X,Y)}}(z)\in\left(1\pm n^{-2}\right)2^{-|J|},\qquad\forall% \ z\in\{0,1\}^{J}.

It is a key lemma in a line of work on classical query-to-communication lifting [28, 29, 11, 12]. And we will combine it with approaches from another line of work on lifting the approximate degree to quantum communication complexity [56, 58, 39].

3 Quantum Communication Lower Bounds on Dense Rectangles

Here we adopt the generalized discrepancy method in Theorem 9 to prove the hybrid quantum communication complexity. For a composed function $F=f\circ G^{n}$ , a series of works [56, 58, 39] develop conditions on the gadget $G$ under which the approximate degree of any outer function $f$ can be lifted to the quantum communication complexity of $F$ . As stated in Theorem 9, any witness matrix $\Psi$ of the same dimension as $F$ reveals a lower bound on the quantum communication complexity of $F$ . A natural choice is to set $\Psi=\psi\circ G^{n}$ , where $\psi$ is a dual polynomial of $f$ as stated in Lemma 4. As $\psi=\sum_{S\subseteq[n]}\widehat{\psi}_{S}{\chi_{S}}$ , we have $\Psi=\sum_{S\subseteq[n]}\widehat{\psi}_{S}M_{S}$ , where $M_{S}={\chi_{S}}\circ G^{n}$ . It has been proved that the matrices $M_{S}$ are strongly orthogonal (that is, $M_{S}M_{T}^{\mathrm{T}}=M_{S}^{\mathrm{T}}M_{T}=0$ for $S\neq T$ ) to each other for nice gadgets, such that it enables us to prove tight lower bounds.

Let $n$ be sufficiently large. Recall that our gadget $G:\Lambda\times\Lambda\to\{0,1\}$ is the inner product function over the Boolean domain, where $\Lambda=\{0,1\}^{b}$ and $b=20\log n$ .

When the input of $f\circ G^{n}$ is restricted to a rectangle, the sub-matrices of matrices $M_{S}$ obtained by restricting $M_{S}$ to a rectangle are no longer strongly orthogonal to each other. The following result is our main technical result, which says that the matrix $\Psi=\psi\circ G^{n}$ restricted to the same rectangle can still be used to show strong quantum communication lower bounds, as long as the size of the gadget $b=\Theta(\log n)$ is sufficiently large (while in [56, 58, 39], the size of the gadget can be constant), and the rectangle satisfies certain density properties.

Theorem 13.

Let $J\subseteq[n]$ be a set of coordinates and $\ell$ be an arbitrary finite number. For sets $U,V\subseteq\Lambda^{J}\times\{0,1\}^{\ell}$ , let the joint random variables $(X,A)$ be uniformly distributed over $U$ and $(Y,B)$ be uniformly distributed over $V$ , where $X,Y\in\Lambda^{J}$ . For any function $f:\{0,1\}^{J}\to\{\pm 1\}$ , define $F:U\times V\to\{\pm 1\}$ such that

F(u,v)=f(G^{J}(x,y)),\qquad\forall\ u=(x,a)\in U,v=(y,b)\in V.

If $X$ and $Y$ are both $0.99$ -dense,

Q^{*}_{0.1}(F)=\Omega\left({\mathrm{deg}}_{1/3}(f)\cdot b\right).

Proof.

Let $R$ be the rectangle $U\times V$ , $m=|J|$ and $d={\mathrm{deg}}_{1/3}(f)$ . Let $\psi$ be the dual polynomial which certifies that ${\mathrm{deg}}_{1/3}(f)\geq d$ as in Lemma 4. We have

$\blacksquare$

${\left\lVert{\psi}\right\rVert}_{1}=1$ and ${\langle{f},{\psi}\rangle}\geq 1/3$ .
$\blacksquare$

$\widehat{\psi}_{S}=0$ for any $S\subseteq[n]$ of size smaller than $d$ .

The hardness of computing $F$ with error $0.1$ can be proved by choosing the matrix $\Psi:U\times V\to{\mathbb{R}}$ that satisfies $\Psi(u,v)=\frac{2^{m}}{|R|}\psi(G^{J}(x,y))$ for every $u=(x,a)\in U,v=(y,b)\in V$ , and applying Theorem 9. The task is to bound ${\left\lVert{\Psi}\right\rVert}_{1}$ , ${\langle{F},{\Psi}\rangle}$ , and ${\left\lVert{\Psi}\right\rVert}$ .

Lemma 14.

${\left\lVert{\Psi}\right\rVert}_{1}\leq 1.01$ and ${\langle{F},{\Psi}\rangle}\geq 0.31$ .

Lemma 15.

${\left\lVert{\Psi}\right\rVert}\sqrt{|R|}\leq n^{-1.1d}$ .

Combining Lemma 14, Lemma 15 with Theorem 9, we have

Q^{*}_{0.1}(F)=\Omega\left(\log\frac{{\langle{F},{\Psi}\rangle}-0.2{\left% \lVert{\Psi}\right\rVert}_{1}}{3{\left\lVert{\Psi}\right\rVert}\sqrt{|R|}}% \right)=\Omega(d\cdot b).\

$\hfill\blacktriangleleft$

The rest of this section proves Lemma 14 and Lemma 15.

Proof of Lemma 14.

By the choice of $\Psi$ ,

	$\displaystyle{\left\lVert{\Psi}\right\rVert}_{1}$	$\displaystyle=\sum_{\begin{subarray}{c}(x,a)\in U\\ (y,b)\in V\end{subarray}}\frac{2^{m}}{\|R\|}{\left\|{\psi(G^{J}(x,y))}\right\|}$
		$\displaystyle=\sum_{z\in\{0,1\}^{J}}\frac{2^{m}}{\|R\|}\|\psi(z)\|\cdot{\left\|{% \left\{((x,a),(y,b))\in R:G^{J}(x,y)=z\right\}}\right\|}.$

Note that

{\mathcal{D}_{G^{J}(X,Y)}}(z)=\frac{{\left|{\left\{((x,a),(y,b))\in R:G^{J}(x,% y)=z\right\}}\right|}}{|R|}

as the joint random variable $((X,A),(Y,B))$ is uniformly distributed over $R$ . Then

{\left\lVert{\Psi}\right\rVert}_{1}=\sum_{z\in\{0,1\}^{J}}2^{m}|\psi(z)|\cdot{% \mathcal{D}_{G^{J}(X,Y)}}(z)\leq 1.01{\left\lVert{\psi}\right\rVert}_{1}=1.01.

The inequality is because $X, Y$ are $0.99$ -dense. By Lemma 12,

{\mathcal{D}_{G^{J}(X,Y)}}(z)\leq\left(1+n^{-2}\right)2^{-m}\leq 1.01\cdot 2^{% -m},

for any $z\in\{0,1\}^{J}$ . The inner product term can be bounded in a similar way:

	$\displaystyle{\langle{F},{\Psi}\rangle}$	$\displaystyle=\sum_{\begin{subarray}{c}(x,a)\in U\\ (y,b)\in V\end{subarray}}f(G^{J}(x,y))\cdot\frac{2^{m}}{\|R\|}\psi(G^{J}(x,y))$
		$\displaystyle=\sum_{z\in\{0,1\}^{J}}2^{m}f(z)\psi(z)\cdot{\mathcal{D}_{G^{J}(X% ,Y)}}(z)$
		$\displaystyle\geq 0.99{\langle{f},{\psi}\rangle}-0.02{\left\lVert{\psi}\right% \rVert}_{1}\geq 0.31.\$

$\hfill\blacktriangleleft$

Proof of Lemma 15.

To bound the spectral norm, we have ${\left\lVert{\Psi}\right\rVert}\leq\left({\mathrm{tr}}\left(\Psi\Psi^{\mathrm{% T}}\right)^{p}\right)^{\frac{1}{2p}}$ for any $p\geq 1$ . We choose $p=2$ . As $\widehat{\psi}_{S}=0$ for every $S\subseteq J$ such that $|S|<d$ , $\psi=\sum_{S\subseteq J:|S|\geq d}\widehat{\psi}_{S}{\chi_{S}}$ .

\Psi=\frac{2^{m}}{|R|}\sum_{S\subseteq J:|S|\geq d}\widehat{\psi}_{S}M_{S},

where $M_{S}(u,v)={\chi_{S}}(G^{J}(x,y))$ for every $u=(x,a)\in U,v=(y,b)\in V$ . We have

	$\displaystyle{\mathrm{tr}}\left(\Psi\Psi^{\mathrm{T}}\right)^{2}$	$\displaystyle=\frac{2^{4m}}{\|R\|^{4}}\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2}% ,T_{2}\subseteq J\\ \|S_{1}\|,\|T_{1}\|,\|S_{2}\|,\|T_{2}\|\geq d\end{subarray}}\widehat{\psi}_{S_{1}}% \widehat{\psi}_{T_{1}}\widehat{\psi}_{S_{2}}\widehat{\psi}_{T_{2}}{\mathrm{tr}% }\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T}}\right)$
		$\displaystyle\leq\frac{1}{\|R\|^{4}}\sum_{S_{1},T_{1},S_{2},T_{2}}{\left\|{{% \mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T% }}\right)}\right\|}.$		(1)

The inequality is because that $|\widehat{\psi}_{S}|\leq 2^{-m}{\left\lVert{\psi}\right\rVert}_{1}\leq 2^{-m}$ for any $S\subseteq J$ . The following states that each term of the summation in Equation 1 can be bounded in terms of $|S_{1}|+|T_{1}|+|S_{2}|+|T_{2}|$ .

Proposition 16.

For any $S_{1},T_{1},S_{2},T_{2}\subseteq J$ ,

\frac{1}{|R|^{2}}{\left|{{\mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{% S_{2}}M_{T_{2}}^{\mathrm{T}}\right)}\right|}\leq 2^{-0.11b(|S_{1}|+|T_{1}|+|S_% {2}|+|T_{2}|)}.

We prove Proposition 16 after showing that it implies Lemma 15. Now according to Equation 1,

	$\displaystyle{\left\lVert{\Psi}\right\rVert}\sqrt{\|R\|}$	$\displaystyle\leq\left({\mathrm{tr}}\left(\Psi\Psi^{\mathrm{T}}\right)^{2}% \right)^{1/4}\sqrt{\|R\|}$
		$\displaystyle\leq\left(\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2},T_{2}% \subseteq J\\ \|S_{1}\|,\|T_{1}\|,\|S_{2}\|,\|T_{2}\|\geq d\end{subarray}}\frac{1}{\|R\|^{2}}{\left\|{{% \mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T% }}\right)}\right\|}\right)^{1/4}$
		$\displaystyle\leq\left(\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2},T_{2}% \subseteq J\\ \|S_{1}\|,\|T_{1}\|,\|S_{2}\|,\|T_{2}\|\geq d\end{subarray}}2^{-0.11b(\|S_{1}\|+\|T_{1}\|+% \|S_{2}\|+\|T_{2}\|)}\right)^{1/4}$
		$\displaystyle=\sum_{S\subseteq J:\|S\|\geq d}2^{-0.11b\|S\|}\leq n^{-1.1d},\$

$\hfill\blacktriangleleft$

Proof of Proposition 16.

The trace term ${\mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{% T}}\right)$ can be expanded as

\sum_{\begin{subarray}{c}(x_{1},a_{1}),(x_{2},a_{2})\in U\\ (y_{1},b_{1}),(y_{2},b_{2})\in V\end{subarray}}{\chi_{S_{1}}}(G^{J}(x_{1},y_{1% })){\chi_{T_{1}}}(G^{J}(x_{2},y_{1})){\chi_{S_{2}}}(G^{J}(x_{2},y_{2})){\chi_{% T_{2}}}(G^{J}(x_{1},y_{2})).

For any $I,K\subseteq J$ , $x\in\Lambda^{I},y\in\Lambda^{K}$ , and $S\subseteq I\cap K$ , define ${\chi_{S}}(x,y)=(-1)^{{\langle{x_{S}},{y_{S}}\rangle}}$ . By replacing the summation over $U, V$ with a summation over the entire $\Lambda^{J}$ and taking the corresponding probabilities, $\frac{1}{|R|^{2}}{\mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_% {T_{2}}^{\mathrm{T}}\right)$ is equal to

		$\displaystyle\sum_{x_{1},x_{2},y_{1},y_{2}\in\Lambda^{J}}\mathcal{D}_{X}^{% \otimes 2}(x_{1}x_{2})\mathcal{D}_{Y}^{\otimes 2}(y_{1}y_{2})\cdot{\chi_{S_{1}% }}(x_{1},y_{1}){\chi_{T_{1}}}(x_{2},y_{1}){\chi_{S_{2}}}(x_{2},y_{2}){\chi_{T_% {2}}}(x_{1},y_{2})$
	$\displaystyle=$	$\displaystyle\sum_{\begin{subarray}{c}x_{1}\in\Lambda^{S_{1}\cup T_{2}},x_{2}% \in\Lambda^{S_{2}\cup T_{1}}\\ y_{1}\in\Lambda^{S_{1}\cup T_{1}},y_{2}\in\Lambda^{S_{2}\cup T_{2}}\end{% subarray}}{\mathcal{D}_{X_{S_{1}\cup T_{2}}}}(x_{1}){\mathcal{D}_{X_{S_{2}\cup T% _{1}}}}(x_{2}){\mathcal{D}_{Y_{S_{1}\cup T_{1}}}}(y_{1}){\mathcal{D}_{Y_{S_{2}% \cup T_{2}}}}(y_{2})\cdot{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}$
	$\displaystyle=$	$\displaystyle\sum_{\begin{subarray}{c}x_{1}x_{2}\in\Lambda^{S_{1}\cup T_{2}}% \times\Lambda^{S_{2}\cup T_{1}}\\ y_{1}y_{2}\in\Lambda^{S_{1}\cup T_{1}}\times\Lambda^{S_{2}\cup T_{2}}\end{% subarray}}{\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{\mathcal{D}_{X_{S_{2}\cup T% _{1}}}}(x_{1}x_{2}){\mathcal{D}_{Y_{S_{1}\cup T_{1}}}}\otimes{\mathcal{D}_{Y_{% S_{2}\cup T_{2}}}}(y_{1}y_{2}){\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}},$

where we define the matrix ${\mathcal{M}}\in\{\pm 1\}^{\left(\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S_{2}% \cup T_{1}}\right)\times\left(\Lambda^{S_{1}\cup T_{1}}\times\Lambda^{S_{2}% \cup T_{2}}\right)}$ by

{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}={\chi_{S_{1}}}(x_{1},y_{1}){\chi_{T_{1}}% }(x_{2},y_{1}){\chi_{S_{2}}}(x_{2},y_{2}){\chi_{T_{2}}}(x_{1},y_{2}).

For random variables $A$ and $B$ , let $A\otimes B$ denote the joint random variable $(A,B)$ with $A$ and $B$ being independent. The distribution ${\mathcal{D}_{A}}\otimes{\mathcal{D}_{B}}$ can be written as ${\mathcal{D}_{A\otimes B}}$ . We have

	$\displaystyle\frac{1}{\|R\|^{2}}{\left\|{{\mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{% \mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T}}\right)}\right\|}$	$\displaystyle={\left\|{\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{% \mathcal{D}_{X_{S_{2}\cup T_{1}}}}\right)^{\mathrm{T}}{\mathcal{M}}\left({% \mathcal{D}_{Y_{S_{1}\cup T_{1}}}}\otimes{\mathcal{D}_{Y_{S_{2}\cup T_{2}}}}% \right)}\right\|}$
		$\displaystyle\leq{\left\lVert{\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes% {\mathcal{D}_{X_{S_{2}\cup T_{1}}}}\right)^{\mathrm{T}}{\mathcal{M}}}\right% \rVert}\cdot{\left\lVert{{\mathcal{D}_{Y_{S_{1}\cup T_{1}}}}\otimes{\mathcal{D% }_{Y_{S_{2}\cup T_{2}}}}}\right\rVert},$

For the second term, ${\left\lVert{{\mathcal{D}_{Y_{S_{1}\cup T_{1}}}}\otimes{\mathcal{D}_{Y_{S_{2}% \cup T_{2}}}}}\right\rVert}\leq 2^{-0.99b(|S_{1}\cup T_{1}|+|S_{2}\cup T_{2}|)% /2}$ as $Y$ is $0.99$ -dense. For the first term, ${\left\lVert{\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{\mathcal{D}_{X_{% S_{2}\cup T_{1}}}}\right)^{\mathrm{T}}{\mathcal{M}}}\right\rVert}^{2}$ equals to

	$\displaystyle\sum_{y_{1}y_{2}\in\Lambda^{S_{1}\cup T_{1}}\times\Lambda^{S_{2}% \cup T_{2}}}\left(\sum_{x_{1}x_{2}\in\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S% _{2}\cup T_{1}}}\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{\mathcal{D}_{% X_{S_{2}\cup T_{1}}}}\right)(x_{1}x_{2}){\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}% \right)^{2}$
$\displaystyle=$	$\displaystyle\sum_{y_{1}y_{2}}\sum_{x_{1}x_{2},x^{\prime}_{1}x^{\prime}_{2}}{% \mathcal{D}_{X_{S_{1}\cup T_{2}}\otimes X_{S_{2}\cup T_{1}}}}(x_{1}x_{2}){% \mathcal{D}_{X_{S_{1}\cup T_{2}}\otimes X_{S_{2}\cup T_{1}}}}(x^{\prime}_{1}x^% {\prime}_{2}){\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime}_{1% }x^{\prime}_{2},y_{1}y_{2}}$
$\displaystyle=$	$\displaystyle\sum_{x_{1}x_{2},x^{\prime}_{1}x^{\prime}_{2}}{\mathcal{D}_{X_{S_% {1}\cup T_{2}}\times X_{S_{2}\cup T_{1}}}}(x_{1}x_{2}){\mathcal{D}_{X_{S_{1}% \cup T_{2}}\otimes X_{S_{2}\cup T_{1}}}}(x^{\prime}_{1}x^{\prime}_{2})\sum_{y_% {1}y_{2}}{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime}_{1}x^{% \prime}_{2},y_{1}y_{2}}$
$\displaystyle\leq$	$\displaystyle\sum_{x_{1}x_{2},x^{\prime}_{1}x^{\prime}_{2}}2^{-0.99b(\|S_{1}% \cup T_{2}\|+\|S_{2}\cup T_{1}\|)\cdot 2}{\left\|{\sum_{y_{1}y_{2}}{\mathcal{M}}_{% x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime}_{1}x^{\prime}_{2},y_{1}y_{2}}}% \right\|}.$	(2)

The inequality is because $X$ is $0.99$ -dense. For any $x_{1}x_{2},x^{\prime}_{1}x^{\prime}_{2}\in\Lambda^{S_{1}\cup T_{2}}\times% \Lambda^{S_{2}\cup T_{1}}$ , by setting $w_{1}=x_{1}\oplus x^{\prime}_{1}\in\Lambda^{S_{1}\cup T_{2}}$ and $w_{2}=x_{2}\oplus x^{\prime}_{2}\in\Lambda^{S_{2}\cup T_{1}}$ ,

		$\displaystyle\sum_{y_{1}y_{2}\in\Lambda^{S_{1}\cup T_{1}}\times\Lambda^{S_{2}% \cup T_{2}}}{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime}_{1}% x^{\prime}_{2},y_{1}y_{2}}$
	$\displaystyle=$	$\displaystyle\sum_{y_{1}y_{2}}{\chi_{S_{1}}}(w_{1},y_{1}){\chi_{T_{1}}}(w_{2},% y_{1}){\chi_{S_{2}}}(w_{2},y_{2}){\chi_{T_{2}}}(w_{1},y_{2})$
	$\displaystyle=$	$\displaystyle\sum_{y_{1}y_{2}}{\chi_{A_{1}}}(w_{1}\oplus w_{2},y_{1}){\chi_{B_% {1}}}(w_{1},y_{1}){\chi_{C_{1}}}(w_{2},y_{1}){\chi_{A_{2}}}(w_{1}\oplus w_{2},% y_{2}){\chi_{B_{2}}}(w_{2},y_{2}){\chi_{C_{2}}}(w_{1},y_{2}),$

where $A_{1}=S_{1}\cap T_{1},B_{1}=S_{1}\setminus T_{1},C_{1}=T_{1}\setminus S_{1}$ are disjoint, and $A_{2}=S_{2}\cap T_{2},B_{2}=S_{2}\setminus T_{2},C_{2}=T_{2}\setminus S_{2}$ are disjoint. Let $\Gamma_{A}(w)$ denote $\sum_{y\in\Lambda^{A}}{\chi_{A}}(w,y)$ . We have

\Gamma_{A}(w)=\left\{\begin{aligned} &2^{b|A|},&&\text{if }w_{A}=0.\\ &0,&&\text{otherwise}.\end{aligned}\right.

And

\sum_{y_{1}y_{2}}{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime% }_{1}x^{\prime}_{2},y_{1}y_{2}}=\Gamma_{A_{1}}(w_{1}\oplus w_{2})\Gamma_{B_{1}% }(w_{1})\Gamma_{C_{1}}(w_{2})\Gamma_{A_{2}}(w_{1}\oplus w_{2})\Gamma_{B_{2}}(w% _{2})\Gamma_{C_{2}}(w_{1}).

We say that $w_{1}w_{2}$ is valid if

(w_{1})_{A_{1}\cup A_{2}}=(w_{2})_{A_{1}\cup A_{2}},(w_{1})_{B_{1}\cup C_{2}}=% 0,(w_{2})_{C_{1}\cup B_{2}}=0.

Therefore,

\sum_{y_{1}y_{2}}{\mathcal{M}}_{x_{1}x_{2},y_{1}y_{2}}{\mathcal{M}}_{x^{\prime% }_{1}x^{\prime}_{2},y_{1}y_{2}}=\left\{\begin{aligned} &2^{b(|S_{1}\cup T_{1}|% +|S_{2}\cup T_{2}|)},&&\text{if }w_{1}w_{2}\text{ is valid}.\\ &0,&&\text{otherwise}.\end{aligned}\right.

(3)

Proposition 17.

The number of valid $w_{1}w_{2}\in\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S_{2}\cup T_{1}}$ is at most

2^{b(|S_{1}\cup T_{2}|+|S_{2}\cup T_{1}|)}\cdot 2^{-b(|S_{1}|+|T_{1}|+|S_{2}|+% |T_{2}|)/4}.

The proof of Proposition 17 is postponed. The number of $x_{1}x_{2},x^{\prime}_{1}x^{\prime}_{2}\in\Lambda^{S_{1}\cup T_{2}}\times% \Lambda^{S_{2}\cup T_{1}}$ such that $w_{1}w_{2}$ is valid (where $w_{1}=x_{1}\oplus x^{\prime}_{1}$ and $w_{2}=x_{2}\oplus x_{2}$ ) will be $2^{b(|S_{1}\cup T_{2}|+|S_{2}\cup T_{1}|)}$ times the number of valid values in $\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S_{2}\cup T_{1}}$ . Hence by combining Equation 2, Equation 3 with Proposition 17, ${\left\lVert{\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{\mathcal{D}_{X_{% S_{2}\cup T_{1}}}}\right)^{\mathrm{T}}{\mathcal{M}}}\right\rVert}^{2}$ is at most

2^{-0.99b(|S_{1}\cup T_{2}|+|S_{2}\cup T_{1}|)\cdot 2}\cdot 2^{2b(|S_{1}\cup T% _{2}|+|S_{2}\cup T_{1}|)}\cdot 2^{-b(|S_{1}|+|T_{1}|+|S_{2}|+|T_{2}|)/4}\cdot 2% ^{b(|S_{1}\cup T_{1}|+|S_{2}\cup T_{2}|)}.

In conclusion,

		$\displaystyle\frac{1}{\|R\|^{2}}{\left\|{{\mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{% \mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T}}\right)}\right\|}$
	$\displaystyle\leq$	$\displaystyle\ {\left\lVert{\left({\mathcal{D}_{X_{S_{1}\cup T_{2}}}}\otimes{% \mathcal{D}_{X_{S_{2}\cup T_{1}}}}\right)^{\mathrm{T}}{\mathcal{M}}}\right% \rVert}\cdot{\left\lVert{{\mathcal{D}_{Y_{S_{1}\cup T_{1}}}}\otimes{\mathcal{D% }_{Y_{S_{2}\cup T_{2}}}}}\right\rVert}$
	$\displaystyle\leq$	$\displaystyle\ 2^{0.01b(\|S_{1}\cup T_{2}\|+\|S_{2}\cup T_{1}\|)}\cdot 2^{-b(\|S_{1% }\|+\|T_{1}\|+\|S_{2}\|+\|T_{2}\|)/8}\cdot 2^{0.005b(\|S_{1}\cup T_{1}\|+\|S_{2}\cup T_{% 2}\|)}$
	$\displaystyle\leq$	$\displaystyle\ 2^{-0.11b(\|S_{1}\|+\|T_{1}\|+\|S_{2}\|+\|T_{2}\|)},$

which is as required by Proposition 16. $\hfill\blacktriangleleft$

Proof of Proposition 17.

The number of coordinates of $w_{1}w_{2}$ is $|S_{1}\cup T_{2}|+|S_{2}\cup T_{1}|$ , and there are $b$ bits on each coordinates. Some coordinates are fixed by the validity condition of $w_{1}w_{2}$ , while the others are totally free. The number of fixed coordinates is at least $|S_{1}\cup T_{1}\cup S_{2}\cup T_{2}|$ . See Figure 1 for an illustration. A formal proof is given below.

Figure 1: An illustration of valid

w_{1}w_{2}\in\Lambda^{(A_{1}\uplus B_{1})\cup(A_{2}\uplus C_{2})}\times\Lambda% ^{(A_{1}\uplus C_{1})\cup(A_{2}\uplus B_{2})}

. The coordinates outlined by the thick black line are those of

w_{1}w_{2}

. A valid

w_{1}w_{2}

satisfies:

(w_{1})_{A_{1}\cup A_{2}}=(w_{2})_{A_{1}\cup A_{2}}

,

(w_{1})_{B_{1}\cup C_{2}}=0

, and

(w_{2})_{C_{1}\cup B_{2}}=0

. The coordinates outlined by the blue line require that

w_{1}

and

w_{2}

be identical. So on the coordinates within the yellow and green area,

w_{1}w_{2}

must be all

0

. On the coordinates in the blue area,

w_{2}

must agree with

w_{1}

. For the rest of the coordinates, the choice can be arbitrary.

The number of valid $w_{1}w_{2}\in\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S_{2}\cup T_{1}}$ is

		$\displaystyle\sum_{w_{1}w_{2}\in\Lambda^{S_{1}\cup T_{2}}\times\Lambda^{S_{2}% \cup T_{1}}}{\mathbbm{1}}\left[(w_{1})_{A_{1}\cup A_{2}}=(w_{2})_{A_{1}\cup A_% {2}}\wedge(w_{1})_{B_{1}\cup C_{2}}=0\wedge(w_{2})_{C_{1}\cup B_{2}}=0\right]$
	$\displaystyle=$	$\displaystyle\sum_{w_{1}\in\Lambda^{S_{1}\cup T_{2}}}{\mathbbm{1}}\left[(w_{1}% )_{B_{1}\cup C_{2}}=0\right]\sum_{w_{2}\in\Lambda^{S_{2}\cup T_{1}}}{\mathbbm{% 1}}\left[(w_{2})_{A_{1}\cup A_{2}}=(w_{1})_{A_{1}\cup A_{2}}\wedge(w_{2})_{C_{% 1}\cup B_{2}}=0\right].$

Fix any $w_{1}\in\Lambda^{S_{1}\cup T_{2}}$ . As $A_{1}\cup A_{2}\cup C_{1}\cup B_{2}=(A_{1}\uplus C_{1})\cup(A_{2}\uplus B_{2})% =S_{2}\cup T_{1}$ , the number of $w_{2}\in\Lambda^{S_{2}\cup T_{1}}$ satisfying $(w_{2})_{A_{1}\cup A_{2}}=(w_{1})_{A_{1}\cup A_{2}}$ and $(w_{2})_{C_{1}\cup B_{2}}=0$ is at most $1$ . The number of valid $w_{1}w_{2}$ is at most

\sum_{w_{1}\in\Lambda^{S_{1}\cup T_{2}}}{\mathbbm{1}}\left[(w_{1})_{B_{1}\cup C% _{2}}=0\right]=2^{b\left(|S_{1}\cup T_{2}|-|B_{1}\cup C_{2}|\right)}=2^{b\left% (|S_{1}\cup T_{2}|+|S_{2}\cup T_{1}|\right)}\cdot 2^{-b\left(|B_{1}\cup C_{2}|% +|S_{2}\cup T_{1}|\right)}.

And $|B_{1}\cup C_{2}|+|S_{2}\cup T_{1}|\geq|B_{1}\cup C_{2}\cup S_{2}\cup T_{1}|=|% S_{1}\cup T_{1}\cup S_{2}\cup T_{2}|\geq\frac{|S_{1}|+|T_{1}|+|S_{2}|+|T_{2}|}% {4}$ . $\hfill\blacktriangleleft$

4 A Decision Tree Yielding Dense Rectangles

We apply the techniques developed in a series of works on classical query-to-communication lifting [29, 11, 12]. Those works consider the composed function $f\circ G^{n}$ with arbitrary outer function $f:\{0,1\}^{n}\to\{\pm 1\}$ and some size $\Theta(\log n)$ -sized gadget $G$ . The gadget is chosen to be the index function [29], the inner product function over the Boolean domain [11], or any function with low discrepancy [12]. A decision tree for $f$ is constructed based on the communication protocol for $f\circ G^{n}$ by keeping the rectangles being dense.

Let $n$ be sufficiently large. Recall that our gadget $G:\Lambda\times\Lambda\to\{0,1\}$ is the inner product function over the Boolean domain, where $\Lambda=\{0,1\}^{b}$ and $b=20\log n$ .

Definition 18 (Density of rectangles).

Let $J\subseteq[n]$ be a set of coordinates and $z\in\{0,1\}^{\bar{J}}$ . For sets $U,V\subseteq\Lambda^{n}$ , let the random variables $X$ be uniformly distributed over $U$ and $Y$ be uniformly distributed over $V$ . The rectangle $R=U\times V$ is dense on $(J,z)$ if

$\blacksquare$

$G^{\bar{J}}(x,y)=z$ for any $(x,y)\in R$ .
$\blacksquare$

$X_{J}$ and $Y_{J}$ are both $0.99$ -dense.

Throughout this section, we consider a hybrid classical-quantum communication protocol ${\mathcal{P}}$ that takes the input from $\Lambda^{n}\times\Lambda^{n}$ , and exchages $c$ bits in the classical communication phase. As discussed in Section 2.3, $\Lambda^{n}\times\Lambda^{n}$ is partitioned into disjoint rectangles in the form of $\Lambda^{n}\times\Lambda^{n}=\biguplus_{m\in\{0,1\}^{c}}R_{m}$ such that for each $m\in\{0,1\}^{c}$ , the transcript is $m$ on any input $(x,y)\in R_{m}$ .

The following lemma shows that there is a decision tree such that a rectangle within some $R_{m}$ can be found, which is dense on the unqueried coordinates and consistent with the queried ones. The analysis follows the deterministic query-to-communication lifting in [11]. Initially $J=[n]$ is the set of unqueried coordinates and $R=\Lambda^{n}\times\Lambda^{n}$ . Whenever a bit is transmitted in ${\mathcal{P}}$ , $R$ is partitioned into two rectangles, and we retain the larger one. Intuitively whenever $R$ is not dense on $J$ , we can make queries to some $I\subset J$ and find a rectangle $R^{\prime}\subseteq R$ such that $R^{\prime}$ becomes dense on $J\setminus I$ and $G^{I}$ is consistent with the query answer on $R^{\prime}$ .

Lemma 19.

For a protocol ${\mathcal{P}}$ that takes the input from $\Lambda^{n}\times\Lambda^{n}$ and uses $c$ bits of deterministic communication, let $\Lambda^{n}\times\Lambda^{n}=\biguplus_{m\in\{0,1\}^{c}}R_{m}$ be a partition such that for each $m\in\{0,1\}^{c}$ , the transcript of ${\mathcal{P}}$ is $m$ on any input $(x,y)\in R_{m}$ . There exists a deterministic decision tree which queries at most $\frac{200c}{b}$ coordinates in $[n]$ such that: for any outcome of the query, there is a transcript $m\in\{0,1\}^{c}$ and a rectangle $R\subseteq R_{m}$ being dense on $(J,z)$ , where $J\subseteq[n]$ is the set of unqueried coordinates and $z\in\{0,1\}^{\bar{J}}$ is the query answer.

To prove Lemma 19, the following results in [11] would be useful.

Proposition 20 ([11, Proposition 11]).

Let $J$ be a set of coordinates and $0<\delta\leq 1$ . For a random variable $X\in\Lambda^{J}$ , let $I\subseteq J$ be any maximal subset such that $H_{\infty}(X_{I})<\delta\cdot b\cdot|I|$ . Let $\alpha\in\Lambda^{I}$ be any value such that ${\mathcal{D}_{X_{I}}}(\alpha)>2^{-\delta b|I|}$ . Then $X_{J\setminus I}\mid X_{I}=\alpha$ is $\delta$ -dense.

Definition 21.

Let $J$ be a set of coordinates and $\alpha\in\Lambda^{J}$ and $0<\delta\leq 1$ . For a random variable $Y\in\Lambda^{J}$ , $\alpha$ is $\delta$ -bad for $Y$ if there is an $I\subseteq J$ and a $z\in\{0,1\}^{I}$ such that $Y_{J\setminus I}\mid G^{I}(\alpha,Y)=z$ is not $\delta$ -dense, or ${\mathcal{D}_{G^{I}(\alpha,Y)}}(z)<2^{-|I|-1}$ .

Lemma 22 ([11, Theorem 7]).

Let $J$ be a set of coordinates and $X,Y\in\Lambda^{J}$ be independent random variables which are $\delta_{X}$ -dense and $\delta_{Y}$ -dense, respectively. If $\delta_{X}+\delta_{Y}\geq 1.4$ and $\delta_{Y}\geq 0.99$ , the probability that $X$ takes a value that is $0.44$ -bad for $Y$ is at most $1/n$ .

Proof of Lemma 19.

Based on ${\mathcal{P}}$ , the desired decision tree is constructed as in Algorithm 1.

Algorithm 1 A decision tree yielding dense rectangles.

We first prove that any set of unqueried coordinates $J\subseteq[n]$ , query answer $z\in\{0,1\}^{\bar{J}}$ , transcript $m$ , and rectangle $R$ obtained by Algorithm 1 satisfy that $R\subseteq R_{m}$ is dense on $(J,z)$ . Then we bound the number of queries. To prove the density of $R$ , the following loop invariants are sufficient.

Proposition 23.

At the start and end of each iteration of the for-loop in Algorithm 1, it holds that $R$ is dense on $(J,z_{\bar{J}})$ . At the start and end of each iteration of the while-loop, it holds that either $X_{J}$ is $0.44$ -dense and $Y_{J}$ is $0.99$ -dense, or $X_{J}$ is $0.99$ -dense and $Y_{J}$ is $0.44$ -dense, where the random variables $X\sim U,Y\sim V$ .

Proof.

We prove this by induction. At the start of the first iteration ( $i=1$ ) of the for-loop, $R$ is dense on $(J,z_{\bar{J}})$ trivially since $R=\Lambda^{n}\times\Lambda^{n}$ and $J=[n]$ . We assume by the induction hypothesis that $R$ is dense on $(J,z_{\bar{J}})$ at the start of the $i$ -th iteration of the for-loop. We consider odd $i$ and the case where $i$ is even is symmetric.

Before executing Line 5, $G^{\bar{J}}(X,Y)\equiv z_{\bar{J}}$ and $X_{J},Y_{J}$ are $0.99$ -dense by the induction hypothesis, where $X\sim U,Y\sim V$ . After executing Line 11, $U$ is replaced by $U^{\prime}$ with $|U^{\prime}|\geq|U|/2$ . For each nonempty $I\subseteq J$ ,

H_{\infty}(X^{\prime}_{I})\geq H_{\infty}(X_{I})-1\geq 0.99b|I|-1\geq 0.98b|I|,

where $X^{\prime}\sim U^{\prime}$ . So $X^{\prime}_{J}$ is at least $0.98$ -dense.

We now temporarily turn to proving the loop invariant for the while-loop. Upon entering the while-loop for the first time, $X_{J}$ is $0.98$ -dense (and, of-course, $0.44$ -dense), and $Y_{J}$ is still $0.99$ -dense, where $X\sim U,Y\sim V$ . The loop invariant holds for the base case. We assume by the induction hypothesis that $X_{J}$ is $0.44$ -dense and $Y_{J}$ is $0.99$ -dense at the start of some iteration of the while-loop. The case where $X_{J}$ is $0.99$ -dense and $Y_{J}$ is $0.44$ -dense is symmetric.

Before executing Line 14, $X_{J}$ is $0.44$ -dense and $Y_{J}$ is $0.99$ -dense by the induction hypothesis, where $X\sim U,Y\sim V$ . After executing Line 14, $U$ is replaced by $U^{\prime}$ with the bad values removed. Then $X^{\prime}$ is not $0.44$ -bad for $Y$ where $X^{\prime}\sim U^{\prime}$ . Let $I\subseteq J$ be any maximal subset such that $H_{\infty}(X^{\prime}_{I})<0.99b|I|$ , $\alpha\in\Lambda^{I}$ be any value such that ${\mathcal{D}_{X^{\prime}_{I}}}(\alpha)>2^{-0.99b|I|}$ , and $z_{I}\in\{0,1\}^{I}$ be the answer of querying coordinates $I$ . Now $U$ is replaced by $U^{\prime\prime}$ such that $X^{\prime\prime}_{I}\equiv\alpha$ , where $X^{\prime\prime}\sim U^{\prime\prime}$ . So $X^{\prime\prime}=\left(X^{\prime}\mid X^{\prime}_{I}=\alpha\right)$ and by Proposition 20,

$X^{\prime\prime}_{J\setminus I}=\left(X^{\prime}_{J\setminus I}\mid X^{\prime}% _{I}=\alpha\right)\textrm{ is }0.99\textrm{-dense}.$

Then $V$ is replaced by $V^{\prime}$ such that $G^{I}(\alpha,Y^{\prime}_{I})\equiv z_{I}$ , where $Y^{\prime}\sim V^{\prime}$ . We have $Y^{\prime}=\left(Y\mid G^{I}(\alpha,Y_{I})=z_{I}\right)$ . As $X^{\prime}_{J}$ is not $0.44$ -bad for $Y_{J}$ and ${\mathcal{D}_{X^{\prime}_{I}}}(\alpha)>0$ , by Definition 21,

$Y^{\prime}_{J\setminus I}=\left(Y_{J\setminus I}\mid G^{I}(\alpha,Y_{I})=z_{I}% \right)\textrm{ is }0.44\textrm{-dense}.$

Besides, $G^{I}(X^{\prime\prime},Y^{\prime})\equiv G^{I}(\alpha,Y^{\prime}_{I})\equiv z_% {I}$ and $I$ is removed from $J$ . So the loop invariant holds at the end of the current iteration of the while-loop, and will still hold at the start of the next iteration of the while-loop.

At the end of the $i$ -th iteration of the for-loop, the loop condition of the while-loop is violated. So $X_{J},Y_{J}$ are both $0.99$ -dense, where $X\sim U,Y\sim V$ . And $G^{\bar{J}}(X,Y)\equiv z_{\bar{J}}$ since whenever some $I$ is removed from $J$ , we have $G^{I}(X,Y)\equiv z_{I}$ . Therefore, $R$ is dense on $(J,z_{\bar{J}})$ at the end of the $i$ -th iteration of the for-loop, also at the start of the $(i+1)$ -th iteration. $\hfill\blacktriangleleft$

Let the transcript $m\in\{0,1\}^{c}$ and the rectangle $R\subseteq\Lambda^{n}\times\Lambda^{n}$ be obtained by Algorithm 1. We prove that $R\subseteq R_{m}$ by induction on $i\in[c]$ .

For $i\in[c]$ , let $\Lambda^{n}\times\Lambda^{n}=\biguplus_{m^{\prime}\in\{0,1\}^{i}}R_{m^{\prime}}$ be the partition such that for each $m^{\prime}\in\{0,1\}^{i}$ , the transcript of the first $i$ bits is $m^{\prime}$ on any input $(x,y)\in R_{m^{\prime}}$ . Assume by the induction hypothesis that $R\subseteq R_{m_{1}\cdots m_{i-1}}$ at the start of the $i$ -th iteration of the for-loop. After executing Line 11, $R\subseteq R_{m_{1}\cdots m_{i}}$ . For the rest of the for-loop, the rectangle $R$ is just replaced by its sub-rectangle. So $R\subseteq R_{m_{1}\cdots m_{i}}$ at the end of the $i$ -th iteration of the for-loop, also at the start of the $(i+1)$ -th iteration. And finally, $R\subseteq R_{m}$ .

Query complexity.

To bound the number of queries, we are going to use the following potential function as in [11]:

\Delta(U,V,J)=2b|J|-H_{\infty}(X_{J})-H_{\infty}(Y_{J})

for $U,V\subseteq\Lambda^{n}$ and $J\subseteq[n]$ , where $X\sim U,Y\sim V$ . It holds that $\Delta(U,V,J)\geq 0$ . In Algorithm 1, the potential function $\Delta(U,V,J)$ initially equals $0$ . Intuitively, during the execution, the potential function increases by at most $O(1)$ for each bit transmitted, and decreases by at least $O(b|I|)$ for each subset $I$ removed from $J$ .

$\blacksquare$

Whenever executing Line 5 - Line 11, either $U$ is replaced by $U^{\prime}$ with $|U^{\prime}|\geq|U|/2$ , or $V$ is replaced by $V^{\prime}$ with $|V^{\prime}|\geq|V|/2$ . For the first case, the potential function increases by $H_{\infty}(X_{J})-H_{\infty}(X^{\prime}_{J})\leq 1$ , where $X^{\prime}\sim U^{\prime}$ . Similarly, for the second case, the potential function increases by $H_{\infty}(Y_{J})-H_{\infty}(Y^{\prime}_{J})\leq 1$ , where $Y^{\prime}\sim V^{\prime}$ .
$\blacksquare$

For each iteration of the while-loop triggered because $X_{J}$ is not $0.99$ -dense. Firstly, $U$ is replaced by $U^{\prime}$ with the bad values removed. Since $X_{J}$ is at least $0.44$ -dense and $Y_{J}$ is $0.99$ -dense. By Lemma 22, $X_{J}$ is $0.44$ -bad for $Y_{J}$ with probability at most $1-|U^{\prime}|/|U|\leq 1/n$ . So $|U^{\prime}|\geq|U|/2$ , and the potential function increases by at most $1$ .

Now $X^{\prime}_{J}$ is not $0.44$ -bad for $Y_{J}$ , where $X^{\prime}\sim U^{\prime}$ . Let $I\subseteq J$ be any maximal subset such that $H_{\infty}(X^{\prime}_{I})<0.99b|I|$ , and $\alpha\in\Lambda^{I}$ be any value such that ${\mathcal{D}_{X^{\prime}_{I}}}(\alpha)>2^{-0.99b|I|}$ . $U$ is replaced by $U^{\prime\prime}$ such that $X^{\prime\prime}_{I}\equiv\alpha$ , where $X^{\prime\prime}\sim U^{\prime\prime}$ . So $|U^{\prime\prime}|\geq|U^{\prime}|\cdot 2^{-0.99b|I|}$ , and the potential function increases by $H_{\infty}(X^{\prime}_{J})-H_{\infty}(X^{\prime\prime}_{J})\leq 0.99b|I|$ .

Then $V$ is replaced by $V^{\prime}$ such that $G^{I}(\alpha,Y^{\prime}_{I})\equiv z_{I}$ for some $z_{I}\subseteq\{0,1\}^{I}$ , where $Y^{\prime}\sim V^{\prime}$ . As $X^{\prime}_{J}$ is not $0.44$ -dense for $Y_{J}$ and ${\mathcal{D}_{X^{\prime}_{I}}}(\alpha)>0$ , by Definition 21, $|V^{\prime}|/|V|={\mathcal{D}_{G^{I}(\alpha,Y_{I})}}(z_{I})\geq 2^{-|I|-1}$ . The potential function increases by $H_{\infty}(Y_{J})-H_{\infty}(Y^{\prime}_{J})\leq|I|+1$ .

Finally, $I$ is removed from $J$ . The potential function increases by

$-2b|I|+H_{\infty}(X^{\prime\prime}_{J})-H_{\infty}(X^{\prime\prime}_{J% \setminus I})+H_{\infty}(Y^{\prime}_{J})-H_{\infty}(Y^{\prime}_{J\setminus I})% \leq-2b|I|+0+b|I|=-b|I|,$

where $H_{\infty}(X^{\prime\prime}_{J})=H_{\infty}(X^{\prime\prime}_{J\setminus I})$ because $X^{\prime\prime}_{I}\equiv\alpha$ .

Overall, the potential function increases by at most $1+0.99b|I|+|I|+1-b|I|\leq-0.005b|I|$ . For iterations triggered because $Y_{J}$ is not $0.99$ -dense, the argument is symmetric.

At the end, the potential function is at most $c-0.005b|\bar{J}|\geq 0$ . The number of queries $|\bar{J}|\leq\frac{200c}{b}$ . $\hfill\blacktriangleleft$

5 Lifting Theorem for Hybrid Classical-Quantum Communication

Let $n$ be sufficiently large. Recall that the gadget $G:\Lambda\times\Lambda\to\{0,1\}$ is the inner product function over the Boolean domain, where $\Lambda=\{0,1\}^{b}$ and $b=20\log n$ . The following is a lifting-style statement: given a hybrid protocol that transmits $c$ classical bits followed by $q$ quantum bits and solves $f\circ G^{n}$ , there is a $O\left(\frac{c}{b}\right)$ -depth decision tree such that the outer function $f$ restricted to any outcome of the query has approximate degree $O\left(\frac{q}{b}\right)$ .

Theorem 24.

Let ${\mathcal{P}}(c,q)$ be a hybrid protocol that allows $c$ bits of deterministic communication in advance, and uses $q$ qubits of quantum communication with prior entanglement (as defined in Section 2.3). For any $f:\{0,1\}^{n}\to\{\pm 1\}$ , if ${\mathcal{P}}$ computes $f\circ G^{n}$ with error $0.1$ , there exists a deterministic decision tree which queries at most $\frac{200c}{b}$ coordinates in $[n]$ such that: for any outcome of the query, ${\mathrm{deg}}_{1/3}(f_{J,z})=O\left(\frac{q}{b}\right)$ , where $J\subseteq[n]$ is the set of unqueried coordinates and $z\in\{0,1\}^{\bar{J}}$ is the query answer.

Proof.

Let $\Lambda^{n}\times\Lambda^{n}=\biguplus_{m\in\{0,1\}^{c}}R_{m}$ be a partition such that for each $m\in\{0,1\}^{c}$ , $R_{m}$ contains all inputs on which the transcript of ${\mathcal{P}}$ is $m$ . If ${\mathcal{P}}$ computes $f\circ G^{n}$ with error $0.1$ , $Q^{*}_{0.1}(F_{m})\leq q$ by Proposition 10, where $F_{m}$ is the function $f\circ G^{n}$ with its input restricted to $R_{m}$ .

By Lemma 19, there is a deterministic decision tree which queries at most $\frac{200c}{b}$ coordinates in $[n]$ such that for any set of unqueried coordinates $J\subseteq[n]$ and query answer $z\in\{0,1\}^{\bar{J}}$ , we can find a transcript $m\in\{0,1\}^{c}$ and a rectangle $R\subseteq R_{m}$ which is dense on $(J,z)$ . Therefore,

$\blacksquare$

$G^{\bar{J}}(x,y)=z$ for all $(x,y)\in R$ .
$\blacksquare$

$X_{J},Y_{J}$ are $0.99$ -dense. Define $F:U\times V\to\{\pm 1\}$ such that

$F(x,y)=f_{J,z}(G^{J}(x,y))=f\circ G^{n}(x,y),\qquad\forall\ (x,y)\in R.$

By Theorem 13, $Q^{*}_{0.1}(F)=\Omega\left({\mathrm{deg}}_{1/3}\left(f_{J,z}\right)\cdot b\right)$ .

Since $R\subseteq R_{m}$ , $Q^{*}_{0.1}(F)\leq Q^{*}_{0.1}(F_{m})\leq q$ . So ${\mathrm{deg}}_{1/3}\left(f_{J,z}\right)=O\left(\frac{q}{b}\right)$ . $\hfill\blacktriangleleft$

As a corollary of Theorem 24, we show the hardness of the classical-quantum trade-off.

Theorem 25.

Let ${\mathcal{P}}(c,q)$ be a hybrid protocol that allows $c$ bits of deterministic communication in advance, and uses $q$ qubits of quantum communication with prior entanglement. For any function $f:\{0,1\}^{n}\to\{\pm 1\}$ , if ${\mathcal{P}}$ computes $f\circ G^{n}$ with error $0.1$ , we have

$\blacksquare$

$q=\Omega\left(\sqrt{{\mathrm{deg}}(f)}\cdot b\right)$ if $c\leq\frac{{\mathrm{deg}}(f)\cdot b}{300}$ .
$\blacksquare$

$q=\Omega\left(\sqrt{{\mathrm{bs}}(f)}\cdot b\right)$ if $c\leq\frac{{\mathrm{bs}}(f)\cdot b}{300}$ .

Proof.

We construct an input $z\in\{0,1\}^{n}$ of the decision tree in Theorem 24 by taking a walk down the decision tree. The set of unqueried coordinates $J$ initially equals $[n]$ . For each queried coordinate $i\in[n]$ , there is a $z_{i}\in\{0,1\}$ such that ${\mathrm{deg}}\left(f_{J\setminus\{i\},z_{\bar{J}}z_{i}}\right)\geq{\mathrm{% deg}}\left(f_{J,z_{\bar{J}}}\right)-1$ as ${\mathrm{deg}}(\cdot)$ is entropic by Proposition 7. We make a query to $i$ and let the query answer be such a $z_{i}$ . Then $i$ is removed from $J$ . At the end, ${\mathrm{deg}}\left(f_{J,z_{\bar{J}}}\right)\geq{\mathrm{deg}}(f)-|\bar{J}|$ . By Theorem 24,

$\blacksquare$

$|\bar{J}|\leq\frac{200c}{b}$ .
$\blacksquare$

${\mathrm{deg}}_{1/3}(f_{J,z})=O\left(\frac{q}{b}\right)$ .

So $q=\Omega\left({\mathrm{deg}}_{1/3}\left(f_{J,z_{\bar{J}}}\right)\cdot b\right)% =\Omega\left(\sqrt{{\mathrm{deg}}\left(f_{J,z_{\bar{J}}}\right)}\cdot b\right)$ [1, Theorem 4]. If $c\leq\frac{{\mathrm{deg}}(f)\cdot b}{300}$ ,

{\mathrm{deg}}\left(f_{J,z_{\bar{J}}}\right)\geq{\mathrm{deg}}(f)-|\bar{J}|% \geq{\mathrm{deg}}(f)-\frac{200c}{b}\geq\frac{{\mathrm{deg}}(f)}{3},

and $q=\Omega\left(\sqrt{{\mathrm{deg}}(f)}\cdot b\right)$ .

The lower bound with respect to block sensitivity ${\mathrm{bs}}(\cdot)$ follows the same argument as ${\mathrm{bs}}(\cdot)$ is entropic by Proposition 8 and ${\mathrm{deg}}_{1/3}\left(f_{J,z}\right)=\Omega\left(\sqrt{{\mathrm{bs}}\left(% f_{J,z}\right)}\right)$ [46, Lemma 3.8]. $\hfill\blacktriangleleft$

As a corollary of Theorem 25, we get a nearly tight bound for read-once formula $f$ . A read-once formula, which consists of AND gates, OR gates, and NOT gates, is a formula in which each variable appears exactly once. We may let $f$ output $1$ if the corresponding formula outputs $0$ , and $-1$ if the formula outputs $1$ .

Corollary 26.

Let ${\mathcal{P}}(c,q)$ be a hybrid protocol that allows $c$ bits of deterministic communication in advance, and uses $q$ qubits of quantum communication with prior entanglement. Let $f$ be a read-once formula on $n$ bits. if ${\mathcal{P}}$ computes $f\circ G^{n}$ with error $0.1$ and $c\leq\frac{nb}{300}$ , then $q=\widetilde{\Theta}\left(\sqrt{n}\cdot b\right)$ .

Proof.

The degree of any read-once formula is $n$ [1, Lemma 27]. By Theorem 25, when $c\leq\frac{nb}{300}$ , we obtain $q=\Omega\left(\sqrt{n}\cdot b\right)$ .

On the other hand, the quantum query complexity of any read-once formula is $\Theta(\sqrt{n})$ [16]. By the BCW simulation [9], this yields a protocol with $q=O\left(\sqrt{n}\cdot b\log n\right)$ . $\hfill\blacktriangleleft$

References

[1] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of huang’s sensitivity theorem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1330–1342. ACM, 2021. doi:10.1145/3406325.3451047.
[2] Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban. The computational complexity of ball permutations. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 317–327. ACM, 2017. doi:10.1145/3055399.3055453.
[3] Scott Aaronson, Harry Buhrman, and William Kretschmer. A qubit, a coin, and an advice string walk into a relational problem. In Venkatesan Guruswami, editor, Proceedings of the 15th Innovations in Theoretical Computer Science Conference, volume 287 of LIPIcs, pages 1:1–1:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.1.
[4] Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee. Separating quantum communication and approximate rank. In Ryan O’Donnell, editor, Proceedings of the 32nd Computational Complexity Conference, volume 79 of LIPIcs, pages 24:1–24:33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.24.
[5] Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. CoRR, abs/2201.01904, 2022. arXiv:2201.01904.
[6] Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. One clean qubit suffices for quantum communication advantage. CoRR, abs/2310.02406, 2023. doi:10.48550/arXiv.2310.02406.
[7] Ziv Bar-Yossef, Thathachar S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM Journal on Computing, 38(1):366–384, 2008. doi:10.1137/060651835.
[8] Ziv Bar-Yossef, Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702–732, 2004. doi:10.1016/J.JCSS.2003.11.006.
[9] Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computing, pages 63–68. ACM, 1998. doi:10.1145/276698.276713.
[10] Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, and Manaswi Paraashar. Quantum query-to-communication simulation needs a logarithmic overhead. In Proceedings of the 35th Computational Complexity Conference, volume 169 of LIPIcs, pages 32:1–32:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CCC.2020.32.
[11] Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting for BPP using inner product. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 35:1–35:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.35.
[12] Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM Journal on Computing, 50(1):171–210, 2021. doi:10.1137/19M1310153.
[13] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. The complexity of nisq. Nature Communications, 14(1):6001, 2023.
[14] Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. Journal of the ACM, 70(1):6:1–6:38, 2023. doi:10.1145/3570637.
[15] Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. CoRR, abs/2205.04656, 2022. doi:10.48550/arXiv.2205.04656.
[16] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In Algorithms – ESA 2012, Proceedings of the 20th Annual European Symposium, volume 7501, pages 337–348. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33090-2_30.
[17] Richard Cleve and Harry Buhrman. Substituting quantum entanglement for communication. Physical Review A, 56:1201–1204, August 1997. doi:10.1103/PhysRevA.56.1201.
[18] Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 889–901. ACM, 2020. doi:10.1145/3357713.3384269.
[19] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. CoRR, abs/1411.4028, 2014. arXiv:1411.4028.
[20] Dmitry Gavinsky. Quantum versus classical simultaneity in communication complexity. IEEE Transactions on Information Theory, 65(10):6466–6483, 2019. doi:10.1109/TIT.2019.2918453.
[21] Dmitry Gavinsky. Entangled simultaneity versus classical interactivity in communication complexity. IEEE Transactions on Information Theory, 66(7):4641–4651, 2020. doi:10.1109/TIT.2020.2976074.
[22] Dmitry Gavinsky. Bare quantum simultaneity versus classical interactivity in communication complexity. IEEE Transactions on Information Theory, 67(10):6583–6605, 2021. doi:10.1109/TIT.2021.3050528.
[23] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 516–525. ACM, 2007. doi:10.1145/1250790.1250866.
[24] Dmitry Gavinsky, Oded Regev, and Ronald de Wolf. Simultaneous communication protocols with quantum and classical messages. Chicago Journal of Theoretical Computer Science, 2008, 2008. URL: http://cjtcs.cs.uchicago.edu/articles/2008/7/contents.html.
[25] Uma Girish. Fourier spectrum of noisy quantum algorithms. CoRR, abs/2510.06385, 2025. doi:10.48550/arXiv.2510.06385.
[26] Uma Girish, Ran Raz, and Avishay Tal. Quantum versus randomized communication complexity, with efficient players. Computational Complexity, 31(2):17, 2022. doi:10.1007/S00037-022-00232-7.
[27] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1465–1475. ACM, 2025. doi:10.1145/3717823.3718155.
[28] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835–1869, 2016. doi:10.1137/15M103145X.
[29] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for bpp. SIAM Journal on Computing, 49(4), 2020. doi:10.1137/17M115339X.
[30] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. The nisq complexity of collision finding. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–32. Springer, 2024. doi:10.1007/978-3-031-58737-5_1.
[31] Atsuya Hasegawa and François Le Gall. An optimal oracle separation of classical and quantum hybrid schemes. In Proceedings of the 33rd International Symposium on Algorithms and Computation, volume 248 of LIPIcs, pages 6:1–6:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ISAAC.2022.6.
[32] Dale Jacobs and Saeed Mehraban. The space just above one clean qubit. CoRR, abs/2410.08051, 2024. doi:10.48550/arXiv.2410.08051.
[33] Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992. doi:10.1137/0405044.
[34] Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20–46, 2007. doi:10.1137/S0097539702405620.
[35] Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81:5672–5675, December 1998. doi:10.1103/PhysRevLett.81.5672.
[36] William Kretschmer, Sabee Grewal, Matthew DeCross, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nicholas Hunter-Jones, Karl Mayer, Brian Neyenhuis, David Hayes, and Scott Aaronson. Demonstrating an unconditional separation between quantum and classical information resources, 2025. arXiv:2509.07255.
[37] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.
[38] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263–398, 2009. doi:10.1561/0400000040.
[39] Troy Lee and Shengyu Zhang. Composition theorems in communication complexity. In Proceedings of the 37th International Colloquium on Automata, Languages, and Programming, volume 6198, pages 475–489. Springer, 2010. doi:10.1007/978-3-642-14165-2_41.
[40] Xiaodie Lin, Zhaohui Wei, and Penghui Yao. Quantum and classical hybrid generations for classical correlations. IEEE Transactions on Information Theory, 68(1):302–310, 2022. doi:10.1109/TIT.2021.3123401.
[41] Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 699–708. ACM, 2007. doi:10.1145/1250790.1250892.
[42] Qipeng Liu, Ran Raz, and Wei Zhan. Memory-sample lower bounds for learning with classical-quantum hybrid memory. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1097–1110. ACM, 2023. doi:10.1145/3564246.3585129.
[43] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, volume 215 of LIPIcs, pages 104:1–104:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.104.
[44] Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Gadgetless lifting beats round elimination: Improved lower bounds for pointer chasing. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference, volume 325 of LIPIcs, pages 75:1–75:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ITCS.2025.75.
[45] Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical Review Letters, 112:130502, April 2014. doi:10.1103/PhysRevLett.112.130502.
[46] Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994. doi:10.1007/BF01263419.
[47] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014.
[48] John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018. doi:10.22331/Q-2018-08-06-79.
[49] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 358–367. ACM, 1999. doi:10.1145/301250.301343.
[50] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 234–243. IEEE Computer Society, 1997. doi:10.1109/SFCS.1997.646112.
[51] Alexander A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385–390, 1992. doi:10.1016/0304-3975(92)90260-M.
[52] Alexander A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003.
[53] Oded Regev and Bo’az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the 43rd ACM Symposium on Theory of Computing, pages 31–40. ACM, 2011. doi:10.1145/1993636.1993642.
[54] Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 773–781. Springer, 2008. doi:10.1007/978-3-540-70575-8_63.
[55] Ansis Rosmanis. Hybrid quantum-classical search algorithms. ACM Transactions on Quantum Computing, 5(2), April 2024. doi:10.1145/3648573.
[56] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969–2000, 2011. doi:10.1137/080733644.
[57] Alexander A. Sherstov. Communication lower bounds using directional derivatives. Journal of the ACM, 61(6):34:1–34:71, 2014. doi:10.1145/2629334.
[58] Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information and Computation, 9(5&6):444–460, 2009. doi:10.26421/QIC9.5-6-7.
[59] Xiaoming Sun and Yufan Zheng. Hybrid decision trees: Longer quantum time is strictly more powerful. CoRR, abs/1911.13091, 2019. arXiv:1911.13091.
[60] Xudong Wu, Guangxu Yang, and Penghui Yao. A lifting theorem for hybrid classical-quantum communication complexity. CoRR, abs/2511.17227, 2026. doi:10.48550/arXiv.2511.17227.
[61] Guangxu Yang and Jiapeng Zhang. Quantum versus classical separation in simultaneous number-on-forehead communication. CoRR, abs/2506.16804, 2025. doi:10.48550/arXiv.2506.16804.
[62] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, pages 209–213. ACM, 1979. doi:10.1145/800135.804414.
[63] Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 352–361. IEEE Computer Society, 1993. doi:10.1109/SFCS.1993.366852.
[64] Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Annual International Cryptology Conference, pages 239–268. Springer, 2019. doi:10.1007/978-3-030-26951-7_9.

[bib.bib1] [1] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of huang’s sensitivity theorem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1330–1342. ACM, 2021. doi:10.1145/3406325.3451047.

[bib.bib2] [2] Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban. The computational complexity of ball permutations. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 317–327. ACM, 2017. doi:10.1145/3055399.3055453.

[bib.bib3] [3] Scott Aaronson, Harry Buhrman, and William Kretschmer. A qubit, a coin, and an advice string walk into a relational problem. In Venkatesan Guruswami, editor, Proceedings of the 15th Innovations in Theoretical Computer Science Conference, volume 287 of LIPIcs, pages 1:1–1:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.1.

[bib.bib4] [4] Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee. Separating quantum communication and approximate rank. In Ryan O’Donnell, editor, Proceedings of the 32nd Computational Complexity Conference, volume 79 of LIPIcs, pages 24:1–24:33. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.24.

[bib.bib5] [5] Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. CoRR, abs/2201.01904, 2022. arXiv:2201.01904.

[bib.bib6] [6] Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. One clean qubit suffices for quantum communication advantage. CoRR, abs/2310.02406, 2023. doi:10.48550/arXiv.2310.02406.

[bib.bib7] [7] Ziv Bar-Yossef, Thathachar S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM Journal on Computing, 38(1):366–384, 2008. doi:10.1137/060651835.

[bib.bib8] [8] Ziv Bar-Yossef, Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702–732, 2004. doi:10.1016/J.JCSS.2003.11.006.

[bib.bib9] [9] Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computing, pages 63–68. ACM, 1998. doi:10.1145/276698.276713.

[bib.bib10] [10] Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, and Manaswi Paraashar. Quantum query-to-communication simulation needs a logarithmic overhead. In Proceedings of the 35th Computational Complexity Conference, volume 169 of LIPIcs, pages 32:1–32:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CCC.2020.32.

[bib.bib11] [11] Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting for BPP using inner product. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 35:1–35:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.35.

[bib.bib12] [12] Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM Journal on Computing, 50(1):171–210, 2021. doi:10.1137/19M1310153.

[bib.bib13] [13] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. The complexity of nisq. Nature Communications, 14(1):6001, 2023.

[bib.bib14] [14] Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. Journal of the ACM, 70(1):6:1–6:38, 2023. doi:10.1145/3570637.

[bib.bib15] [15] Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. CoRR, abs/2205.04656, 2022. doi:10.48550/arXiv.2205.04656.

[bib.bib16] [16] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In Algorithms – ESA 2012, Proceedings of the 20th Annual European Symposium, volume 7501, pages 337–348. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33090-2_30.

[bib.bib17] [17] Richard Cleve and Harry Buhrman. Substituting quantum entanglement for communication. Physical Review A, 56:1201–1204, August 1997. doi:10.1103/PhysRevA.56.1201.

[bib.bib18] [18] Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 889–901. ACM, 2020. doi:10.1145/3357713.3384269.

[bib.bib19] [19] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. CoRR, abs/1411.4028, 2014. arXiv:1411.4028.

[bib.bib20] [20] Dmitry Gavinsky. Quantum versus classical simultaneity in communication complexity. IEEE Transactions on Information Theory, 65(10):6466–6483, 2019. doi:10.1109/TIT.2019.2918453.

[bib.bib21] [21] Dmitry Gavinsky. Entangled simultaneity versus classical interactivity in communication complexity. IEEE Transactions on Information Theory, 66(7):4641–4651, 2020. doi:10.1109/TIT.2020.2976074.

[bib.bib22] [22] Dmitry Gavinsky. Bare quantum simultaneity versus classical interactivity in communication complexity. IEEE Transactions on Information Theory, 67(10):6583–6605, 2021. doi:10.1109/TIT.2021.3050528.

[bib.bib23] [23] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 516–525. ACM, 2007. doi:10.1145/1250790.1250866.

[bib.bib24] [24] Dmitry Gavinsky, Oded Regev, and Ronald de Wolf. Simultaneous communication protocols with quantum and classical messages. Chicago Journal of Theoretical Computer Science, 2008, 2008. URL: http://cjtcs.cs.uchicago.edu/articles/2008/7/contents.html.

[bib.bib25] [25] Uma Girish. Fourier spectrum of noisy quantum algorithms. CoRR, abs/2510.06385, 2025. doi:10.48550/arXiv.2510.06385.

[bib.bib26] [26] Uma Girish, Ran Raz, and Avishay Tal. Quantum versus randomized communication complexity, with efficient players. Computational Complexity, 31(2):17, 2022. doi:10.1007/S00037-022-00232-7.

[bib.bib27] [27] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1465–1475. ACM, 2025. doi:10.1145/3717823.3718155.

[bib.bib28] [28] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835–1869, 2016. doi:10.1137/15M103145X.

[bib.bib29] [29] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for bpp. SIAM Journal on Computing, 49(4), 2020. doi:10.1137/17M115339X.

[bib.bib30] [30] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. The nisq complexity of collision finding. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–32. Springer, 2024. doi:10.1007/978-3-031-58737-5_1.

[bib.bib31] [31] Atsuya Hasegawa and François Le Gall. An optimal oracle separation of classical and quantum hybrid schemes. In Proceedings of the 33rd International Symposium on Algorithms and Computation, volume 248 of LIPIcs, pages 6:1–6:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ISAAC.2022.6.

[bib.bib32] [32] Dale Jacobs and Saeed Mehraban. The space just above one clean qubit. CoRR, abs/2410.08051, 2024. doi:10.48550/arXiv.2410.08051.

[bib.bib33] [33] Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545–557, 1992. doi:10.1137/0405044.

[bib.bib34] [34] Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20–46, 2007. doi:10.1137/S0097539702405620.

[bib.bib35] [35] Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81:5672–5675, December 1998. doi:10.1103/PhysRevLett.81.5672.

[bib.bib36] [36] William Kretschmer, Sabee Grewal, Matthew DeCross, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nicholas Hunter-Jones, Karl Mayer, Brian Neyenhuis, David Hayes, and Scott Aaronson. Demonstrating an unconditional separation between quantum and classical information resources, 2025. arXiv:2509.07255.

[bib.bib37] [37] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.

[bib.bib38] [38] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263–398, 2009. doi:10.1561/0400000040.

[bib.bib39] [39] Troy Lee and Shengyu Zhang. Composition theorems in communication complexity. In Proceedings of the 37th International Colloquium on Automata, Languages, and Programming, volume 6198, pages 475–489. Springer, 2010. doi:10.1007/978-3-642-14165-2_41.

[bib.bib40] [40] Xiaodie Lin, Zhaohui Wei, and Penghui Yao. Quantum and classical hybrid generations for classical correlations. IEEE Transactions on Information Theory, 68(1):302–310, 2022. doi:10.1109/TIT.2021.3123401.

[bib.bib41] [41] Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 699–708. ACM, 2007. doi:10.1145/1250790.1250892.

[bib.bib42] [42] Qipeng Liu, Ran Raz, and Wei Zhan. Memory-sample lower bounds for learning with classical-quantum hybrid memory. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1097–1110. ACM, 2023. doi:10.1145/3564246.3585129.

[bib.bib43] [43] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, volume 215 of LIPIcs, pages 104:1–104:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.104.

[bib.bib44] [44] Xinyu Mao, Guangxu Yang, and Jiapeng Zhang. Gadgetless lifting beats round elimination: Improved lower bounds for pointer chasing. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference, volume 325 of LIPIcs, pages 75:1–75:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ITCS.2025.75.

[bib.bib45] [45] Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical Review Letters, 112:130502, April 2014. doi:10.1103/PhysRevLett.112.130502.

[bib.bib46] [46] Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994. doi:10.1007/BF01263419.

[bib.bib47] [47] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014.

[bib.bib48] [48] John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018. doi:10.22331/Q-2018-08-06-79.

[bib.bib49] [49] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 358–367. ACM, 1999. doi:10.1145/301250.301343.

[bib.bib50] [50] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 234–243. IEEE Computer Society, 1997. doi:10.1109/SFCS.1997.646112.

[bib.bib51] [51] Alexander A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385–390, 1992. doi:10.1016/0304-3975(92)90260-M.

[bib.bib52] [52] Alexander A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003.

[bib.bib53] [53] Oded Regev and Bo’az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the 43rd ACM Symposium on Theory of Computing, pages 31–40. ACM, 2011. doi:10.1145/1993636.1993642.

[bib.bib54] [54] Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 773–781. Springer, 2008. doi:10.1007/978-3-540-70575-8_63.

[bib.bib55] [55] Ansis Rosmanis. Hybrid quantum-classical search algorithms. ACM Transactions on Quantum Computing, 5(2), April 2024. doi:10.1145/3648573.

[bib.bib56] [56] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40(6):1969–2000, 2011. doi:10.1137/080733644.

[bib.bib57] [57] Alexander A. Sherstov. Communication lower bounds using directional derivatives. Journal of the ACM, 61(6):34:1–34:71, 2014. doi:10.1145/2629334.

[bib.bib58] [58] Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information and Computation, 9(5&6):444–460, 2009. doi:10.26421/QIC9.5-6-7.

[bib.bib59] [59] Xiaoming Sun and Yufan Zheng. Hybrid decision trees: Longer quantum time is strictly more powerful. CoRR, abs/1911.13091, 2019. arXiv:1911.13091.

[bib.bib60] [60] Xudong Wu, Guangxu Yang, and Penghui Yao. A lifting theorem for hybrid classical-quantum communication complexity. CoRR, abs/2511.17227, 2026. doi:10.48550/arXiv.2511.17227.

[bib.bib61] [61] Guangxu Yang and Jiapeng Zhang. Quantum versus classical separation in simultaneous number-on-forehead communication. CoRR, abs/2506.16804, 2025. doi:10.48550/arXiv.2506.16804.

[bib.bib62] [62] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, pages 209–213. ACM, 1979. doi:10.1145/800135.804414.

[bib.bib63] [63] Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 352–361. IEEE Computer Society, 1993. doi:10.1109/SFCS.1993.366852.

[bib.bib64] [64] Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Annual International Cryptology Conference, pages 239–268. Springer, 2019. doi:10.1007/978-3-030-26951-7_9.

	$\displaystyle{\left\lVert{\Psi}\right\rVert}\sqrt{\|R\|}$	$\displaystyle\leq\left({\mathrm{tr}}\left(\Psi\Psi^{\mathrm{T}}\right)^{2}% \right)^{1/4}\sqrt{\|R\|}$
		$\displaystyle\leq\left(\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2},T_{2}% \subseteq J\\ \|S_{1}\|,\|T_{1}\|,\|S_{2}\|,\|T_{2}\|\geq d\end{subarray}}\frac{1}{\|R\|^{2}}{\left\|{{% \mathrm{tr}}\left(M_{S_{1}}M_{T_{1}}^{\mathrm{T}}M_{S_{2}}M_{T_{2}}^{\mathrm{T% }}\right)}\right\|}\right)^{1/4}$
		$\displaystyle\leq\left(\sum_{\begin{subarray}{c}S_{1},T_{1},S_{2},T_{2}% \subseteq J\\ \|S_{1}\|,\|T_{1}\|,\|S_{2}\|,\|T_{2}\|\geq d\end{subarray}}2^{-0.11b(\|S_{1}\|+\|T_{1}\|+% \|S_{2}\|+\|T_{2}\|)}\right)^{1/4}$
		$\displaystyle=\sum_{S\subseteq J:\|S\|\geq d}2^{-0.11b\|S\|}\leq n^{-1.1d},\$