A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity

The good thing about existentially-quantified (${\mathrm{\Sigma }}_1$) statements is that proving them amounts to finding a witness, after which the proof is a routine verification. But – if we assume that $\mathrm{𝖭𝖯}\ne \mathrm{𝖼𝗈𝖭𝖯}$ – there will necessarily exist universally-quantified (${\mathrm{\Pi }}_1$) statements which cannot be proven in this way. Simultaneously, there exists a small number of situations when a particular class of ${\mathrm{\Sigma }}_1$ statements is known to be closed under negation, meaning, every statement in this class can be either proven or disproven by finding an explicit, easy-to-verify witness. Of course, this includes all “easy” statements (decidable in $𝖯$), but beyond that the exhaustive list is quite short. To our knowledge, the following list includes all problems that are known to be in $\mathrm{𝖭𝖯}\cap \mathrm{𝖼𝗈𝖭𝖯}$, ¹¹1More precisely, conic feasibility is known to be in $\mathrm{𝖭𝖯}(ℝ)\cap \mathrm{𝖼𝗈𝖭𝖯}(ℝ)$, as there are issues with the bitlength of solutions, which appear unavoidable. For example, one can construct a semidefinite feasibility problem $(𝒜,b)$, with polynomially-many bits of of precision, which is satisfiable, but any solution $x$ must be specified with exponentially-many bits of precision. This is a classical example by Khachiyan, see [23]. but not known to be in $𝖯$: arithmetical statements around factoring and discrete log, conic feasibility [24], which includes semidefinite feasibility, (approximate) lattice problems [1], stochastic games (see, e.g. [28]), the unknotting problem [17], and the arrival problem [10]. In this paper, we focus on semidefinite feasibility problems (SDFPs), which are a particular kind of conic feasibility.

Our original interest in looking at SDFPs was: to study semidefinite relaxations of communication complexity. Why should one care to do this? Well, the existence of a protocol for solving a given function is our ${\mathrm{\Sigma }}_1$ statement, and by duality of SDFPs, every lower-bound for any such model is explicitly witnessed by a small object, which is desirable if one wishes to prove lower-bounds. A previous result by Karchmer, Kushilevitz and Nisan [15] attempted to do this with linear programming – and showed that the natural way of doing it gives models that are too powerful, they can solve all Karchmer–Wigderson games in $O(\log n)$ communication. To attempt to do this using semidefinite programming is a natural, obvious thing to try.²²2It may seem like the linear relaxations of communication protocols being too powerful would imply that the semidefinite relaxations are too. However, the semidefinite constraints used to define what a valid relaxation is are also stronger than the linear constraints, and hence the linear relaxations can’t be turned into valid semidefinite relaxations. We show, however, that the conclusion is essentially the same.
This paper consists of the following.

• $\mathrm{■}$

  We begin by studying a natural semidefinite relaxation of the pigeonhole principle, which we call the “Quantum Pigeonhole Principle” (QPHP), a statement which is strictly stronger than the classical PHP, and which we consider to be a interesting linear algebraic theorem in its own right. We show several proofs of the QPHP, from a loose, easy-to-prove bound, to the best possible quantitative statement.

• $\mathrm{■}$

  We then study two different computational models, both obtained as semidefinite relaxations of communication complexity:

  • –

    One such model is a structured generalization of the ${\gamma }_2$ norm. It relates with ${\gamma }_2$ norm in an analogous way to how communication protocols are related with rectangles. We prove a simple lower-bound for such a model, based on the ${\gamma }_2$ norm, and we prove that, in this model, equality can be solved in $O(\log n)$ bits of communication.

  • –

    We call the other model “Quantum lab protocols”. We prove that such protocols can compute every function in 3 rounds with 4 bits of communication. As an application of the QPHP we show that, in 2 rounds, such protocols cannot compute equality with less than $n+1$ bits of communication.
• $\mathrm{■}$

  Finally, we show that these results are not an artifact of the particular semidefinite program which we used to model communication complexity, that any program which attempts to do this, and obeys some mild assumptions, must necessarily fail. We call this a “no-go theorem”. This theorem also applies to linear-programming relaxations, since they are special case of SDPs, and even in this restricted setting our no-go theorem is very different to the “complexity is not convex” results of [15] and the follow-up paper [12] (see [14], Section 6.9).

We will now overview our reasoning in greater detail. Supplementary definitions on various topics touched on in the introduction can be found in Section 6.

In proof complexity, more specifically in a proof system called Polynomial Calculus, the negation of the pigeonhole principle is sometimes formalized as the following quadratic feasibility problem:

This system is not homogeneous, so it is not immediate how to express it as a SDFP. Nonetheless, we can attempt to naively relax this program to higher dimensions, by replacing real numbers with vectors, and products with inner products. This gives us exactly the negation of the QPHP (Theorem 1):

To see the equivalence, notice that for each fixed $i\in [p]$, (2) states that the $v_{i,j}$ are orthogonal. Under such orthogonality, it is obvious that 1 implies 1a and 1b, by Pythagoras’ Theorem. Conversely, let ${\lambda }_i^{\prime }={\sum }_j{v}_{i,j}$. Then 1b states that $⟨{\lambda }_j^{\prime },\lambda ⟩={\Vert \lambda \Vert }^2$ and, under orthogonality, Pythagoras’ Theorem says ${\Vert {\lambda }_i^{\prime }\Vert }^2={\sum }_j{\Vert v_{i,j}\Vert }^2$, and so (3) is saying that ${\Vert {\lambda }_j^{\prime }\Vert }^2={\Vert \lambda \Vert }^2$. These two together imply, by the equality case of Cauchy-Schwarz, that ${\lambda }_j^{\prime }=\lambda$.

It is now clear that we have a semidefinite feasibility problem. It can also be seen that taking constraints (1)-(4), and further restricting $\lambda$, $v_{i,j}$ to have dimension $1$, gives us a HQFP, which is equivalent to the negation of the PHP.

It is also possible to state the QPHP using only quantum language, as follows. Suppose that we have $p$ quantum registers $1,\mathrm{\dots },p$, which are all initialized in the same state: $|{\psi }_1⟩=\mathrm{\cdots }=|{\psi }_p⟩$. We then apply an $h$-outcome measurement to each of the registers. The specific measurement which we make may be different for different registers. Regardless, the measurements cause the registers to collapse to possibly-different states $|{\varphi }_1⟩,\mathrm{\dots },|{\varphi }_p⟩$. The QPHP states that, if , there will always exist an outcome $j$ and two registers $i\ne i^{\prime }$, such that there is a non-zero probability of obtaining the same outcome $j$ after measuring both registers $i$ and $i^{\prime }$, and when this happens the resulting states $|{\varphi }_i⟩$ and $|{\varphi }_{i^{\prime }}⟩$ are not orthogonal.

We show that the Quantum Pigeonhole Principle is true.

In the full version of our paper [11] we show proofs of three versions of the QPHP:

• $\mathrm{■}$

  Using the AM-GM inequality we give a short and simple proof of a weaker version of the QPHP, only showing non-orthogonality if the number of holes $h$ is significantly smaller than the number $p$ of pigeons, namely .

• $\mathrm{■}$

  We also prove a quantitatively stronger version of the QPHP, which allows for the initial states ${\lambda }_i$ to be different for different pigeons, and gives a tight lower-bound on the maximal overlap $⟨v_{i,j},v_{i^{\prime },j}⟩$, as a function of the average initial overlap $\beta :=\frac{1}{p(p-1)}{\sum }_{i\ne i^{\prime }}⟨{\lambda }_i\mid {\lambda }_{i^{\prime }}⟩$. Namely we get that there exists $j\in [h]$ and $i\ne i^{\prime }\in [p]$ such that

  $$⟨v_{i,j},v_{i^{\prime },j}⟩\ge \frac{1}{h^2}\left(\beta -\frac{h-1}{p-1}\right)$$

• $\mathrm{■}$

  Finally we also prove the QPHP via one of the short “canonical” proofs which are guaranteed to exist via duality. Namely, we derive a feasibility problem dual to the relaxed negation of the QPHP, and give an explicit solution for it.

Sections 4 and 5 of the paper apply the above approach to statements of the form “the communication complexity of $f$ is $>k$”. This is a ${\mathrm{\Pi }}_1$ statement when the two-player function (or relation) $f$ is given as a communication matrix. Indeed, the statement “the communication complexity of $f$ is $\le k$” is easily seen to be ${\mathrm{\Sigma }}_1$, by taking an existential quantifier over all protocols of cost at most $k$.

When starting this project over two years ago, our naive hope was that maybe we could use semidefinite programming to prove some new lower-bounds against Karchmer–Wigderson games. This would follow a long, successful tradition of using convex optimization to prove lower-bounds: approximate and threshold degree [8], the quantum adversary bound [19], and the ${\gamma }_2$ norm [20] are all examples of complexity measures which relax classical measures in one way or another, and which have been used to prove lower-bounds on classical and quantum query complexity, communication complexity, proof complexity, data structures, etc.

But also, such attempts have systematically failed against more powerful computational models, such as Boolean circuits and formulas. A famous result by Karchmer, Kushilevitz and Nisan [15] (CCC’92) shows that the smooth partition bound is small for every Karchmer–Wigderson relation.⁴⁴4This result was generalized by Hrubeš et al. [12], to show that any “convex rectangle measure” assigns small complexity to KW relations. A smooth partition is a linear-programming relaxation of an integer program defining the partition number, which is the smallest number of monochromatic rectangles needed to partition a communication matrix, itself a relaxation of the number of leaves in a communication protocol. KKN were hoping [15, page 2] that such a linear relaxation would help them prove lower bounds on the communication complexity of Karchmer–Wigderson relations, and hence lower bounds on the depth of Boolean formulas. Sadly, they could only report on a failed attempt. A few years later, Razborov and Rudich presented their natural-proofs barrier [25] (STOC’95), which strongly suggests that no linear programming relaxation, or any other efficiently computable quantity, will be able to approximate the computational complexity of any model which is powerful enough to contain pseudorandom function generators.

One might think that the natural proofs barrier applies here, but one would be subtly mistaken. Indeed, semidefinite feasibility is not known to be in $𝖯$, and there is significant evidence that it is actually a hard problem [30].⁵⁵5We are referring to a result by Tarasov and Vyalyi, showing that any algorithm for solving semidefinite feasibility could be used to compare numbers represented by arithmetic circuits. Note that here we do not have a bound on the degree of the circuits, which could then be exponential in the size of the circuit, and efficiently comparing the (possibly doubly-exponentially large) numbers output by such arithmetic circuits is an old, longstanding problem, which includes the infamous sum-of-square-roots problem as a special case, and which may well not be polynomial-time solvable. However, semidefinite feasibility is in $\mathrm{𝖭𝖯}(ℝ)\cap \mathrm{𝖼𝗈𝖭𝖯}(ℝ)$, and one can formulate a sufficiently strong cryptographic conjecture, which would imply the existence of a natural proofs barrier that would apply here.⁶⁶6In a follow-up to his and Razborov’s natural-proofs result [26], Rudich extended the natural proofs barrier as follows. Clearly no pseudorandom generator can fool $\mathrm{𝖭𝖯}$, since in order to distinguish a random from a pseudorandom string, one can always guess the preimage. In his work, Rudich considers the possibility that there exist pseudorandom generators that fool $\mathrm{𝖼𝗈𝖭𝖯}$. In other words, he conjectures that there exist pseudorandom generators such that no family of short, efficiently recognizable (${\{0,1\}}^{\ast }$-valued) objects serve to witness that a given string is not pseudorandom (not even for a non-negligible fraction of all strings). One could extend Rudich’s conjecture from $\mathrm{𝖼𝗈𝖭𝖯}$ distinguishers to $\mathrm{𝖼𝗈𝖭𝖯}(ℝ)$ distinguishers: that no family of low-dimensional, efficiently recognizable real-valued objects could serve to witness that a given string is not pseudorandom. Under this generalization of Rudich’s conjecture, it necessarily follows that all attempts at approximating complexity using semidefinite feasibility are doomed to fail, since the real-valued dual witnesses could ultimately be used to witness that a given string is not pseudorandom. One could argue whether such a strong cryptographic assumption is believable, but such a discussion will soon become irrelevant to our purpose.

Because shortly after we started working on this, Austrin and Risse [5] showed that the sum of squares proof system (SOS) needs degree roughly $S$ to prove, for any given function $f$, that $f$ needs circuits of size $S$. Carefully checking their proof, and doing the necessary adaptations, it also follows from their results that SOS needs degree roughly $2^d$ to prove a depth-$d$ lower-bound on Boolean formulas. And it is possible to formalize the Karchmer–Wigderson theorem in the SOS proof system, and hence it will follow that SOS needs degree roughly $2^d$ to prove a lower-bound of $d$ on the communication complexity of a Karchmer–Wigderson relation. However, a satisfying instance of a semidefinite feasibility problem can be verified in the SOS proof system using a degree-2 proof! It must then follow that, if we define a communication model using our approach, i.e., we generalize communication complexity by formalizing the existence of a deterministic protocol using a HQFP, and relaxing it to a SDFP, then either (1) the proof that our communication model is stronger than the usual deterministic protocols cannot be show by low-degree SOS proofs (“our formalization of communication complexity is weird”), or (2) our generalized communication model can actually solve every single Karchmer–Wigderson game. This follows because our generalized model is such that we always have short, low-degree proofs of any true lower-bound.

The above considerations lead to a no-go theorem, which (informally stated) says that, unless a weird “high-degree” ingredient is introduced somewhere in the formalization (of communication complexity as a HQFP), the model obtained by semidefinite relaxation will be too strong, and will solve all Karchmer–Wigderson relations. We found it remarkable that statements in proof complexity about lengths of proofs imply the existence of algorithms for Karchmer–Wigderson relations, in a large class of computational models!

This no-go theorem should be seen as a natural, expected consequence of the results of Austrin and Risse. But, perhaps owing to our inexperience with proof complexity, it was not easy for us to verify that the formal connection is really there, and so in the full version of our paper [11] we provide a formalization and proof of this no-go theorem.

In light of such a result, one should ask: is it still worthwhile to pursue the stated aim, of formalizing communication complexity using a HQFP, relaxing to a SDFP, and studying the resulting communication model? As it turned out, we went through this formalize-and-relax process twice, and in both times there was something interesting to be found on the other side. In one case we ended up with a communication model which is a kind of structured version of the well-known and well-studied ${\gamma }_2$ norm. In the other case, we ended up with a communication model that has a natural, physical description, and understanding this model revealed to us something non-obvious about the nature of quantum measurements.

And although it is now expected that both models can solve all Karchmer–Wigderson relations, the above no-go theorem is not constructive, and gives us no explicit description of the algorithms in the model that actually do this. So it is still worthwhile to give a constructive proof of this, i.e., to find algorithms in the model for solving Karchmer–Wigderson relations.

Our first attempt to express a communication protocol as an HQFP proceeds as follows. We view a two-party communication protocol computing a function $f:𝒳\times 𝒴\to \{0,1\}$ as defined by two parts: the structure $𝒯$ of the protocol tree (i.e. the nodes in the protocol tree and which player speaks at which node) and the specification of the state of the protocol at each node in the protocol tree. The second part can be specified by a combinatorial rectangle of $𝒳\times 𝒴$ at every node.

Now, for a given tree structure $𝒯$ we will design an HQFP $Q_{\text{protocol}}$ such that solutions to $Q_{\text{protocol}}$ are in 1-1 correspondence with protocols of structure $𝒯$ for computing $f$, i.e., associations of rectangles to the nodes of $𝒯$ that form a valid protocol for computing $f$. Then, there will exist a protocol with structure $𝒯$ computing the function $f$ if and only if there is a solution to $Q_{\text{protocol}}$.

The central feature of $Q_{\text{protocol}}$ is that we have one variable $A_t(x)$ for each node $t$ and each input $x$ of Alice, and one variable $B_t(y)$ for each node $t$ and each input $y$ of Bob, so that the product $A_t(x)\cdot B_t(y)$ is to be interpreted as an indicator of whether the input $(x,y)$ belongs to the rectangle associated with node $t$. Given this particular choice of variables, the constraints are the most obvious possible. We give a detailed description of the HQFP in the full version of our paper [11] and over here we directly provide the SDFP relaxation $P_{\text{protocol}}$. It will follow, then, that one can view a solution of $P_{\text{protocol}}$ as a generalization of a protocol computing $f$ and we refer to the solutions of $P_{\text{protocol}}$ as “${\gamma }_2$ protocols” due to their relationship with the ${\gamma }_2$ norm that we will describe shortly.

Recall that a SDFP asks whether there exists vectors obeying some linear constraints on the inner products.

A (binary, two-player) ${\gamma }_2$ deterministic protocol is a tuple $\pi =(𝒳\times 𝒴,𝒯,d,\alpha ,\beta )$, where $𝒳\times 𝒴$ is a finite product set of inputs, $𝒯$ is a protocol structure, and $\alpha$ and $\beta$ are collections of maps ${\alpha }_t:𝒳\to {ℝ}^d$ and ${\beta }_t:𝒴\to {ℝ}^d$, for each node $t\in 𝒯$, satisfying a number of constraints below – that arise from relaxation of the standard protocol constraints described above, where we replace the multiplication by the standard inner product $⟨\cdot ,\cdot ⟩$ in ${ℝ}^d$.

Root constraints.

For the root $\lambda$ of $𝒯$ we have the following constraints.

	$⟨{\alpha }_{\lambda }(x),{\alpha }_{\lambda }(x^{\prime })⟩$	$=1$	$\forall x,x^{\prime }\in 𝒳$
	$⟨{\beta }_{\lambda }(y),{\beta }_{\lambda }(y^{\prime })⟩$	$=1$	$\forall y,y^{\prime }\in 𝒴$
	$⟨{\alpha }_{\lambda }(x),{\beta }_{\lambda }(y)⟩$	$=1$	$\forall (x,y)\in 𝒳\times 𝒴$

This implies that every ${\alpha }_{\lambda }(x)$ and ${\beta }_{\lambda }(x)$ is the same unit-length vector (in ${\mathrm{\ell }}_2$ norm).

Alice’s nodes constraints.

Let $t\in 𝒯$ be an Alice’s node with children $t0,t1$. We impose the following constraints which are equivalent to saying (using the Cauchy-Schwarz inequality and the Pythagorean theorem) that for any $x\in 𝒳$ and $y\in 𝒴$, we have that ${\alpha }_t(x)={\alpha }_{t0}(x)+{\alpha }_{t1}(x)$, ${\alpha }_{t0}(x)$ and ${\alpha }_{t1}(x)$ are orthogonal, and ${\beta }_t(y)={\beta }_{t0}(y)={\beta }_{t1}(y)$. (Note that if we restrict to $1$-dimensional vectors, this is exactly how a rectangle gets partitioned into subrectangles at an Alice node.)

	${\Vert {\alpha }_{t0}(x)\Vert }^2+{\Vert {\alpha }_{t1}(x)\Vert }^2$	$={\Vert {\alpha }_t(x)\Vert }^2$	$\forall x\in 𝒳$
	$⟨{\alpha }_{t0}(x),{\alpha }_t(x)⟩+⟨{\alpha }_{t1}(x),{\alpha }_t(x)⟩$	$={\Vert {\alpha }_t(x)\Vert }^2$	$\forall x\in 𝒳$
	$⟨{\alpha }_{t0}(x),{\alpha }_{t1}(x)⟩$	$=0$	$\forall x\in 𝒳$
	${\Vert {\beta }_{t0}(y)\Vert }^2$	$={\Vert {\beta }_t(y)\Vert }^2$	$\forall y\in 𝒴$
	${\Vert {\beta }_{t1}(y)\Vert }^2$	$={\Vert {\beta }_t(y)\Vert }^2$	$\forall y\in 𝒴$
	$⟨{\beta }_{t0}(y),{\beta }_t(y)⟩$	$={\Vert {\beta }_t(y)\Vert }^2$	$\forall y\in 𝒴$
	$⟨{\beta }_{t1}(y),{\beta }_t(y)⟩$	$={\Vert {\beta }_t(y)\Vert }^2$	$\forall y\in 𝒴$

Bob’s nodes constraints.

The constraints for Bob’s nodes are analogous to Alice’s node constraints.

Let $f\subseteq 𝒳\times 𝒴\times 𝒵$ be a relation with output set $𝒵\subseteq {\{0,1\}}^k$ and let $\pi =(𝒳\times 𝒴,𝒯,d,\alpha ,\beta )$ be a ${\gamma }_2$ protocol. We say that $\pi$ computes $f$ if the depth of every leaf $\mathrm{\ell }\in 𝒯$ is at least $k$, and the collections $\alpha$ and $\beta$ satisfy the following constraints.

Computational constraints.

For every leaf $\mathrm{\ell }\in 𝒯$ of the form $\mathrm{\ell }=tz$ for some $z\in {\{0,1\}}^k$ we have the following constraints:

$⟨{\alpha }_{\mathrm{\ell }}(x),{\beta }_{\mathrm{\ell }}(y)⟩$

$=0$

$\forall (x,y)\in 𝒳\times 𝒴\text{ s.t. }(x,y,z)\notin f$

The deterministic ${\gamma }_2$ communication complexity of $f$, ${\mathsf{\Gamma }}_{\mathrm{𝟤}}{𝖣}^{\mathrm{𝖼𝖼}}(f)$, is the smallest depth of a protocol structure $𝒯$ such that there exists a ${\gamma }_2$ deterministic protocol $\pi =(𝒳\times 𝒴,𝒯,d,\alpha ,\beta )$ that computes $f$.

Let us begin by contrasting what we will do in Section 5 with what we have done in Section 4. As before, we will formulate the existence of a two-party deterministic protocol computing $f$ as a HQFP. In the previous section, for every node $t$ in the protocol tree we had variables ${\{A_t(x)\}}_{x\in 𝒳}\cup {\{B_t(y)\}}_{y\in 𝒴}$. The different starting point here is that our HQFP will instead have ${\{C_t(x,y)\}}_{x\in 𝒳,y\in 𝒴}$. Before, we interpreted $A_t(x)\cdot B_t(y)\in \{0,1\}$ as indicating whether $(x,y)$ is in the rectangle associated with $t$. Now, instead, we let $C_t(x,y)\in \{0,1\}$ indicate the same thing. The constraints of the new program are again designed in the most obvious way possible, so as to ensure that the HQFP is feasible if and only if $f$ can be computed by a deterministic communication protocol with the given structure. We will then relax the quadratic program to a semidefinite program and see what we get.

Notice the difference in approach. In the previous section we had a rationale to obtain the semidefinite program which we obtained: we wanted to add structure to a known rectangle-like notion, the ${\gamma }_2$ norm, in a similar way to how protocols are obtained from rectangles. The previous model can thus be justified on technical grounds, as, what happens when we add structure to the ${\gamma }_2$ norm?. In contrast, the work in this section began by simply trying to make a different set of constraints where the variables are organized differently. It was surprising to us, then, to discover that the resulting computational model has a natural, functional definition, which is why we call it the “quantum lab” model. We provide the semidefinite program below and then elaborate on the quantum lab interpretation.

A deterministic quantum-lab protocol is a tuple $\pi =(𝒳\times 𝒴,𝒯,d,\psi )$, where $𝒳\times 𝒴$ is a finite product set of inputs, $𝒯$ is a protocol structure, and $\psi$ is a collections of maps ${\psi }_t:𝒳\times 𝒴\to {ℝ}^d$, for each node $t\in 𝒯$, satisfying the following constraints.

Root constraints.

For the root $\lambda$ of $𝒯$ we have:

${\psi }_{\lambda }(x,y)\cdot {\psi }_{\lambda }(x^{\prime },y^{\prime })$

$=1$

$\forall x,x^{\prime }\in 𝒳,y,y^{\prime }\in 𝒴$

This implies that every ${\psi }_{\lambda }(x,y)$ is the same unit-length vector.

Alice’s nodes constraints.

For $t\in 𝒯$ an Alice node with children $t0,t1$:

	${\Vert {\psi }_{t0}(x,y)\Vert }^2+{\Vert {\psi }_{t1}(x,y)\Vert }^2$	$={\Vert {\psi }_t(x,y)\Vert }^2$	$\forall x\in 𝒳$
	$⟨{\psi }_{t0}(x,y),{\psi }_t(x,y)⟩+⟨{\psi }_{t1}(x,y),{\psi }_t(x,y)⟩$	$={\Vert {\psi }_t(x,y)\Vert }^2$	$\forall x\in 𝒳$
	$⟨{\psi }_{t0}(x,y),{\psi }_{t1}(x,y^{\prime })⟩$	$=0$	$\forall x\in 𝒳,y,y^{\prime }\in 𝒴$

While the first two constraints above are just an orthogonal decomposition, the third constraint is more subtle. It is a relaxation of a constraint in the HQFP that maintains that when Alice makes a decision on what to communicate on input $x$, the same decision is made regardless of what the value of $y$ is.

Bob’s nodes constraints.

The constraints for Bob’s nodes are analogous to Alice’s node constraints.

We are only missing the constraints that define when a protocol computes a relation. So let $f\subseteq 𝒳\times 𝒴\times 𝒵$ be a relation with output set $𝒵\subseteq {\{0,1\}}^k$ and let $\pi =(𝒳\times 𝒴,𝒯,d,\psi )$ be a quantum lab protocol. We say that $\pi$ computes $f$ if the depth of every leaf $\mathrm{\ell }\in 𝒯$ is at least $k$, and $\psi$ satisfies:

Computational constraints.

For every leaf $\mathrm{\ell }\in 𝒯$ of the form $\mathrm{\ell }=tz$ for some $z\in {\{0,1\}}^k$ we have the following constraints:

${\Vert {\psi }_{\mathrm{\ell }}(x,y)\Vert }^2$

$=0$

$\forall (x,y)\in 𝒳\times 𝒴\text{ s.t. }(x,y,z)\notin f$

We assume that the reader is familiar with Boolean formulas, Boolean circuits, and communication complexity. Recall that the Karchmer–Wigderson theorem states that the minimum depth of a Boolean circuit or formula that computes a given Boolean function $f:{\{0,1\}}^n\to \{0,1\}$, is equal to the communication complexity of the Karchmer–Wigderson relation ${\mathrm{𝖪𝖶}}_f$, where Alice is given $x\in f^{-1}(1)$ and Bob is given $y\in f^{-1}(0)$, and they wish to find some $i$ such that $x_i\ne y_i$. A proof can be found in [16, Section 10.2, see also Chapters 5 & 10].