\stackMath

The Quantum and Classical Streaming Complexity of
Quantum and Classical Max-Cut

John Kallaugher
Sandia National Laboratories
[email protected] Ojas Parekh
Sandia National Laboratories
[email protected]

Abstract

We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and Krachun [STOC ‘19] resolved the classical complexity of the classical problem, showing that any $(2-\varepsilon)$ -approximation requires $\Omega(n)$ space (a $2$ -approximation is trivial with $\textrm{O}(\log n)$ space). We generalize both of these qualifiers, demonstrating $\Omega(n)$ space lower bounds for $(2-\varepsilon)$ -approximating Max-Cut and Quantum Max-Cut, even if the algorithm is allowed to maintain a quantum state. As the trivial approximation algorithm for Quantum Max-Cut only gives a $4$ -approximation, we show tightness with an algorithm that returns a $(2+\varepsilon)$ -approximation to the Quantum Max-Cut value of a graph in $\textrm{O}(\log n)$ space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $\textrm{o}(n)$ space.

We prove our lower bounds through the techniques of Boolean Fourier analysis. We give the first application of these methods to sequential one-way quantum communication, in which each player receives a quantum message from the previous player, and can then perform arbitrary quantum operations on it before sending it to the next. To this end, we show how Fourier-analytic techniques may be used to understand the application of a quantum channel.

1 Introduction

Quantum approaches for discrete optimization, such as the Quantum Approximate Optimization Algorithm (QAOA) have received significant attention. The seminal work of Farhi, Goldstone, and Gutmann [FGG14] showed that QAOA applied to an NP-hard classical constraint satisfaction problem (CSP) gave a better worst-case approximation than the best known classical approximation algorithm at the time. An improved classical approximation algorithm subsequently followed [BMO⁺15]; however, this seeded the question of whether a quantum approximation algorithm might offer a provably better approximation guarantee than the best classical approximation for some CSP or discrete optimization problem, which still remains open. One potential barrier is that classical hardness of approximation results may also restrict quantum approximation algorithms. For example, it is generally not expected that $\textsf{NP}\subseteq\textsf{BQP}$ , so a quantum approximation is not expected to overcome NP-hardness of approximation results. Even possibly weaker hardness assumptions such as Unique-Games-hardness may impede quantum approximations. It would be surprising if a quantum approximation were able to achieve a $(1/0.878\ldots-\varepsilon)$ -approximation¹¹1This result is more typically stated as $0.878\ldots+\varepsilon$ , where an $\alpha$ -approximation is held to mean returning a value in $[\alpha\cdot\text{OPT},\text{OPT}]$ , for OPT the correct value. However, we follow previous work on streaming Max-Cut by instead using a $K$ -approximation to mean returning a value in $[\text{OPT},K\cdot\text{Opt}]$ . for the Maximum Cut Problem (Max-Cut), which is Unique-Games-hard [KKMO07].

Although the prospects for quantum approximations for classical CSPs may seem limited, a natural question is whether quantum approximations can offer provably better guarantees for quantum versions of CSPs. The $k$ -Local Hamiltonian Problem ( $k$ -LH) serves as the canonical QMA-hard quantum generalization of $k$ -CSP. A recent line of work has enjoyed success in devising nontrivial classical approximations for $2$ -LH [GK12, BH16, BGKT19, GP19, PT21b, AGM20, PT21a, AGMKS21]; however, truly quantum approximations for LH remain elusive. Hardness of approximation results with respect to QMA are even more elusive, as the existence of a quantum analogue of the classical PCP theorem, a cornerstone for hardness of approximation, remains a major open question [AAV13, NV18].

We seek to understand the power of quantum versus classical approximations for $2$ -CSP and $2$ -LH in the streaming setting, where space is the computational quantity of interest. In particular we consider the Max-Cut (MC) and Quantum Max-Cut (QMC) problems. Max-Cut is a prototypical CSP in the sense that approximation and hardness results are typically devised for Max-Cut and then generalized to other CSPs; Quantum Max-Cut has emerged to serve a similar role in approximating $2$ -LH. Quantum Max-Cut is also closely related to the quantum Heisenberg model (see [GP19]), which is a well-studied model of quantum magnetism introduced in the late 1920s.

For classical algorithms applied to classical Max-Cut, tight bounds²²2Up to log factors in the space complexity, as is typical for streaming algorithms. for the space complexity in terms of the approximation factor are known [KK19]—our work generalizes these results in both ways, giving tight bounds on the approximation factor attainable in $\operatorname*{o}\left\lparen n\right\rparen$ space by quantum streaming algorithms for classical Max-Cut and by quantum and classical algorithms for Quantum Max-Cut.

We find, perhaps surprisingly, that quantum streaming algorithms offer no advantage over classical ones in approximating Max-Cut or Quantum Max-Cut. Although our main contribution is a quantum hardness result, the matching upper bound for approximating Quantum Max-Cut in the stream requires analyzing a nontrivial streaming algorithm, which is a departure from the case of Max-Cut.

1.1 Our Contributions

Ours is the first work to consider streaming versions of $2$ -LH or any kind of quantum optimization problem. Just as the results of [KK19] have been expanded for more general CSPs, we expect that our results for Quantum Max-Cut will apply to more general instances of $2$ -LH. Indeed there is precedent for this in the standard approximation setting [HLP20, PT21b].

We give tight (up to an arbitrarily small additive constant in the approximation factor) characterizations of the best possible approximation factor achievable in $\operatorname*{o}\left\lparen n\right\rparen$ space for quantum and classical algorithms for quantum and classical Max-Cut. Our results are laid out in Table 1.

	Max-Cut		Quantum Max-Cut
Approximation Factor	$2+\varepsilon$	$2-\varepsilon$	$2+\varepsilon$	$2-\varepsilon$
Classical Algorithm	$\operatorname*{O}\left\lparen\log n\right\rparen$	$\operatorname*{\Omega}\left\lparen n\right\rparen$	$\operatorname*{O}\left\lparen\log n\right\rparen$	$\operatorname*{\Omega}\left\lparen n\right\rparen$
Quantum Algorithm	$\operatorname*{O}\left\lparen\log n\right\rparen$	$\Omega(n)$	$\operatorname*{O}\left\lparen\log n\right\rparen$	$\operatorname*{\Omega}\left\lparen n\right\rparen$

Table 1: The space needed by quantum and classical algorithms for quantum and classical Max-Cut. Results from this paper are shown in bold.

Our lower bounds are encompassed in the following theorem (the classical lower bound for Quantum Max-Cut is a special case of this, as any classical streaming algorithm can be implemented as a quantum streaming algorithm).

Theorem 1.

For any $\varepsilon>0$ , any quantum streaming algorithm for Max-Cut or Quantum Max-Cut that returns a $(2-\varepsilon)$ -approximation with probability $2/3$ requires

n/2^{\operatorname*{O}\left\lparen 1/\varepsilon^{2}\right\rparen}

qubits of storage.

For Max-Cut the upper bound for $(2+\varepsilon)$ -approximation (in fact, even $2$ -approximation) is trivial, as a graph on $m$ edges always has Max-Cut value between $m/2$ and $m$ . However, for Quantum Max-Cut the trivial approximation is only a $4$ -approximation, so we give an algorithm that returns a $(2+\varepsilon)$ -approximation using $\operatorname*{O}\left\lparen\log n\right\rparen$ space. We also give an algorithm for weighted graphs, but in this case we are only able to attain a $(5/2+\varepsilon)$ -approximation (the lower bound remains a 2-approximation).

Theorem 2.

Let $G$ be a weighted graph on $n$ vertices with weights that are multiples of $1/\operatorname{poly}(n)$ . Then for any $\varepsilon,\delta\in(0,1)$ there is a streaming algorithm that returns a $(5/2+\varepsilon)$ -approximation to the Quantum Max-Cut value of $G$ with probability at least $1-\delta$ using $\operatorname*{O}\left\lparen\frac{1}{\varepsilon^{2}}\log\frac{1}{\delta}\log n\right\rparen$ space. If all the weights in the graph are $1$ , it returns a $(2+\varepsilon)$ -approximation instead.

We note here two lacunae in our results for (unweighted) graphs. Firstly, for classical Max-Cut it is possible to achieve a $(1+\varepsilon)$ -approximation in $\operatorname*{\widetilde{O}}\left\lparen n\right\rparen$ space, through the use of cut-preserving sparsifiers [AG09]. However, analogous results on sparsifiers for general $2$ -local Hamiltonians are not known, and indeed there are results pointing in the opposite direction [AZ19]. So while we can characterize the approximation factors possible in sublinear space the semi-streaming complexity remains open. Secondly, our $\operatorname*{O}\left\lparen\log n\right\rparen$ -space upper bound for Quantum Max-Cut only gives a $(2+\varepsilon)$ -approximation instead of a $2$ -approximation. This is a consequence of the fact that it is based on graph parameters that must themselves be approximated rather than just the number of edges, which can be calculated exactly.

Fourier Analysis for Quantum Channels

The technical core of our lower bound is a quantum communication complexity bound for a sequential one-way communication problem (originally introduced in [KK19] in the classical setting), in which the first player sends a message to the second player, the second to the third, and so on. Our bound for this problem is based on a novel application of Boolean Fourier analysis³³3For a general overview of Boolean Fourier analysis, see [O’D14].—in particular, we prove that a key inequality associated with this problem, analyzed in [KK19] for the classical case, is preserved even in the presence of quantum communication.

The application of Boolean Fourier Analysis to two-player one-way communication problems in the classical setting goes back to [GKK⁺07], in which it was used to prove lower bounds for the Boolean Hidden Matching problem (and its application to communication complexity more generally goes back further, e.g. [Raz95, Kla07]). This problem, and its generalization in the Boolean Hidden Hypermatching problem (analyzed in [VY11]), are the main route by which Fourier analysis has contributed to lower bounds for streaming algorithms.

However, in later years these techniques have been extended to communication lower bounds (and corresponding streaming lower bounds) with different configurations of players. In [KKP18] they were applied to problems where many players communicate with a single referee, while in [KKSV17] they were extended to problems where players communicate in a line, as is the case in the Distributed Implicit Partition Problem (from [KK19]) we make use of in this paper. In [CGS⁺22], a generalization of this problem was studied through the use of Fourier analysis on $\mathbb{Z}_{q}^{n}$ .

The core ingredient of most of these lower bounds is a hypercontractive Fourier coefficients lemma from [KKL88], that can be seen as generalizing facts about sampling protocols, in which a player chooses some subset of their input to send to protocols where players send arbitrary (classical) messages. This lemma was generalized to matrix-valued functions in [BARdW08], opening the door to the application of Fourier-analytic methods to lower bounds for quantum communication protocols, as these can be seen as functions from inputs to density matrices.

This was first used to prove quantum lower bounds on the complexity of the Boolean Hidden Hypermatching problem [SW12]. This result was further generalized in [DM20], while [AD21] generalized the Fourier coefficients lemma further, in order to obtain quantum lower bounds for Max-Cut and more general hypergraph problems. However, these are all two-player one-way communication problems. We give the first application of Fourier-analytic techniques to sequential quantum one-way communication. The key technical challenge is in finding methods for applying Fourier analysis to the application of quantum channels.

In classical communication, as long as we consider a single “hard” input distribution, a player’s message can be without loss of generality assumed to be a deterministic function of the message they received and their input. In sequential quantum communication, however, the player may apply an arbitrary quantum channel to the message they receive. Our key insight is that, as quantum channels are linear operators, many of the techniques of Fourier analysis, including the convolution lemma for Fourier coefficients, may be applied to them.

1.2 Other Related Work

Streaming bounds for Max-Cut

The fact that that a $2$ -approximation for Max-Cut is possible in $\operatorname*{O}\left\lparen\log n\right\rparen$ space is an immediate consequence of the fact that the Max-Cut value is always at least $m/2$ . Less immediately, but still a consequence of standard results in streaming algorithms, is the fact that it can be $(1+\varepsilon)$ -approximated in $\operatorname*{\widetilde{O}}\left\lparen n\right\rparen$ space, through sparsifiers that preserve cut values [AG09]. The question, then, was whether a better approximation than the first could be attained in less space than the second.

In [KK15, KKS15], it was shown that any $(2-\varepsilon)$ -approximation would require at least polynomial space in $n$ , while [KKSV17] showed that $(1+\varepsilon)$ -approximation would require $\operatorname*{\Omega}\left\lparen n\right\rparen$ space. This left open the possibility of intermediate results, but [KK19] closed the door on this possibility, proving that $(2-\varepsilon)$ -approximation would require $\operatorname*{\Omega}\left\lparen n\right\rparen$ space for any constant $\varepsilon>0$ .

However, the above results are only for classical algorithms. In [AD21], a polynomial lower bound was shown that applies even to quantum streaming algorithms, but this left open the possibility that a $(2-\varepsilon)$ approximation was possible in $\operatorname*{o}\left\lparen n\right\rparen$ space for quantum algorithms.

Quantum streaming algorithms

The first work on quantum streaming was [LG06], which showed that there are problems that that are exponentially easier for quantum streaming algorithms than classical ones. In [GKK⁺08], it was shown that this is true even for a function that does not depend on the order of the stream (the more “standard” streaming model).

Later work has investigated the question of whether quantum streaming can obtain advantages over classical for problems of independent classical interest (as the aforementioned work is for problems constructed for the purpose of proving separations). The problem of recognizing Dyck(2) in the stream was considered as a candidate problem in [JN14, NT17], but only negative results were found. For problems where $\operatorname*{\omega}\left\lparen 1\right\rparen$ passes are allowed over the stream, [Mon16] and [HM19] showed an advantage for the well-studied moment estimation problem. Later, [Kal22] showed that an advantage exists in the one-pass setting for the problem of counting triangles in graph streams.

Approximating Quantum Max-Cut

Quantum Max-Cut was introduced in [GP19], where a classical $1/0.498$ -approximation algorithm was given, akin to the Goemans-Williamson algorithm for Max-Cut, that produces an unentangled product state. Since the gap between the best product state and best entangled quantum state on a single edge is two (see Section 3.3), at best a $2$ -approximation is possible for algorithms that return product states, and so the $1/0.498$ -approximation is nearly optimal among such algorithms. By rounding to entangled states, [AGM20] gave the first approximation with guarantee better than 2. Subsequently [PT21a] showed how to use higher levels of the quantum Lasserre hierarchy of semidefinite programs to obtain a slight improvement over [AGM20].

2 Proof Overview

2.1 Lower Bounds

Our lower bounds for the quantum streaming complexity of Max-Cut and Quantum Max-Cut are derived from a new analysis of the Distributional Implicit Hidden Partition (DIHP) problem introduced in [KK19] to prove lower bounds for the streaming complexity of approximating classical Max-Cut. We restate this problem here.

2.1.1 The Distributed Implicit Hidden Partition Problem

In an instance of $\text{\bf DIHP}(n,\alpha,T)$ , $T$ players are each given a partial matching $M_{t}$ of $\alpha n$ edges on $n$ vertices, with each edge labelled with a bit. Either these bit labels are generated by choosing a random partition of $[n]$ and assigning 1 to the edges crossing the partition (a YES case) or they are chosen uniformly at random (a NO case).

The players are allowed one-way communication, from player $i$ to player $i+1$ for each $i$ , and are additionally given the matching edges (but not the edge labels) of every previous player for free. Their goal is to determine whether their inputs were drawn from a YES case or a NO case with probability at least $2/3$ over the random draw and any internal randomness they may use.

Reduction to Classical Max-Cut

If each player $t$ creates the graph $G_{t}$ consisting of edges labelled $1$ in $M_{t}$ , $G=\bigcup_{t}G_{t}$ will be bipartite in a YES case, and close to random in a NO case. This means it is possible to cut every edge in the first case, and not much more than half of them in the second. Therefore, an algorithm that returns a $(2-\varepsilon)$ -approximation to Max-Cut can distinguish them if $\varepsilon$ is large enough (by making $\alpha$ small enough and $T$ large enough, we can make the necessary $\varepsilon$ arbitrarily small). Therefore, a Max-Cut algorithm using $S$ space gives a protocol in which each player sends a size- $S$ message, by having each player run the algorithm on their input and then send their algorithm’s state to the next player. The graphs the players get with this reduction are illustrated in Figure 1.

(a) In a YES case, only edges crossing the underlying partition are included.

(b) In a NO case, each edge received is included with probability

\frac{1}{2}

Figure 1: The graphs each player receives when reducing DIHP to Max-Cut.

One problem with this is that, if the players’ matchings are randomly chosen they may share edges. Our approach to this differs somewhat from that of [KK19]. Instead of considering multigraphs, we take advantage of the fact that player $t$ is allowed to know the matching (but not the edge labels) of players $s<t$ . This means we can have them decline to add edges that are present in previous matchings, guaranteeing that the final graph is simple. We show that, as the number of edges thus removed is small, it has little effect on the reduction.

Extending the Reduction to Quantum Max-Cut

The reduction to Quantum Max-Cut uses exactly the same mapping from DIHP instances to graphs. We consider the following SDP,

\max_{f:V\rightarrow S^{n-1}}\sum_{uv\in E}-\langle f(u),f(v)\rangle

which is a shifted version of the standard Goemans-Williamson SDP for Max-Cut. In particular, its optimal value is an upper bound on $2K-m$ , where $K$ is the Max-Cut value of a graph. Usefully, when $2K-m$ is small, a converse property holds, as the optimal value of this SDP is at most a constant factor times larger than $2K-m$ [CW04]. This means the graphs generated by NO instances of DIHP will have small values of this SDP.

This gives us a Quantum Max-Cut lower bound, because this SDP also upper bounds $\frac{4}{3}Q-\frac{m}{3}$ , where $Q$ is the Quantum Max-Cut value of the graph⁴⁴4See Section 2.3 of [HNP⁺21]. Note that in the cited work, both Quantum Max-Cut and the SDP are scaled by $\frac{1}{m}$ relative to our usage.. So NO instances will create graphs with Quantum Max-Cut value approximately $m/4$ . Conversely YES instances will create graphs with Quantum Max-Cut value at least $m/2$ , as they are bipartite and the Quantum Max-Cut value is always at least half the Max-Cut value. So a $(2-\varepsilon)$ approximation algorithm would suffice to distinguish between the two.

2.1.2 Quantum Communication Lower Bounds for DIHP

In [KK19] it was shown that DIHP is hard when the players are only allowed to send classical messages, requiring $\operatorname*{\Omega}\left\lparen n\right\rparen$ space when $\alpha$ and $T$ are constant. The majority of the technical difficulty of our lower bounds is in proving that DIHP is hard even if the players are allowed to send quantum messages. This immediately implies that quantum algorithms must use $\operatorname*{\Omega}\left\lparen n\right\rparen$ space to $(2-\varepsilon)$ -approximate Max-Cut or Quantum Max-Cut, and so no quantum advantage for either problem is possible.

Reduction to Boolean Fourier Analysis

As with the classical lower bound of [KK19], our proof depends on applying Fourier analysis to functions on the Boolean cube. In particular, we will show that a bound on Fourier coefficients used in the classical proof is maintained even in the presence of quantum communication. We start by providing an intuition for the significance of this bound.

Suppose the game is in a YES case, and so player $t$ ’s input depends only on the matching $M_{t}$ and the randomly chosen partition (which we may write $x\in\{0,1\}^{n}$ , with the bit of vertex $i$ determining which side of the partition it is on). Then, fixing $(M_{s})_{s=1}^{t}$ , we can write a function

f_{t}:\{0,1\}^{n}\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}

where $f(x)$ is the density matrix sent by player $t$ if the partition is $x$ , and $\beta$ is the number of qubits used to represent that state.

Now suppose player $t+1$ would like to determine whether they are in a YES or a NO case. They have received $f_{t}(x)$ if they are in a YES case, and they want to determine if it is consistent with being in a YES case. In addition, they have the bit labels of the edges in $M_{t+1}$ . Therefore, for any odd-cardinality set of edges in $M_{t+1}$ , they know the parity of the set of vertices in $x$ matched by these edges. We write such sets of vertices as $M_{t+1}^{\text{tr}}s$ for a string $s\in\{0,1\}^{\alpha n}$ indexing a subset of the edges in $M_{t+1}$ .

Now suppose the player looked at only one of these sets $s$ , and so knew the parity of the vertices $M_{t+1}^{\text{tr}}s$ alone. To tell whether $f_{t}(x)$ could come from a YES instance, they need⁵⁵5We are eliding the possibility that, for instance, the state player $t+1$ receives is impossible or unlikely in a YES case due to, for instance, only arising if a triangle in previously arrived edges has every edge labelled 1. However it turns out this possibility is already accounted for by considering what a previous player would’ve seen on receiving the third edge of that triangle. its average value when the parity of $M_{t+1}^{\text{tr}}s$ is $0$ to be distinguishable from its average value when the parity of $M_{t+1}^{\text{tr}}s$ is $1$ .

The distinguishability of two distributions over quantum states is given by the trace norm of the difference between their density matrices, so the quantity the player would need to be large is

	$\displaystyle\frac{1}{2}\left\lVert\frac{1}{2^{n-1}}\sum_{\begin{subarray}{c}x\in\{0,1\}^{n}:\\ x\cdot M_{t+1}^{\text{tr}}s=0\end{subarray}}f_{t}(x)-\frac{1}{2^{n-1}}\sum_{\begin{subarray}{c}x\in\{0,1\}^{n}:\\ x\cdot M_{t+1}^{\text{tr}}s=1\end{subarray}}f_{t}(x)\right\rVert_{1}$	$\displaystyle=\frac{1}{2^{n}}\left\lVert\sum_{x\in\{0,1\}^{n}}f_{t}(x)(-1)^{x\cdot M_{t+1}^{\text{tr}}s}\right\rVert_{1}$
		$\displaystyle=\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\rVert_{1}$

where we now introduce $\widehat{f}_{t}$ , the Fourier transform of $f_{t}$ , given by

\widehat{f}(S)=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}f(x)(-1)^{S\cdot x}\text{.}

It turns out that this sums nicely—it can be shown that player $T$ ’s ability to distinguish between a YES and a NO case is bounded by

\sum_{t=1}^{T}\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\rVert_{1}

and so our goal will be to prove that this sum is small in expectation over $(M_{t})_{t=1}^{T}$ .

To prove this, we bound the total value of weight- $2\ell$ Fourier coefficients for every $\ell$ . As a ${\sim}\binom{\alpha n}{\ell}/\binom{n}{2\ell}$ fraction of these will end up being matched by a set of $\ell$ matching edges, it suffices to prove that the value is bounded by⁶⁶6This expression changes somewhat when $\ell\geq\beta$ , but we will disregard those highest-order terms in this overview.

\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}

where we have dropped some constants exponential in $T$ and $\ell$ . Then if $\beta\ll n$ , this expression will be small enough for the final states to be hard to distinguish.

The Evolution of Fourier Coefficients

We will bound the expression above by induction on $t$ , considering how these coefficients evolve based on the message sent from player $t$ to player $t+1$ . This is where the quantum difficulty of the proof will arise, and is the most important novel element in our analysis—the combinatorial aspects of the evolution are similar to those in the classical case but now player $t$ may apply a quantum channel to generate $f_{t}$ rather than sending a deterministic⁷⁷7When proving a lower bound for a classical communication problem with a known input distribution, one may without loss of generality assume the players act deterministically. message based on their input and the message $f_{t-1}$ .

The base case of the induction is straightforward (for simplicity we can think of player 1 as receiving $0^{\beta}$ from a player $0$ , and consider only an inductive step). For the inductive step, we need to understand the effect of player $t$ applying a quantum channel $\mathcal{A}$ to $f_{t-1}(x)$ . This quantum channel itself is determined by player $t$ ’s input, and therefore (again fixing $(M_{s})_{s=1}^{t}$ ) we can write $\mathcal{A}_{x}$ for its value when the underlying partition is $x$ . As quantum channels are linear operators, we can define a Fourier transform

\widehat{\mathcal{A}}_{S}=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\mathcal{A}_{x}(-1)^{S\cdot x}

that in particular obeys the convolution lemma for the Boolean Fourier transform, which tells us that

\widehat{\mathcal{A}_{x}f_{t-1}(x)}(S)=\sum_{U}\widehat{\mathcal{A}}_{U}\widehat{f}_{t-1}(U\oplus S)\text{.}

Using the fact that $\widehat{\mathcal{A}}_{U}$ is $0$ whenever $U$ is not $M_{t}s$ for some $s\in\{0,1\}^{\alpha n}$ (intuitively, this is because $\mathcal{A}_{x}$ only depends on the edge labels of the edges in $M_{t}$ ), we can write down “mass transfer” lemmas describing how coefficients of weight $2\ell_{2}$ of $f_{t}$ are formed from coefficients of weight $2\ell_{1}$ of $f_{t-1}$ . We want to know how much weight can be contributed to $\widehat{\mathcal{A}_{x}f_{t-1}(x)}(S)$ from $\widehat{\mathcal{A}}_{U}\widehat{f}_{t-1}(M_{t}^{\text{tr}}s\oplus S)$ where $|S|=\ell_{2}$ and $M_{t}^{\text{tr}}s\oplus S=\ell_{1}$ .

We can think of this in terms of three more parameters, $a$ the number of edges from $M_{t}^{\text{tr}}s$ that are entirely contained in $S$ , $b$ the number of edges that each have one endpoint in $S$ , $c$ the number that are entirely outside of $S$ (so $\ell_{2}=\ell_{1}-a+c$ ). We end up with the amount of “mass” transferred from $\ell_{1}$ -weight coefficients via $M^{\text{tr}}_{t}s$ with this property being bounded by

\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell_{1}\end{subarray}}\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ |u|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ |v|=b\end{subarray}}I_{S}(u)B_{S}(v)\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ |w|=c\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)\rVert_{1}

where $I_{S}(u)$ and $B_{S}(v)$ are indicator variables on whether $M_{t}^{\text{tr}}u$ is entirely contained in $S$ and $M_{t}^{\text{tr}}v$ has one endpoint of each edge in $S$ . See Figure 2 for an illustration.

Figure 2: When player

t

receives the matching

M_{t}

, each subset

s

of the edges in

M_{t}

and each Fourier coefficient

\widehat{f}_{t-1}(S)

corresponds to a new Fourier coefficient

\widehat{f}_{t}(S\oplus M_{t}^{\text{tr}}s)

. In this example

s

includes

a=1

edge internal to

S

b=2

edges with one endpoint in

S

, and

c=1

edge outside, so the resulting coefficient

S\oplus M_{t}^{\text{tr}}s

has weight

|S|+a-c=5

The final tool we need to bound this is an extension of the matrix-valued Fourier coefficients inequality, a consequence of Theorem 1 of [BARdW08] (itself a generalization of a lemma of [KKL88]) that has previously been used for two-player quantum lower bounds [SW12, DM20, AD21]. This will tell us that⁸⁸8Again, this has to be somewhat changed when $c$ is particularly large.

\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ |w|=c\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)\rVert_{1}=\binom{\operatorname*{O}\left\lparen\beta\right\rparen}{c}\left\lVert\widehat{f}_{t-1}(S)\right\rVert_{1}\text{.}

With this in place, and using the fact that

\operatorname*{\mathbb{P}}\left[I_{S}(u)B_{S}(v)\right]\sim\frac{\binom{\ell_{1}}{a}}{\binom{n}{a}}\cdot\frac{\binom{\ell_{1}}{b}}{\binom{n}{b}}

we can bound the above in expectation over $M_{t}$ , and from then the proof becomes an exercise in carefully evaluating sums.

2.2 Space Upper Bounds for Quantum Max-Cut

For classical Max-Cut a trivial classical algorithm achieving a $2$ -approximation in logarithmic space is already known—count the number of edges (or total weight for a weighted graph) $m$ and report $m$ , which is at most twice the true value. As our lower bound for quantum algorithms for classical Max-Cut is the same as the classical one, nothing more is needed here. However, for Quantum Max-Cut the story is a bit different. The trivial lower bound in this case is $m/4$ , and so the aforementioned algorithm would only guarantee a 4-approximation.

We give a simple algorithm that achieves a $(2+\varepsilon)$ -approximation in the unweighted case, and a $(5/2+\varepsilon)$ -approximation in the weighted case. The basic idea will be the same in both cases, so for ease of exposition the rest of the discussion in this section will assume a weighted graph, and we will point out where every edge having unit weight allows a better approximation.

Upper Bounding the QMC Value

Let $m$ be the total weight of the graph, and let $W=\sum_{u\in V}\max_{v\in N(u)}w_{uv}$ , the sum of the max-weight edges incident to each vertex (so $W$ is just the number of non-isolated vertices in the unweighted case). It is known [AGM20] (see Lemma 24) that

\frac{m}{2}+\frac{W}{4}

is an upper bound for Quantum Max-Cut. So we want lower bounds in terms of $m$ and $W$ .

Lower Bounding the QMC Value in General Weighted Graphs

We use a modified version of an argument of [AGM20]. Consider the subgraph formed by taking the highest-weight edge incident to every vertex. We can decompose this into a matching $M$ consisting of every edge “chosen” by two vertices, and a forest $F$ of all the other edges (note that the two together are also a forest). Abusing notation to use the names of the objects to also denote their total weights, we have $2M+F=W$ .

Now, for any edge, it is possible to earn Quantum Max-Cut energy equal to its weight by assigning its vertices the singlet. Secondly, when we have a collection of vertex-disjoint graphs it is possible to maximize each of their Quantum Max-Cut energies separately and still earn energy $w_{e}/4$ for each edge $e$ between distinct pairs of graphs. So there is a solution earning $M+(m-M)/4$ .

Secondly, as $M\cup F$ is a forest, cutting it clasically earns energy $(M+F)/2$ , as any classical cut gives a quantum cut earning at least half as much energy. By minimizing these two expressions subject to $2M+F=W$ it can be shown that the Quantum Max-Cut value is at least

\frac{m}{5}+\frac{W}{10}

giving a $(5/2)$ -approximation determined only by $m$ and $W$ . We illustrate this construction in Figure 3.

Figure 3: Proving a lower bound for the optimal Quantum Max-Cut value of a weighted graph. The edges “chosen” by one vertex (in solid black) form a tree

T

, while the edges “chosen” by two (in solid red) form a matching

M

. There is an assignment earning energy

\frac{T+M}{2}=12

from assigning a perfect classical cut to

T\cup M

, and one earning energy

M+\frac{M-m}{4}=14

from assigning the singlet to every edge in

M

and earning

w_{e}/4

on every other edge.

Lower Bounding the QMC Value in Unweighted Graphs

In the unweighted case we have the advantage that any method for choosing a maximal tree chooses one of optimal weight, and so (inspired by a method of [GY21]) we consider depth-first search trees. We will assume the graph is connected—note that $m$ , $W$ , and the Quantum Max-Cut value all sum up over components, so as long as the lower bound we show is linear in $m$ and $W$ this will immediately generalize.

In the weighted case, trying to optimize the energy we earned from our tree meant potentially earning nothing from edges outside the tree, as we had no control over how they might cross the tree. However, with a DFS tree, we have the following useful property: for any node in the tree, the subtrees rooted at its children are disconnected from each other (because otherwise those connecting edges would have been explored before both subtrees were). This means we can do the following: choose either the even or odd levels (with level $i$ being edges from depth- $i$ vertices to depth- $(i+1)$ vertices) of the tree, one of which will contain at least half the edges; call this set of edges $H$ . Now, $H$ consists of disjoint bipartite subgraphs, and no edge outside the tree connects two edges in the same level of $H$ . Thus, as noted above for the weighted case, there is an optimal Quantum Max-Cut solution for $H$ that still earns $1/4$ from every edge outside the tree, and from the edges in the unchosen levels. An optimal classical solution of this kind on $H$ earns a Quantum Max-Cut value of $1/2$ on each edge in $H$ (by randomly selecting either a fixed assignment that cuts all the edges or the “bit-flipped” assignment, independently for each component of $H$ ).

Now, as the tree contains $W-1$ edges, merely using the optimal classical solution would only earn us at least $\frac{W-1}{4}+\frac{m-(W-1)/2}{4}$ , which is not quite as strong as we want. But each level of the tree is a disjoint union of stars, and the optimal Quantum Max-Cut assignment for a star with $d$ leaves earns $\frac{d+1}{2}$ . So we can earn at least $1/2$ more energy, giving us

\frac{W-1}{4}+\frac{m-(W-1)/2}{4}+\frac{1}{2}>\frac{m}{4}+\frac{W}{8}

for a $2$ -approximation determined only by $m$ and $W$ . We illustrate this construction in Figure 4.

Figure 4: Proving a lower bound for the optimal Quantum Max-Cut value of an unweighted graph based on a DFS tree (the solid edges in the graph). The heavier half of the levels in the DFS (colored in red) are given an optimal assignment, and then every other edge (solid and dashed) earns 1/4. The total energy earned in this example is

\frac{3}{2}+\frac{3}{2}+\frac{7}{4}=4.75

Estimating $W$ in the Stream

To obtain an actual algorithm we will need a $(1+\varepsilon)$ -multiplicative approximation to $m/2+W/4$ . Counting $m$ is trivial, and in the unweighted case $W$ can be approximated with cardinality estimation algorithms. So the problem we need to resolve (ideally in $\operatorname*{O}\left\lparen\log n\right\rparen$ space) is estimating

\sum_{u\in V}\max_{v\in N(u)}w_{uv}

in the stream. Our approach is to use reservoir sampling to sample edges $e$ with probability proportion to $w_{e}$ , choose an endpoint at random, and then check whether they are higher-weight than every edge that arrives after them in the stream (since we can’t check edges that arrive earlier). If we defined an estimator that is $1$ whenever this happened and $0$ otherwise, we would get a contribution of $w_{e}/2$ for every vertex $u$ and $v\in N(u)$ such that $w_{uv}$ was a “scenic viewpoint”, an edge of higher weight than all subsequent edges incident to $u$ .

To correct for this, we also check the weight $w^{\prime}$ of the highest-weight edge to arrive incident to $u$ after $uv$ (calling it $0$ if $uv$ is the last edge) and then subtract $w^{\prime}/w_{uv}$ . This gives us an estimator with expectation

W/2m

and constant variance, that we can compute in logarithmic space. So we could have trouble getting a multiplicative estimate of $W$ if $m\gg W$ , but this isn’t a problem—we only want an estimate of $m/2+W/4$ , and so a $\varepsilon m$ -approximation of $W$ suffices. This then gives us our full streaming algorithm, obtaining a $(2+\varepsilon)$ - and $(5/2+\varepsilon)$ -approximation in the unweighted and weighted case, respectively, using $\operatorname*{O}\left\lparen\log n\right\rparen$ space if $\varepsilon$ is constant.

3 Preliminaries

3.1 Notation

We will generally write $\beta$ for the number of qubits an algorithm uses. We will therefore write the state of the algorithm as a density matrix in $\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ . However, when considering Quantum Max-Cut assignments, qubits will typically correspond to vertices in a graph $(V,E)$ , in which case we will use $n$ to denote both $|V|$ and the number of qubits; we expect this will be clear from context.

In defining Quantum Max-Cut, we will need to use the Pauli matrices. These are defined as:

I=\begin{bmatrix}1&0\\ 0&1\end{bmatrix},\,\,\,\,\,\,X=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},\,\,\,\,\,\,Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},\,\text{and}\,\,\,\,\,\,Z=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix}.

The notation $\sigma_{i}$ is used to denote a Pauli matrix $\sigma\in\{X,Y,Z\}$ acting on qubit $i$ :

\sigma_{i}=I\otimes I\otimes\ldots\otimes\sigma\otimes\ldots\otimes I\in\mathbb{C}^{2^{n}\times 2^{n}},

where the $\sigma$ occurs at position $i$ . A Pauli term or term refers to a tensor product of Pauli operators (e.g., $X_{i}X_{j}$ ). We say a term is $k$ -local if it is the tensor product of exactly $k$ (non-identity) Pauli operators (e.g., $I$ is $0$ -local, $Y_{i}$ is $1$ -local, and $X_{i}Z_{j}$ is $2$ -local). A term is odd-local if it is $k$ -local for some odd $k$ , and it is even-local otherwise.

The $4^{n}$ Pauli terms each square to I and are orthonormal under the Hilbert-Schmidt inner product, i.e., $\frac{1}{2^{n}}\operatorname{Tr}[a^{2}]=\frac{1}{2^{n}}\operatorname{Tr}[I]=1$ and $\frac{1}{2^{n}}\operatorname{Tr}[ab]=0$ for distinct Pauli terms $a,b$ . Consequently every Hermitian operator $A$ acting on $n$ qubits (i.e., $A\in\mathbb{C}^{2^{n}\times 2^{n}})$ can be written as a linear combination of Pauli terms with real coefficients.

When we write $\lVert.\rVert_{p}$ for a matrix, we mean the Schatten $p$ -norm, defined as the $p$ -norm of the singular values of the matrix (also known as the trace norm when $p=1$ ). The matrix $D$ representing the state of the algorithm will therefore be positive semi-definite, Hermitian, and satisfy $\lVert D\rVert_{1}=1$ .

We will often be using $x\in\{0,1\}^{n}$ to represent a subset of $[n]$ . In a slight abuse of notation, we will sometimes use $x\in\{0,1\}^{n}$ and $x\subseteq[n]$ interchangeably, when this does not cause ambiguity. We use the “weight” of a set $x$ to refer to $|x|$ , usually in the context of a Fourier coefficient. When dealing with a Fourier coefficient $\widehat{f}(x)$ (defined later in this section), we use “mass” informally to refer to its magnitude.

In a graph $G=(V,E)$ , we use $N(v)$ to denote the neighborhood of a vertex $v\in V$ , defined as $\{u\in V:uv\in E\}$ .

3.2 Quantum Streaming Algorithms

As our lower bounds are based on reductions from communication complexity, they will be valid for the strong definition of quantum streaming, in which the algorithm maintains $\beta$ qubits and has a family of quantum channels $(\mathcal{A}_{\sigma})_{\sigma\in A}$ where $A$ is the alphabet of all possible updates that can appear in the stream. On seeing update $\sigma$ , the algorithm applies $\mathcal{A}_{\sigma}$ to its current state. We will therefore not need to concern ourselves with questions about ancillary qubits—for more discussion on the subtleties involved here, see section 2.4 of [NT17].

3.3 Quantum and Classical Max-Cut

We define Max-Cut and Quantum Max-Cut as follows.

Definition 3 (Max-Cut).

Given a graph $G=(V,E)$ with weights $w_{uv}\geq 0$ for $uv\in E$ , find the value of

\max_{f:V\rightarrow\{-1,1\}}\sum_{uv\in E}w_{uv}\frac{1-f(u)f(v)}{2}.

An unweighted instance is one where $w_{uv}=1$ for all $uv\in E$ .

In other words, we seek to assign each vertex $u$ to a side of a cut in a graph (a side designated by $f(u)=-1$ or $f(u)=1$ ) to maximize the weight of edges crossing the cut. Max-Cut is an instance of classical $2$ -CSP, and one may define a related instance of $2$ -LH that is closely related to the anti-ferromagnetic quantum Heisenberg model that has extensively been studied by physicists.

Definition 4 (Quantum Max-Cut).

Given a graph $G=(V,E)$ with weights $w_{uv}\geq 0$ for $uv\in E$ , find the maximum eigenvalue (or energy) of

Q=\sum_{uv\in E}w_{uv}\frac{I-X_{u}X_{v}-Y_{u}Y_{v}-Z_{u}Z_{v}}{4}.

An unweighted instance is one where $w_{uv}=1$ for all $uv\in E$ .

While Max-Cut is NP-hard, Quantum Max-Cut is QMA-hard [CM16, PM15]. Although Quantum Max-Cut is cast as a maximum-eigenvalue problem, we note that $Q\in\mathbb{C}^{2^{n}\times 2^{n}}$ is exponentially large in the number of vertices, corresponding to qubits, $n$ . We may also express Max-Cut in such a form, where we seek to find the maximum eigenvalue of

M=\sum_{uv\in E}w_{uv}\frac{I-Z_{u}Z_{v}}{2}.

To see that this is equivalent to Definition 3, consider $|\psi\rangle=|s_{1}\ldots s_{n}\rangle$ , with $s_{u}\in\{0,1\}$ . Then

$\displaystyle\langle\psi\|M\|\psi\rangle$	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-\langle\psi\|Z_{u}Z_{v}\|\psi\rangle}{2}$
	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-\langle s_{u}\|Z\|s_{u}\rangle\langle s_{v}\|Z\|s_{v}\rangle}{2}$
	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-(1-2s_{u})(1-2s_{v})}{2},$	(1)

and we may take $f(u)=1-2s_{u}$ to obtain the desired correspondence. So maximizing $\langle\psi|M|\psi\rangle$ over computational basis states $|\psi\rangle$ corresponds to Max-Cut; however, we observe that $M$ is a diagonal matrix in the computational basis, so that a basis state achieves the maximum eigenvalue. One way to see that Max-Cut and Quantum Max-Cut are related is that the diagonals of $M$ and $Q$ differ by a factor of two, and so Quantum Max-Cut captures Max-Cut if we restrict ourselves to classical solutions, i.e., basis states.

The quantum nature of Quantum Max-Cut may be better understood by observing that if we look at a graph consisting of a single unweighted edge, we have

Q=\frac{I-X\otimes X-Y\otimes Y-Z\otimes Z}{4}=|\psi^{-}\rangle\langle\psi^{-}|,

(2)

where $|\psi^{-}\rangle=(|01\rangle-|10\rangle)/\sqrt{2}$ is the maximally entangled singlet state. Thus the maximum energy of one is obtained by assigning the singlet to the two qubits. The diagonal of Q is $(|01\rangle\langle 01|+|10\rangle\langle 10|)/2$ , so a classical solution (basis state) can earn energy at most half by cutting the edge, which corresponds to “anti-aligning” or assigning different $\{-1,1\}$ -values to the endpoints, in the sense of Definition 3. A quantum solution can obtain an additional energy of half by taking an “anti-aligned” superposition of the two ways of cutting an edge.

Approximation algorithms

We say (following previous work on streaming Max-Cut that an algorithm $K$ -approximates a function $f(G)$ of a graph $G$ if it returns a value in $[f(G),Kf(G)]$ . In our space-limited setting, we only focus on approximating the objective value of a problem rather than also producing a corresponding feasible solution.

3.4 Fourier Analysis

For a function $f$ on the Boolean cube $\{0,1\}^{n}$ , the Fourier transform is given by

\widehat{f}(S)=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}f(x)(-1)^{x\cdot S}

where $S$ ranges over $\{0,1\}^{n}$ . Note that this is well-defined if $f$ takes values in a field $\mathbb{F}$ or vector space over $\mathbb{F}$ such that $\mathbb{Z}\subset\mathbb{F}$ . In particular, we will use it when $f$ takes values in $\mathbb{C}$ , in the space of square matrices over $\mathbb{C}$ , and in the space of linear operators on the space of square matrices over $\mathbb{C}$ . In the latter case, to reduce ambiguity about function arguments, we will write

\widehat{\mathcal{A}}_{S}=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\mathcal{A}_{x}(-1)^{S\cdot x}

when $\mathcal{A}_{x}$ is a family of such linear operators parametrized by $x\in\{0,1\}^{n}$ . As $\sum_{S\in\{0,1\}^{n}}(-1)^{S\cdot x}$ is $2^{n}$ when $x=0^{n}$ and $0$ otherwise, we can also write

f(x)=\sum_{S\in\{0,1\}^{n}}\widehat{f}(S)(-1)^{x\cdot S}

and so the Fourier transform is self-inverse up to a scale factor of $2^{-n}$ .

We will use the following hypercontractive inequality from [BARdW08], which takes the place of an inequality of [KKL88] that is typically used in applications of Fourier analysis to classical streaming.

Theorem 5 (Theorem 1 in [BARdW08]).

For every $f:\{0,1\}^{n}\rightarrow\mathbb{C}^{m\times m}$ and $1\leq p\leq 2$ ,

\sum_{S\subseteq[n]}(p-1)^{|S|}\lVert\widehat{f}(S)\rVert_{p}^{2}\leq\left\lparen\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\lVert f(x)\rVert_{p}^{p}\right\rparen^{1/p}

where $\lVert\cdot\rVert_{1}$ is the Schatten (nuclear) 1-norm.

We will also use Parseval’s identity.

Theorem 6 (Parseval).

For any function $f:\{0,1\}^{n}\rightarrow\mathbb{R}$ ,

\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}f(x)^{2}=\sum_{S\subseteq[n]}\widehat{f}(S)^{2}\text{.}

Useful Lemmas

The convolution lemmas and applications of hypercontractivity in this section will be extensions of standard results in Fourier analysis, but we will need slightly stronger or more general versions, so we prove them here.

We will need an extension of the convolution theorem for Fourier transforms to the matrix-valued case.

Lemma 7.

Let $f$ , $g$ be functions on $\{0,1\}^{n}$ such that the range of $f$ is contained in either $\mathbb{C}$ or $\mathbb{C}^{a\times b}$ , and the range of $g$ is contained in either $\mathbb{C}$ or $\mathbb{C}^{b\times c}$ , where $a,b,c\in\mathbb{N}$ . Then

\widehat{fg}(S)=\sum_{T\in\{0,1\}^{n}}\widehat{f}(T)\widehat{g}(T\oplus S)

for all $S\in\{0,1\}^{n}$ .

Proof.

	$\displaystyle\widehat{fg}(S)$	$\displaystyle=\operatorname*{\mathbb{E}}_{x}\left[f(x)g(x)(-1)^{S\cdot x}\right]$
		$\displaystyle=\operatorname*{\mathbb{E}}_{x}\left[\sum_{T\in\{0,1\}^{n}}\widehat{f}(T)(-1)^{T\cdot x}g(x)(-1)^{S\cdot x}\right]$
		$\displaystyle=\sum_{T\in\{0,1\}^{n}}\widehat{f}(T)\operatorname*{\mathbb{E}}_{x}\left[g(x)(-1)^{(T\oplus S)\cdot x}\right]$
		$\displaystyle=\sum_{T\in\{0,1\}^{n}}\widehat{f}(T)\widehat{g}(T\oplus S)$

∎

We will use Theorem 5 to derive two lemmas that bound the Fourier mass of functions that output density matrices (or, more generally, matrices with bounded trace norm), one for lower-degree coefficients and one for all coefficients. Both will be based on the following corollary of Theorem 5. Our proof is along the lines of that of Lemma 10 in [AD21], but in a slightly different setting.

Lemma 8.

For any $f:\{0,1\}^{n}\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ such that $\lVert f(x)\rVert_{1}\leq 1$ for all $x$ , for any $0\leq\delta\leq 1$ ,

\sum_{S\subseteq[n]}\delta^{|S|}\lVert\widehat{f}(S)\rVert_{1}^{2}\leq 2^{2\delta\beta}\text{.}

Proof.

Setting $p=1+\delta$ , we obtain

	$\displaystyle\sum_{S\subseteq[n]}\delta^{\|S\|}\lVert\widehat{f}(S)\rVert_{1+\delta}^{2}$	$\displaystyle\leq\left\lparen\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\lVert f(x)\rVert_{1+\delta}^{1+\delta}\right\rparen^{\frac{1}{1+\delta}}$
		$\displaystyle\leq\left\lparen\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}\lVert f(x)\rVert_{1}^{1+\delta}\right\rparen^{\frac{1}{1+\delta}}$
		$\displaystyle=1$

Next, note that for any $q$ , $2^{-\beta}\lVert\widehat{f}(S)\rVert_{q}^{q}$ can be viewed as $\operatorname*{\mathbb{E}}\left[|X|^{q}\right]$ , where $X$ is uniformly chosen from the singular values of $\widehat{f}(S)$ . So by Jensen’s inequality, we obtain

	$\displaystyle\lVert\widehat{f}(S)\rVert_{1+\delta}$	$\displaystyle=\left\lparen 2^{\beta}\operatorname*{\mathbb{E}}\left[\|X\|^{1+\delta}\right]\right\rparen^{\frac{1}{1+\delta}}$
		$\displaystyle\geq 2^{\frac{\beta}{1+\delta}}\operatorname*{\mathbb{E}}\left[\|X\|\right]$
		$\displaystyle=2^{\frac{\beta}{1+\delta}-\beta}\lVert\widehat{f}(S)\rVert_{1}$
		$\displaystyle\geq 2^{-\delta\beta}\lVert\widehat{f}(S)\rVert_{1}$

and so the corollary follows. ∎

We can now bound lower order terms of the Fourier expansion with a careful choice of $\delta$ .

Lemma 9.

For any $f:\{0,1\}^{n}\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ such that $\lVert f(x)\rVert_{1}\leq 1$ for all $x$ , and for any $k\in[\beta]$ ,

	$\displaystyle\sum_{\begin{subarray}{c}S\subseteq[n]:\\ \|S\|=k\end{subarray}}\lVert\widehat{f}(S)\rVert_{1}^{2}$	$\displaystyle\leq\left\lparen\frac{\operatorname*{O}\left\lparen\beta\right\rparen}{k}\right\rparen^{k}$
	$\displaystyle\sum_{\begin{subarray}{c}S\subseteq[n]:\\ \|S\|=k\end{subarray}}\lVert\widehat{f}(S)\rVert_{1}$	$\displaystyle\leq\left\lparen\frac{\operatorname*{O}\left\lparen\sqrt{\beta n}\right\rparen}{k}\right\rparen^{k}$

Proof.

Set $\delta=k/\beta$ in Lemma 8. Then we get

	$\displaystyle\sum_{\begin{subarray}{c}S\subseteq[n]:\\ \|S\|=k\end{subarray}}\lVert\widehat{f}(S)\rVert_{1}^{2}$	$\displaystyle\leq\left\lparen\frac{\beta}{k}\right\rparen^{k}\sum_{S\subseteq[n]}\left\lparen\frac{k}{\beta}\right\rparen^{\|S\|}\lVert\widehat{f}(S)\rVert_{1}^{2}$
		$\displaystyle\leq\left\lparen\frac{\beta}{k}\right\rparen^{k}2^{2k}$
		$\displaystyle=\left\lparen\frac{\operatorname*{O}\left\lparen\beta\right\rparen}{k}\right\rparen^{k}\text{.}$

The second line then follows from applying Cauchy-Schwarz, as for any non-negative-valued function $g$ on subsets of $[n]$ ,

\sum_{S\subseteq[n]}g(S)\leq\sqrt{\sum_{S\subseteq[n]}g(S)}\cdot\sqrt{\sum_{S\subseteq[n]}1}\leq\sqrt{\sum_{S\subseteq[n]}g(S)}\cdot\sqrt{\binom{n}{k}}

∎

We can also obtain a general bound with a less careful choice of $\delta$ .

Lemma 10.

For any $f:\{0,1\}^{n}\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ such that $\lVert f(x)\rVert_{1}\leq 1$ for all $x$ ,

	$\displaystyle\sum_{S\subseteq[n]}\lVert\widehat{f}(S)\rVert_{1}^{2}$	$\displaystyle\leq 2^{2\beta}$
	$\displaystyle\sum_{S\subseteq[n]}\lVert\widehat{f}(S)\rVert_{1}$	$\displaystyle\leq\left\lparen\frac{O(n)}{k}\right\rparen^{k/2}$

Proof.

Set $\delta=1$ in Lemma 8. The second line then follows from Cauchy-Schwarz as in the previous proof. ∎

For scalar-valued functions, a stronger version of the above (for the 2-norm) is given by Parseval’s identity⁹⁹9This can be proved for matrix-valued functions too, but we will not need it. (Theorem 6). This will allow us to characterize the Fourier coefficients of a function that checks whether its input satisfies a collection of linear constraints.

Lemma 11.

Let $M\in\{0,1\}^{k\times n}$ be a matrix over $\mathbb{Z}_{2}$ . Let $y\in\{0,1\}^{k}$ , and define $q:\{0,1\}^{n}\rightarrow\{0,1\}$ by

q(x)=\begin{cases}1&\mbox{if $Mx=y$}\\ 0&\mbox{otherwise.}\end{cases}

Then for every $s\in\{0,1\}^{k}$ ,

\widehat{q}(M^{\text{tr}}s)=\frac{|q^{-1}(1)|}{2^{n}}(-1)^{s\cdot y}

and every other Fourier coefficient of $q$ is $0$ .

Proof.

We first prove the part of this theorem pertaining to coefficients of the form $M^{\text{tr}}s$ . We have

	$\displaystyle\widehat{q}(M^{\text{tr}}s)$	$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}q(x)(-1)^{x\cdot(M^{\text{tr}}s)}$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}q(x)(-1)^{x^{\text{tr}}M^{\text{tr}}s}$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}q(x)(-1)^{y^{\text{tr}}s}$
		$\displaystyle=\frac{\|q^{-1}(1)\|}{2^{n}}(-1)^{s\cdot y}$

where the third line makes use of the fact that $q(x)=1$ iff $Mx=y$ . We will now use Parseval’s identity (Theorem 6) to show that every other coefficient must be 0. Now, if $Mx=y$ has no solutions $x$ , every coefficient will be $0$ and the theorem will hold trivially.

So suppose it has at least one solution. Then by the Rank-Nullity theorem and the fact we are working over $\mathbb{Z}_{2}$ , the number of solutions $|q^{-1}(1)|$ is $2^{n-r}$ , where $r$ is the dimension of the row space of $M$ . Furthermore, $2^{r}$ is the number of distinct coefficients $M^{t}s$ . So

	$\displaystyle\sum_{\begin{subarray}{c}z\in\{0,1\}^{n}:\\ \exists s\in\{0,1\}^{k},T=M^{\text{tr}}s\end{subarray}}\widehat{q}(z)^{2}$	$\displaystyle=2^{r}\frac{\|q^{-1}(1)\|^{2}}{2^{2n}}$
		$\displaystyle=\frac{\|q^{-1}(1)\|}{2^{n}}$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}q(x)^{2}$

which by Parseval is the sum of the square of every Fourier coefficient of $q$ , so as $q$ is real-valued its other Fourier coefficients must all be $0$ . ∎

As well as being used directly, this will also allow us to restrict the set of non-zero Fourier coefficients for any function that only depends on a linear function of its inputs.

Lemma 12.

Let $f$ be a real or complex (matrix or scalar)-valued function on $\{0,1\}^{n}$ , and let $M$ be a matrix over $\mathbb{Z}_{2}$ and $g$ another function such that $f(x)=g(Mx)$ for all $x\in\{0,1\}^{n}$ . Then for every $S\in\{0,1\}^{n}$ ,

\widehat{f}(S)=0

unless $S$ is $M^{\text{tr}}s$ for some $s\in\{0,1\}^{k}$ .

Proof.

We can write

f(x)=\sum_{y\in\{0,1\}^{k}}q_{y}(x)g(y)

where $q_{y}$ is the indicator function of $Mx=y$ , as in Lemma 11. So then, if $S$ is not $M^{\text{tr}}s$ for some $s\in\{0,1\}^{k}$ , $\widehat{q}_{y}(S)=0$ for all $y$ by Lemma 11 and so $\widehat{f}(S)=0$ . ∎

Finally, we will need a generalization of the convolution theorem to arbitrary linear operators. For a family of linear operators $(\mathcal{A}_{x})_{x\in\{0,1\}^{n}}$ we will write, by analogy to the Fourier transform,

\widehat{\mathcal{A}}_{s}=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}(-1)^{x\cdot s}\mathcal{A}_{x}\text{.}

Lemma 13.

Let $(\mathcal{A}_{x})_{x\in\{0,1\}^{n}}:\mathcal{L}_{1}\rightarrow\mathcal{L}_{2}$ be a family of linear operators, $f:\{0,1\}^{n}\rightarrow\mathcal{L}_{1}$ any function, and $g:\{0,1\}^{n}\rightarrow\mathcal{L}_{2}$ be given by

g(x)=\mathcal{A}_{x}f(x)\text{.}

Then

\widehat{g}(S)=\sum_{T\in\{0,1\}^{n}}\widehat{\mathcal{A}}_{T}\widehat{f}(S\oplus T)

for all $S\in\{0,1\}^{n}$ .

Proof.

	$\displaystyle\sum_{T\in\{0,1\}^{n}}\widehat{\mathcal{A}}_{T}\widehat{f}(S\oplus T)$	$\displaystyle=\frac{1}{2^{2n}}\sum_{T,x,y\in\{0,1\}^{n}}(-1)^{x\cdot T+y\cdot(S\oplus T)}\mathcal{A}_{x}f(y)$
		$\displaystyle=\frac{1}{2^{2n}}\sum_{T,x,y\in\{0,1\}^{n}}(-1)^{(x\oplus y)\cdot T+y\cdot S}\mathcal{A}_{x}f(y)$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x,y\in\{0,1\}^{n}}(-1)^{y\cdot S}\mathcal{A}_{x}f(y)\mathbb{I}(x=y)$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}(-1)^{x\cdot S}\mathcal{A}_{x}f(x)$
		$\displaystyle=\widehat{g}(S)$

∎

4 Communication Problem

We will use the Distributional Implicit Hidden Partition (DIHP) problem of [KK19].

In a DIHP $(n,\alpha,T)$ instance, for $n,T\in\mathbb{N}$ and $\alpha\in(0,1/2)$ such that $\alpha n\in\mathbb{N}$ , $T$ players indexed by $t\in[T]$ each receive the incidence matrix of a matching $M_{t}\in\{0,1\}^{\alpha n\times n}$ along with bit labels $w_{t}\in\{0,1\}^{\alpha n}$ .

The bit labels are private to their respective players, while each player $t$ knows $M_{s}$ for all $s\leq t$ . The players will communicate sequentially, from player $i$ to player $i+1$ , and the objective is for player $T$ to determine which of the following two distributions the inputs were drawn from:

YES: Draw $X\sim\mathcal{U}\left(\{0,1\}^{n}\right)$ . For each $t\in[T]$ , set $w_{t}=M_{t}X$ .
NO: For each $t\in[T]$ , draw $w_{t}\sim\mathcal{U}\left(\{0,1\}^{\alpha n}\right)$ .

5 Reducing Quantum and Classical Max-Cut to DIHP

In this section we will prove that any Max-Cut or QMC algorithm gives a DIHP protocol.

Theorem 14.

There exists a constant $C>0$ such that, for any $\varepsilon,\delta\in(0,1]$ and $n$ a multiple of $\lceil C/\varepsilon\rceil\cdot\lceil C^{3}/\varepsilon^{2}\rceil$ , the following holds: Suppose there is a streaming algorithm that returns a $(2-\varepsilon)$ -approximation to the Max-Cut size of an $n$ -vertex graph, or a $(2-\varepsilon)$ -approximation to its QMC value, in $S$ space with probability $1-\delta$ . Then DIHP $(n,1/\lceil C/\varepsilon\rceil,\lceil C^{3}/\varepsilon^{2}\rceil)$ has a protocol using $S+2\log n$ space that succeeds with probability $1-\delta-2^{-n}$ .

An immediate consequence of this is that, if we can show that solving DIHP $(n,\alpha,T)$ with probability $2/3$ requires $\operatorname*{\Omega}\left\lparen n\right\rparen$ space for all sufficiently small constants $\alpha$ , $T$ , then any algorithm giving a $(2-\varepsilon)$ -approximation to Max-Cut or QMC with $2/3$ probability for some constant $\varepsilon$ requires $\operatorname*{\Omega}\left\lparen n\right\rparen$ space.

Our reduction will be based on a graph encoding of DIHP. We can generate a graph from a DIHP instance by, for each matching $M_{t}$ and the $i^{\text{th}}$ edge in that matching, adding the edge to the graph iff $(w_{t})_{i}=1$ and the edge is not in $Ms$ for any $s\leq t$ . Note that as player $t$ knows $(M_{s})_{s\leq t}$ , they can construct this graph in the stream, as their own input and $(M_{s})_{s\leq t}$ will suffice to determine which edges to insert.

We write $\mathcal{G}^{Y}$ for the distribution on graphs generated thus conditioned on the DIHP instance being a YES case, and $\mathcal{G}^{N}$ for the distribution conditioned on a NO case. Let $\mathbf{G}$ denote a draw from one of these distributions, and $\mathbf{m}$ the number of edges in $\mathbf{G}$ . We will show, in both cases, a $(2-\varepsilon)$ -separation between the cut value of a draw from $\mathcal{G}^{Y}$ and $\mathcal{G}^{N}$ (as a fraction of $\mathbf{m}$ ), with high probability.

Lemma 15.

Let $\mathbf{G}$ be drawn from $\mathcal{G}^{Y}$ . Then the Max-Cut value of $\mathbf{G}$ is $\mathbf{m}$ and the QMC value is at least $\mathbf{m}/2$ .

Proof.

$\mathbf{G}$ will always be bipartite, as every edge will cross the bipartition given by $X$ . Therefore, the Max-Cut value will be $\mathbf{m}$ , and as any classical cut always earns at least half its value for QMC, the QMC value is at least $\mathbf{m}/2$ . ∎

To lower-bound the cut value, we will start with classical Max-Cut and then show that this implies the corresponding QMC bound.

Lemma 16.

Let $\mathbf{G}$ be drawn from $\mathcal{G}^{N}$ , and let $n\geq T$ . Then, with probability $1-e^{n(1-\operatorname*{\Omega}\left\lparen\alpha^{2}T\right\rparen)}$ , the Max-Cut value of $\mathbf{G}$ is less than $\mathbf{m}/(2-\operatorname*{O}\left\lparen 1/n+\alpha\right\rparen)$ .

Proof.

We start by proving that $\mathbf{m}$ is at least $\alpha Tn/8$ with high probability. Consider the probability that the $i^{\text{th}}$ edge of the $t^{\text{th}}$ matching is included in $\mathbf{G}$ , conditioned on on $(M_{s})_{s=1}^{t-1}$ and edges $1,\dots,i-1$ of $M_{t}$ . Then, the $i^{\text{th}}$ edge of $M_{t}$ is uniformly distributed among those edges not incident to any of the $i-1$ edges from $M_{t}$ conditioned on, and it will be included with probability $1/2$ if it is none of the edges in $(M_{s})_{s=1}^{t-1}$ . So it is included with probability at least

\frac{1}{2}\cdot\frac{\binom{n}{2}-(i-1)n-\alpha(t-1)n}{\binom{n}{2}}\leq\frac{n^{2}-n-2\alpha n^{2}-2\alpha nT}{2n^{2}}\leq\frac{1}{2}-1/n-\alpha-\alpha T/n\leq\frac{1}{2}-1/n-2\alpha

as $n\geq T$ . We may assume $1/n-2\alpha\leq 1/4$ , as otherwise the lemma follows trivially by choosing the constants in $\operatorname*{\Omega}\left\lparen\cdot\right\rparen$ and $\operatorname*{O}\left\lparen\cdot\right\rparen$ to be large enough. So the distribution of $\mathbf{m}$ stochastically dominates $\text{{Bi}}\left\lparen n\alpha T,1/4\right\rparen$ and so by the Chernoff bounds,

\mathbf{m}\geq\frac{\alpha nT}{8}

with probability at least

1-e^{-\operatorname*{\Omega}\left\lparen n\alpha T\right\rparen}\text{.}

Now, conditioning on any value of $\mathbf{m}\geq\frac{\alpha nT}{8}$ , consider any cut of the $[n]$ vertices. Now, consider the probability that any one of those $\mathbf{m}$ edges crosses the cut. For the $i^{\text{th}}$ edge of $M_{t}$ , even if we condition on the entire state of the game except for $(M_{t})_{i}$ , and additionally condition on the edge being included in the graph, its location is uniformly distributed over at least $\binom{n}{2}-2\alpha n^{2}-\alpha nT\geq n^{2}(1-1/n-5\alpha)/2$ possible locations (as the other edges from the same player’s $\alpha n$ -matching exclude no more than $2\alpha n^{2}$ possibilities, $2n$ for each of them, while the edges from other players’ matchings can exclude at most $1$ edge each, for a total of no more than $\alpha nT$ ). So the probability it will cross the cut is at most

\frac{1}{2(1-1/n-5\alpha)}

as at most $n^{2}/4$ of the possible locations for the edge will cross the cut. As this holds conditioning on any value of the rest of the input, it will also hold conditioning on any part of it, and so the number of edges crossing the cut is stochastically dominated by $\text{{Bi}}\left\lparen\mathbf{m},\frac{1}{2-1/n-5\alpha}\right\rparen$ , and so by again applying the Chernoff bounds and assuming that $1-1/n-6\alpha\geq 1/2$ (as otherwise the lemma again holds trivially), it is less than

\frac{\mathbf{m}}{2(1-1/n-6\alpha)}=\frac{\mathbf{m}}{2-1/n-5\alpha}+\operatorname*{\Omega}\left\lparen\alpha m\right\rparen

with probability at least

1-e^{-\operatorname*{\Omega}\left\lparen\alpha^{2}m\right\rparen}=1-e^{-\operatorname*{\Omega}\left\lparen\alpha^{3}n^{2}T\right\rparen}=1-e^{-\operatorname*{\Omega}\left\lparen\alpha^{2}nT\right\rparen}

conditioned on any $\mathbf{m}\geq n\alpha T/8$ and using the fact that $\alpha n\in\mathbb{N}$ . The lemma follows by taking a union bound over all $2^{n}$ possible cuts. ∎

This upper bounds the Max-Cut value of a NO instance. To extend this bound to Quantum Max-Cut, we use the fact that the natural semidefinite programming (SDP) relaxation of Max-Cut also gives an SDP relaxation of QMC, and this relaxation becomes tight as the max-cut value tends towards $1/2$ . Specifically, we use the vector program

\max_{f:V\rightarrow S^{n-1}}\sum_{uv\in E}-\langle f(u),f(v)\rangle

(3)

for a graph $G=(V,E)$ . The above vector program is equivalent to the standard Goemans-Williamson vector program

\max_{f:V\rightarrow S^{n-1}}\sum_{uv\in E}\frac{1-\langle f(u),f(v)\rangle}{2},

and may be solved as an SDP [GW95]. Thus if the optimal value of (3) is $K$ , the Max-Cut value of $G$ is at most $(\mathbf{m}+K)/2$ . A related vector program also gives an upper bound for QMC, so that its value is at most $(\mathbf{m}+3K)/4$ [GP19].

Conversely, we also have that if the Max-Cut value of $G$ is at most $n/2+\varepsilon$ , then $K=O(\varepsilon)$ , by [CW04]. This allows us to prove the following lemma:

Lemma 17.

Let $\mathbf{G}$ be drawn from $\mathcal{G}^{N}$ , and let $n\geq T$ . Then, with probability $1-e^{1-\operatorname*{O}\left\lparen\alpha^{2}nT\right\rparen}$ , the QMC value of $\mathbf{G}$ is less than $\mathbf{m}/(4-\operatorname*{O}\left\lparen 1/n+\alpha\right\rparen)$ .

Proof.

By Lemma 16, with this probability the Max-Cut value is at least $\mathbf{m}/(2-\operatorname*{O}\left\lparen 1/n+\alpha\right\rparen)$ , and so the SDP value is $\operatorname*{O}\left\lparen(1/n+\alpha)\mathbf{m}\right\rparen$ . This in turn implies that the QMC value is less than $\mathbf{m}/(4-\operatorname*{O}\left\lparen 1/n+\alpha\right\rparen)$ . ∎

We may now prove Theorem 14. See 14

Proof.

The protocol will be as follows:

•

Each player in turn gives every edge in their matching $M_{t}$ with bit label 1 to the algorithm, unless the edge appears in a previous player’s matching $M_{s}$ . They keep track of $\mathbf{m}$ , the number of edges input this way.
•

The final player uses the algorithm to approximate Max-Cut/QMC, returning YES if the returned value is at least $\mathbf{m}/(2-\varepsilon)$ (for Max-Cut) or at least $\mathbf{m}/(4-\varepsilon)$ (for QMC) and NO otherwise.

This will cost $S$ space to maintain the algorithm, and $2\log n$ space to maintain the counter.

The player’s input is now a draw from $\mathcal{G}^{Y}$ conditioned on the problem being in a YES instance, or from $\mathcal{G}^{N}$ conditioned on it being in a NO instance. Lemma 15 guarantees that a draw from $\mathcal{G}^{Y}$ will have Max-Cut value $\mathbf{m}$ and QMC value at least $\mathbf{m}/2$ .

Provided $C$ is chosen to be large enough, Lemmas 16 and 17 say that a draw from $\mathcal{G}^{N}$ will have Max-Cut value less than $\mathbf{m}/(2-\varepsilon)$ and QMC value less than $\mathbf{m}/(4-\varepsilon)$ with probability at least

1-2^{-n(1-\operatorname*{O}\left\lparen\lceil C/\varepsilon\rceil^{-2}\cdot\lceil C^{3}/\varepsilon^{2}\rceil\right\rparen)}=1-2^{-n}

and so as the algorithm succeeds with probability $1-\delta$ , the protocol will return the correct answer with probability at least $1-\delta-2^{-n}$ . ∎

6 Quantum Lower Bound for DIHP

6.1 Reduction to Fourier Analysis

Let $\beta$ be the number of qubits each player may send to the next. For simplicity we will think of the final player, $T$ , sending an $\beta$ -qubit message (consisting of either YES or NO with another $\beta-1$ bits fixed at $|0\rangle$ ). We will think of the first player as receiving a message from “player 0” that is fixed as $|0\rangle^{\beta}$ . We write $g_{t}:\{0,1\}^{\alpha Tn}:\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ for player $t$ ’s message as a function of the edge labels of the first $t$ matchings, and $f_{t}:\{0,1\}^{n}:\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ for $f_{t}(x)=g_{t}\left\lparen\left\lparen M_{s}x\right\rparen_{s=1}^{t}\right\rparen$ . Note that both functions depend on the first $t$ matchings $(M_{s})_{s=1}^{t}$ . Note also that as these messages are density matrices, they in particular have trace norm 1.

Now, we define

\phi_{t}=\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen},y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n\alpha(T-t)}\right\rparen}}\left[g_{T}\left\lparen(M_{s}x)_{s=1}^{t},y\right\rparen\right]

so for any given set of matchings $(M_{t})_{t=1}^{\text{tr}}$ , the total variation difference between the final player’s output in a YES and a NO case is given by

\lVert\phi_{T}-\phi_{0}\rVert_{1}.

Lemma 18.

\lVert\phi_{T}-\phi_{0}\rVert_{1}\leq\sum_{t=1}^{T-1}\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\left\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\right\rVert_{1}

Proof.

We first note that $\phi_{1}$ and $\phi_{0}$ are identical, as $M_{1}x$ is uniformly distributed. It will therefore suffice to prove that, for all $t\in[T-1]$ ,

\lVert\phi_{t+1}-\phi_{t}\rVert_{1}\leq\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\left\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\right\rVert_{1}

and the theorem will then follow by the triangle inequality. Now, we note that $\phi_{t+1}$ and $\phi_{t}$ are given by applying the same quantum channel to

\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen}}\left[g_{t+1}\left\lparen(M_{s}x)_{s=1}^{t+1}\right\rparen\right]

and

\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen},y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[g_{t+1}\left\lparen(M_{s}x)_{s=1}^{t},y\right\rparen\right]

respectively. Therefore, it will suffice to bound the trace norm of

\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen},y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[g_{t+1}\left\lparen(M_{s}x)_{s=1}^{t+1}\right\rparen-g_{t+1}\left\lparen(M_{s}x)_{s=1}^{t},y\right\rparen\right]

which we may rewrite as

\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen},y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\mathcal{A}_{M_{t+1}x}\left\lparen f_{t}(x)-\mathcal{A}_{y}\left\lparen f_{t}(x)\right\rparen\right\rparen\right]

where $\mathcal{A}_{y}$ is the quantum channel that player $t+1$ applies to the message received from player $t$ to generate the message sent onwards, if player $(t+1)$ ’s bit labels are $y$ (this channel may also depend on the matchings $(M_{s})_{s=1}^{t+1}$ ).

Writing $q_{y}$ for the indicator function on $y=M_{t+1}x$ , this in turn equals

\operatorname*{\mathbb{E}}_{x\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{n}\right\rparen},y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[2^{\alpha n}q_{y}(x)\mathcal{A}_{y}\left\lparen f_{t}(x)\right\rparen-\mathcal{A}_{y}\left\lparen f_{t}(x)\right\rparen\right]

which by the linearity of $\mathcal{A}_{y}$ can be rewritten as

\operatorname*{\mathbb{E}}_{y\sim\operatorname*{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\mathcal{A}_{y}\left\lparen 2^{\alpha n}\widehat{q_{y}f_{t}}(\emptyset)-\widehat{f}_{t}(\emptyset)\right\rparen\right]\text{.}

Now, by Lemmas 7 and 11,

	$\displaystyle\widehat{q_{y}f_{t}}(\emptyset)$	$\displaystyle=\sum_{S\in\{0,1\}^{n}}\widehat{q}_{y}(S)\widehat{f}_{t}(S)$
		$\displaystyle=\sum_{s\in\{0,1\}^{\alpha n}}\frac{\|q^{-1}_{y}(1)\|}{2^{n}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}$
		$\displaystyle=2^{-\alpha n}\sum_{s\in\{0,1\}^{\alpha n}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}$

as a $2^{-\alpha n}$ fraction of strings $x$ satisfy $M_{t+1}x=y$ . Putting this together, we get

	$\displaystyle\lVert\phi_{t+1}-\phi_{t}\rVert_{1}$	$\displaystyle\leq\left\lVert\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\mathcal{A}_{y}\left\lparen\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rparen\right]\right\rVert_{1}$
		$\displaystyle\leq\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\left\lVert\mathcal{A}_{y}\left\lparen\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rparen\right\rVert_{1}\right]$
		$\displaystyle=\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\left\lVert\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rVert_{1}\right]$
		$\displaystyle\leq\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\left\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\right\rVert_{1}$

completing the proof. ∎

6.2 Evolution of Fourier Coefficients

In this section we will show that, in expectation over the matchings, the even-degree Fourier coefficients of $f$ remain small enough in magnitude for Lemma 18 to give a useful bound.

Lemma 19.

There exists constants $C>1,D>1$ such that, for all $\ell\in[n/2]$ and $t\in[T]$ , if $\beta\leq n/D^{t}$ and $\alpha\leq 1/D$ ,

\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell\end{subarray}}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\lVert\widehat{f}_{t}(S)\rVert_{1}\right]\leq\left\lparen\frac{C^{t}n}{\ell}\cdot\max\left\{\frac{\beta}{\ell},1\right\}\right\rparen^{\ell/2}\text{.}

We write $\mathcal{A}_{x}^{t}$ for the quantum channel player $t$ applies to the state received from player $t-1$ , if the input player $t$ sees is $(M_{t},M_{t}x)$ (the family $(\mathcal{A}_{x})_{x\in\{0,1\}^{n}}$ will therefore depend on $M_{t}$ and nothing else). This means that $f_{t}(x)=\mathcal{A}_{x}^{t}f_{t-1}(x)$ and so we may apply Lemma 13 to get

\widehat{f}_{t}(S)=\sum_{U\in\{0,1\}^{n}}\widehat{\mathcal{A}}_{U}\widehat{f}_{t-1}(U\oplus S)

for all $S\in\{0,1\}^{n}$ . Now we will show that we only need to care about the coefficients $U$ that correspond to sets of edges in the matching $M_{t}$ .

Lemma 20.

For all $S\in\{0,1\}^{n}$ , $\widehat{\mathcal{A}}^{t}_{S}=0$ unless $S=M_{t}^{\text{tr}}s$ for some $s\in\{0,1\}^{\alpha n}$ .

Proof.

Suppose $S$ is not $M_{t}^{\text{tr}}s$ for any $s$ . Then for any $N\in\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ , define

h(x)=\mathcal{A}_{x}^{t}N\text{.}

As $\mathcal{A}^{t}_{x}$ depends only on $M_{t}x$ , we may apply Lemma 12 to get that $\widehat{h}(S)=0$ and therefore $\widehat{\mathcal{A}}^{t}_{S}N=0$ . As this applies for all $N$ , $\widehat{\mathcal{A}}^{t}_{S}=0$ . ∎

Applying this gives us

\widehat{f}_{t}(S)=\sum_{s\in\{0,1\}^{\alpha n}}\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}s}\widehat{f}_{t-1}(M^{\text{tr}}s\oplus S)

and summing over $S$ of weight $2\ell_{2}$ for any $\ell_{2}\in[n/2]$ , we get

	$\displaystyle\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell_{2}\end{subarray}}\lVert\widehat{f}_{t}(S)\rVert_{1}$	$\displaystyle\leq\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell_{2}\end{subarray}}\sum_{s\in\{0,1\}^{\alpha n}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}s}\widehat{f}_{t-1}(M^{\text{tr}}s\oplus S)\rVert_{1}$
		$\displaystyle=\sum_{S\in\{0,1\}^{n}}\sum_{\begin{subarray}{c}s\in\{0,1\}^{\alpha n}\\ \|M^{\text{tr}}s\oplus S\|=2\ell_{2}\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}s}\widehat{f}_{t-1}(S)\rVert_{1}\text{.}$

Now we can write the total mass on weight- $\ell_{2}$ coefficients of $\widehat{f}_{t}$ in terms of the contributions from each weight of coefficients of $\widehat{f}_{t-1}$ . Grouping $s\in\{0,1\}^{\alpha n}$ by the (always even) weight of $M^{\text{tr}}s\oplus S$ , we get,

\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell_{2}\end{subarray}}\lVert\widehat{f}_{t}(S)\rVert_{1}\leq\sum_{\ell_{1}=0}^{\lfloor n/2\rfloor}\tau_{t}(\ell_{1},\ell_{2})

where $\tau_{t}(\ell_{1},\ell_{2})$ is a bound on the amount of “mass transferred” between coefficients of weight $\ell_{1}$ and $\ell_{2}$ at step $t$ , given by

\tau_{t}(\ell_{1},\ell_{2})\coloneqq\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell_{1}\end{subarray}}\sum_{\begin{subarray}{c}s\in\{0,1\}^{\alpha n}\\ |M_{t}^{\text{tr}}s\oplus S|=2\ell_{2}\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M^{\text{tr}}s}\widehat{f}_{t-1}(S)\rVert_{1}\text{.}

We now split $s\in\{0,1\}^{\alpha n}$ into smaller groups, based on parameters $a,b,c\in\mathbb{N}$ , where $a$ is the number of edges from $M^{\text{tr}}s$ contained in $S$ , $b$ is the number with one endpoint in $S$ and $c$ is the number outside of $S$ (and so requiring that $|M^{\text{tr}}s\oplus S|=2\ell_{2}$ is equivalent to requiring that $\ell_{1}+c-a=\ell_{2}$ ). Let $I_{S}(y)$ be the indicator variable on $M_{t}^{\text{tr}}y$ being contained in $S$ , and $B_{S}(y)$ on the $i^{\text{th}}$ column of $M_{t}^{\text{tr}}$ having intersection exactly $1$ with $S$ whenever $y_{i}=1$ . Then we have

\tau_{t}(\ell_{1},\ell_{2})\leq\sum_{\begin{subarray}{c}a,b,c\in\mathbb{N}\\ \ell_{1}+c-a=\ell_{2}\end{subarray}}\tau(\ell_{1},a,b,c)

for

\tau_{t}(\ell_{1},a,b,c)\coloneqq\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell_{1}\end{subarray}}\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ |u|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ |v|=b\end{subarray}}I_{S}(u)B_{S}(v)\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ |w|=c\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)\rVert_{1}\text{.}

We are now ready to bound this “mass transfer” in terms of the of weight- $\ell_{1}$ coefficients of $\widehat{f}_{t-1}$ , in expectation over $M_{t}$ . This will hold for any values of $(M_{s})_{s=1}^{t-1}$ and $(x_{s})_{s=1}^{t}$ (note that $M_{t}$ is distributed independently of all these variables).

Lemma 21.

\operatorname*{\mathbb{E}}_{M_{t}}\left[\tau_{t}(\ell_{1},a,b,c)\right]\leq 2^{O(\ell_{1}+c)}\cdot(\alpha\cdot a/n)^{a}\cdot(n/c)^{c/2}\cdot\max\{(\beta/c)^{c/2},1\}\cdot\sum\limits_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell_{1}\end{subarray}}\lVert\widehat{f}_{t-1}(S)\rVert_{1}

Proof.

We start by bounding the innermost sum in $\tau_{t}$ , regardless of $u$ , $v$ , or $M_{t}$ . Let $\mathcal{B}^{t}_{y}$ denote the channel applied by player $t$ on seeing $y$ , so that $\mathcal{A}_{x}=\mathcal{B}_{M_{t}x}$ for all $x$ . For any fixed $S\in\{0,1\}^{n}$ , let $g:\{0,1\}^{\alpha n}\rightarrow\mathbb{C}^{2^{\beta}\times 2^{\beta}}$ be given by

g(y)=(-1)^{(u\oplus v)\cdot y}\mathcal{B}^{t}_{y}\widehat{f}_{t-1}(S)/\lVert\widehat{f}_{t-1}(S)\rVert_{1}\text{.}

Then for all $w\in\{0,1\}^{\alpha n}$ ,

	$\displaystyle\widehat{g}(w)$	$\displaystyle=\frac{1}{2^{\alpha n}}\sum_{y\in\{0,1\}^{\alpha n}}(-1)^{(u\oplus v\oplus w)\cdot y}\mathcal{B}^{t}_{y}\widehat{f}_{t-1}(S)/\lVert\widehat{f}_{t-1}(S)\rVert_{1}$
		$\displaystyle=\frac{1}{2^{\alpha n}}\sum_{y\in\{0,1\}^{\alpha n}}\frac{1}{2^{(1-\alpha)n}}\sum_{\begin{subarray}{c}x\in\{0,1\}^{n}\\ M_{t}x=y\end{subarray}}(-1)^{(u\oplus v\oplus w)\cdot M_{t}x}\mathcal{A}^{t}_{x}\widehat{f}_{t-1}(S)/\lVert\widehat{f}_{t-1}(S)\rVert_{1}$
		$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\{0,1\}^{n}}(-1)^{M_{t}^{\text{tr}}(u\oplus v\oplus w)\cdot x}\mathcal{A}^{t}_{x}\widehat{f}_{t-1}(S)/\lVert\widehat{f}_{t-1}(S)\rVert_{1}$
		$\displaystyle=\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)/\lVert\widehat{f}_{t-1}(S)\rVert_{1}$

and as applying a quantum channel can only shrink the trace norm, $\lVert g(x)\rVert_{1}\leq 1$ for all $x$ . So we may apply Lemmas 9 and 10 to obtain

	$\displaystyle\frac{1}{\lVert\widehat{f}_{t-1}(S)\rVert_{1}}\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ \|w\|=c\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)\rVert_{1}$	$\displaystyle=\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ \|w\|=c\end{subarray}}\lVert\widehat{g}(w)\rVert_{1}$
		$\displaystyle\leq\begin{cases}\left\lparen\frac{\sqrt{\operatorname{O}\left\lparen\beta\cdot\alpha n\right\rparen}}{c}\right\rparen^{c}&\mbox{$c\leq\beta$}\\ \left\lparen\frac{\operatorname{O}\left\lparen\alpha n\right\rparen}{c}\right\rparen^{c/2}&\mbox{$c>\beta$}\end{cases}$
		$\displaystyle\leq\begin{cases}2^{O(c)}\cdot c^{-c}\cdot\left\lparen\beta n\right\rparen^{c/2}&\mbox{$c\leq\beta$}\\ 2^{O(c)}\cdot c^{-c/2}\cdot n^{c/2}&\mbox{$c>\beta$}\end{cases}$
		$\displaystyle=2^{O(c)}\cdot(n/c)^{c/2}\cdot\max\{(\beta/c)^{c/2},1\}\text{.}$

With the inner sum bounded independently of $u$ , $v$ , and $M_{t}$ , it will then suffice to have a bound on

\operatorname*{\mathbb{E}}_{M_{t}}\left[\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ |u|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ |v|=b\end{subarray}}I_{S}(u)B_{S}(v)\right]

that holds for all $S$ .

First note that, there are $\binom{n}{2a}$ possible sets of vertices that can be matched by a size- $a$ subset of the matching $M_{t}$ , and $\binom{\ell_{1}}{2a}$ of them are contained in $S$ . So $I_{S}(u)$ is $1$ with probability $\binom{\ell_{1}}{2a}/\binom{n}{2a}$ .

Then, for any $u$ , conditioned on $I_{S}(u)=1$ , any $v$ not disjoint from $u$ has probability zero of having $B_{S}(v)=1$ , as no edge can have both endpoints in $S$ while also having exactly one endpoint. Meanwhile, for a size- $b$ disjoint $v$ , there are $2^{b}$ ways to choose one endpoint from each edge in the subset of $M_{t}$ indexed by $v$ , and then a $\binom{b}{\ell_{1}-a}/\binom{b}{n-a}$ probability that these endpoints are all in $S$ , so $\operatorname*{\mathbb{E}}\left[B_{S}(v)|I_{S}(u)=1\right]\leq 2^{b}\binom{b}{\ell_{1}-a}/\binom{b}{n-a}$ .

Therefore, and assuming $a,b\leq\ell_{1}$ and $\ell_{1}\leq n/2$ as otherwise the lemma would hold trivially,

	$\displaystyle\operatorname*{\mathbb{E}}_{M_{t}}\left[\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}I_{S}(u)B_{S}(v)\right]$	$\displaystyle\leq\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}\frac{\binom{\ell_{1}}{2a}}{\binom{n}{2a}}\cdot 2^{b}\cdot\frac{\binom{\ell_{1}-a}{b}}{\binom{n-a}{b}}$
		$\displaystyle\leq\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}\frac{2^{\ell_{1}}}{(n/2a)^{2a}}\cdot 2^{b}\cdot\frac{2^{\ell_{1}}}{((n-a)/b)^{b}}$
		$\displaystyle=\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}2^{O(\ell_{1})}\cdot a^{2a}b^{b}\cdot n^{-2a-b}$
		$\displaystyle=\binom{\alpha n}{a}\binom{\alpha n}{b}2^{O(\ell_{1})}\cdot a^{2a}b^{b}\cdot n^{-2a-b}$
		$\displaystyle\leq 2^{O(\ell_{1})}\cdot(\alpha\cdot a)^{a}\cdot n^{-a}$

and so the lemma follows. ∎

This will give us the inductive step we need to prove Lemma 19. We will need one further small lemma about integers for our proof.

Lemma 22.

For any $x,y,z\in\mathbb{N}_{>0}$ and $x\leq y+z$ ,

\frac{x^{x}}{y^{y}\cdot z^{z}}\leq\frac{2^{O(y+z)}}{(y+z-x)^{y+z-x}}

Proof.

Without loss of generality we will assume that $y\leq z$ .

	$\displaystyle\frac{x^{x}}{y^{y}\cdot z^{z}}$	$\displaystyle=2^{z}\frac{x^{x}}{y^{y}\cdot(2z)^{z}}$
		$\displaystyle\leq 2^{z}\frac{x^{x}}{(y+z)!}$
		$\displaystyle\leq 2^{O(y+z)}\frac{x^{x}}{(y+z)^{y+z}}$
		$\displaystyle\leq 2^{O(y+z)}\frac{1}{(y+z)^{y+z-x}}$
		$\displaystyle\leq\frac{2^{O(y+z)}}{(y+z-x)^{y+z-x}}$

∎

See 19

Proof.

We proceed by induction on $t$ , proving the slightly stronger version that includes $t=0$ . For $t=0$ , the result holds trivially because $f_{0}$ is constant and so $\lVert\widehat{f}_{0}(S)\rVert_{1}\leq 1$ if $S=\emptyset$ and $0$ otherwise.

Now, suppose there is a constant $C>0$ such that the lemma holds for $t-1$ . We will show that, if $C$ is chosen to be a large enough constant,

\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell\end{subarray}}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\lVert\widehat{f}_{t}(S)\rVert_{1}\right]\leq\left\lparen\frac{C^{t}n}{\ell}\cdot\max\left\{\frac{\beta}{\ell},1\right\}\right\rparen^{\ell/2}

for any given $\ell\in\mathbb{N}$ . We will split this into two parts, the low degree case ( $\ell\leq\beta$ ) and the high degree case ( $\ell>\beta$ ).

Low Degree Case

We have

\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ |S|=2\ell\end{subarray}}\lVert\widehat{f}_{t}(S)\rVert_{1}\leq\sum_{\ell^{\prime}=1}^{\beta}\tau_{t}(\ell^{\prime},\ell)+\sum_{\ell^{\prime}=\beta+1}^{\lfloor n/2\rfloor}\tau_{t}(\ell^{\prime},\ell)\text{.}

(4)

We will start by using the inductive hypothesis and Lemma 21 to bound the first sum in (4). Recall that we can bound $\tau_{t}(\ell^{\prime},\ell)$ as a sum over $\tau_{t}(\ell^{\prime},a,b,c)$ such that $\ell=\ell^{\prime}+c-a$ , and note that $\tau_{t}(\ell^{\prime},a,b,c)$ can only be non-zero 0 if $2a+b\leq 2\ell^{\prime}$ . For any $a,b,c$ satisfying both criteria (which as $\ell^{\prime}$ and $\ell$ are both at most $\beta$ , also imply $c<\beta$ , we have, by Lemma 21 and our inductive hypothesis,

	$\displaystyle\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{t}(\ell^{\prime},a,b,c)\right]$	$\displaystyle\leq 2^{O(\ell^{\prime}+c)}\cdot(a/n)^{a}\cdot(\sqrt{\beta n}/c)^{c}\cdot\left\lparen\frac{\sqrt{C^{t-1}\beta n}}{\ell^{\prime}}\right\rparen^{\ell^{\prime}}$
		$\displaystyle=2^{O(\ell^{\prime}+c)}\cdot\frac{a^{a}}{c^{c}{\ell^{\prime}}^{\ell^{\prime}}}\cdot(\beta n)^{(\ell^{\prime}+c-a)/2}\cdot(\beta/n)^{a/2}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}$
		$\displaystyle\leq 2^{O(\ell^{\prime}+c)}\cdot\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot(\beta/n)^{\max\{(\ell^{\prime}-\ell)/2,0\}}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}$

Now, using the fact that $a,b\leq\ell^{\prime}$ and so there are at most $\ell^{\prime}$ possibilities for each (and since $\ell-\ell^{\prime}=c-a$ , at most $\ell^{\prime}$ possibilities for $c$ ), we have

\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{t}(\ell^{\prime},\ell)\right]\leq 2^{O(\ell^{\prime}+c)}\cdot\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot(\beta/n)^{\max\{(\ell^{\prime}-\ell)/2,0\}}\cdot C^{\ell^{\prime}(t-1)/2}

and so, using the fact that $c=\ell-\ell^{\prime}+a\leq\ell$ ,

	$\displaystyle\sum_{\ell^{\prime}=1}^{\beta}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{1}(\ell^{\prime},\ell)\right]$	$\displaystyle=\sum_{\ell^{\prime}=1}^{\ell}\operatorname{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{1}(\ell^{\prime},\ell)\right]+\sum_{\ell^{\prime}=\ell+1}^{\beta}\operatorname{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{1}(\ell^{\prime},\ell)\right]$
		$\displaystyle\leq\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot\left\lparen\sum_{\ell^{\prime}=1}^{\ell}2^{O(\ell+\ell^{\prime})}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}+\sum_{\ell^{\prime}=\ell+1}^{\beta}2^{O(\ell+\ell^{\prime})}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}(\beta/n)^{\frac{(\ell^{\prime}-\ell)}{2}}\right\rparen$
		$\displaystyle\leq\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot\left\lparen\sum_{\ell^{\prime}=1}^{\ell}2^{O(\ell+\ell^{\prime})}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}+\sum_{\ell^{\prime}=\ell+1}^{\beta}2^{O(\ell+\ell^{\prime})}\cdot C^{\frac{\ell^{\prime}(t-1)}{2}}D^{\frac{-t(\ell^{\prime}-\ell)}{2}}\right\rparen$
		$\displaystyle\leq\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot 2^{O(\ell)}\cdot C^{\frac{\ell(t-1)}{2}}$
		$\displaystyle\leq\frac{1}{2}\left\lparen\frac{\sqrt{C^{t}\beta n}}{\ell}\right\rparen^{\ell}$

provided that $C$ is chosen to be a sufficiently large constant and $D$ is chosen to be sufficiently larger than $C$ .

Now, we use Lemma 21, the inductive hypothesis, and Lemma 10 to bound the second sum in (4). Putting these together, we have for $a,b,c$ such that $\ell=\ell^{\prime}+c-a$ , $\ell^{\prime}>\beta\geq\ell$ , and $\tau_{t}(\ell^{\prime},a,b,c)$ is non-zero (which in particular implies $2a+b\leq 2\ell^{\prime}$ ),

	$\displaystyle\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau_{t}(\ell^{\prime},a,b,c)\right]$	$\displaystyle\leq 2^{O(\ell^{\prime}+c)}\cdot(\alpha\cdot a/n)^{a}\cdot(n/c)^{c/2}\cdot\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell^{\prime}\end{subarray}}\lVert\widehat{f}_{t-1}(S)\rVert_{1}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{a}\cdot(a/n)^{a/2}\cdot(n/c)^{c/2}\cdot\min\left\{\left\lparen\frac{C^{t-1}n}{\ell^{\prime}}\right\rparen^{\ell^{\prime}/2},\left\lparen\frac{n}{\ell^{\prime}}\right\rparen^{\ell^{\prime}}\right\}\cdot(a/n)^{a/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{\ell^{\prime}-\ell}\cdot(a/n)^{a/2}\cdot(n/c)^{c/2}\cdot\left\lparen\frac{C^{t-1}n}{\ell^{\prime}}\right\rparen^{\ell/2}\cdot\left\lparen\frac{n}{\ell^{\prime}}\right\rparen^{(\ell^{\prime}-\ell)}\cdot(a/n)^{(\ell^{\prime}-\ell)/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{\ell^{\prime}-\ell}\cdot\frac{a^{a/2}}{c^{c/2}{\ell^{\prime}}^{\ell^{\prime}/2}}\cdot n^{(\ell^{\prime}+c-a)/2}\cdot C^{(t-1)\ell/2}\cdot(a/\ell^{\prime})^{(\ell^{\prime}-\ell)/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{\ell^{\prime}-\ell}\cdot\left\lparen\frac{n}{\ell^{\prime}+c-a}\right\rparen^{(\ell^{\prime}+c-a)/2}\cdot C^{(t-1)\ell/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{\ell^{\prime}-\ell}\cdot\left\lparen\frac{n}{\ell}\right\rparen^{\ell/2}\cdot C^{(t-1)\ell/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot\alpha^{\ell^{\prime}-\ell}\cdot\left\lparen\frac{\sqrt{\beta n}}{\ell}\right\rparen^{\ell}\cdot C^{(t-1)\ell/2}$
		$\displaystyle\leq 2^{O(\ell^{\prime})}\cdot(1/D)^{\ell^{\prime}-\ell}\cdot\left\lparen\frac{\sqrt{C^{t-1}\beta n}}{\ell}\right\rparen^{\ell}\text{.}$

making use of Lemma 22. Again using the fact that there are no more than $\ell^{\prime}$ choices for each of $a,b,c$ that give non-zero $\tau_{t}$ , we get

\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau(\ell^{\prime},\ell)\right]\leq 2^{O(\ell^{\prime})}\cdot(1/D)^{\ell^{\prime}-\ell}\cdot\left\lparen\frac{\sqrt{C^{t-1}\beta n}}{\ell}\right\rparen^{\ell}

and so summing over all $\ell^{\prime}>m$ gives us

\sum_{\ell^{\prime}=\beta+1}^{\lfloor n/2\rfloor}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau(\ell^{\prime},\ell)\right]\leq\frac{1}{2}\left\lparen\frac{\sqrt{C^{t}\beta n}}{\ell}\right\rparen^{\ell}

provided $C$ and $D$ are chosen to be sufficiently large. Adding our bounds on the first and second sum in (4) completes the inductive step for $\ell\leq\beta$ .

High Degree Case

For this case we will use the fact that $(x/y)^{y}\leq\binom{x}{y}\leq 2^{x}$ when $y\in[x]$ . Let $\ell\in(\beta,n/2]\cap\mathbb{Z})$ . For any $\ell^{\prime},a,b,c$ such that $a,b\leq\ell^{\prime}$ and $\ell^{\prime}+c-a=\ell$ we get, by Lemma 21, our inductive hypothesis, and Lemma 10,

	$\displaystyle\tau_{t}(\ell^{\prime},a,b,c)$	$\displaystyle\leq 2^{O(\ell^{\prime}+c)}\cdot(\alpha\cdot a/n)^{a}\cdot(n/c)^{c/2}\cdot\max\{(\beta/c)^{c/2},1\}$
		$\displaystyle\phantom{\leq}\cdot\min\left\{\left\lparen\frac{C^{t-1}n}{\ell^{\prime}}\cdot\max\left\{\frac{\beta}{\ell^{\prime}},1\right\}\right\rparen^{\ell^{\prime}/2},\left\lparen\frac{n}{\ell^{\prime}}\right\rparen^{\ell^{\prime}}\right\}$
		$\displaystyle\leq 2^{O(\ell^{\prime}+c)}\cdot\alpha^{a}\cdot(a/n)^{a/2}\cdot(n/c)^{c/2}\cdot 2^{\beta}$
		$\displaystyle\phantom{\leq}\cdot\left\lparen\frac{C^{t-1}n}{\ell^{\prime}}\right\rparen^{\min\{\ell/2,\ell^{\prime}/2\}}\cdot 2^{\ell^{\prime}}\cdot(n/\ell^{\prime})^{\max\{(\ell^{\prime}-\ell),0\}}\cdot(a/n)^{a/2}$
		$\displaystyle\leq 2^{O(\ell+\ell^{\prime})}\cdot\frac{a^{a/2}{\ell^{\prime}}^{\ell^{\prime}/2}}{c^{c/2}}\cdot n^{(\ell^{\prime}-a+c)/2}\cdot C^{(t-1)\ell/2}\cdot\alpha^{\max\{\ell^{\prime}-\ell,0\}}$
		$\displaystyle\phantom{\leq}\cdot C^{(t-1)\min\left\{(\ell^{\prime}-\ell)/2,0\right\}}\cdot(n/\ell^{\prime})^{\max\left\{(\ell-\ell^{\prime})/2,0\right\}}\cdot(a/n)^{\max\left\{(\ell-\ell^{\prime})/2,0\right\}}$
		$\displaystyle\leq 2^{O(\ell+\ell^{\prime})}\cdot\left\lparen\frac{C^{t-1}n}{\ell}\right\rparen^{\ell/2}\cdot\max\left\{1/C,1/D\right\}^{\|\ell^{\prime}-\ell\|}$

and once again we use the fact that there are no more than $\ell^{\prime}$ choices for $a,b,c$ to obtain

\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau(\ell^{\prime},\ell)\right]\leq 2^{O(\ell^{\prime}+c)}\cdot\left\lparen\frac{C^{t-1}n}{\ell}\right\rparen^{\ell/2}\cdot\max\left\{1/C,1/D\right\}^{|\ell^{\prime}-\ell|}\text{.}

We may then sum over all $\ell^{\prime}$ to obtain

\sum_{\ell^{\prime}=\beta+1}^{\lfloor n/2\rfloor}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\tau(\ell^{\prime},\ell)\right]\leq\left\lparen\frac{\sqrt{C^{t}n}}{\ell}\right\rparen^{\ell/2}

provided $C$ and $D$ are chosen to be sufficiently large. ∎

6.3 Completing the Bound

Theorem 23.

For any constant $\delta>0$ , there exists a constant $C>0$ such that, for any $\alpha<1/C$ , $n,T\in\mathbb{N}$ , $\text{\bf DIHP}(n,\alpha,T)$ requires at least $n/C^{T}$ communication to solve with probability $1/2+\delta$ in the one-way quantum communication model.

Proof.

Let $C^{\prime},D^{\prime}$ correspond to the constants $C,D$ from Lemma 19. We will choose $C$ to be larger than $\max{(C^{\prime})^{6},D^{\prime},2}$ . Consider a protocol using $\beta\leq n/C^{T}$ communication (with $C$ to be specified later). We will start by assuming that $\beta\geq\log T$ , then show how to remove this assumption. Using the notation of Section 6.1, the probability that the final player outputs the correct answer for any given matchings $(M_{t})_{t=1}^{T}$ is bounded by

\frac{1}{2}+\frac{1}{2}\lVert\phi_{T}-\phi_{0}\rVert_{1}

and so (applying Lemmas 18 and 19, and Lemma 10 for higher-degree Fourier terms), the success probability is bounded by $1/2$ plus

	$\displaystyle\operatorname*{\mathbb{E}}_{(M_{t})_{t=1}^{T}}\left[\lVert\phi_{T}-\phi_{0}\rVert_{1}\right]$	$\displaystyle\leq\sum_{t=1}^{T-1}\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\operatorname*{\mathbb{E}}_{(M_{t})_{t=1}^{T}}\left[\left\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\right\rVert_{1}\right]$
		$\displaystyle=\sum_{t=1}^{T-1}\sum_{\ell=1}^{\alpha n}\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell\end{subarray}}\sum_{s\in\{0,1\}^{\alpha n}}\operatorname{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\lVert\widehat{f}(S)\rVert_{1}\cdot\operatorname{\mathbb{P}}_{M_{t+1}}\left[M_{t+1}^{\text{tr}}s=S\right]\right]$
		$\displaystyle\leq\sum_{t=1}^{T-1}\sum_{\ell=1}^{\alpha n}\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell\end{subarray}}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\lVert\widehat{f}(S)\rVert_{1}\right]\cdot\binom{\alpha n}{\ell}/\binom{n}{2\ell}$
		$\displaystyle\leq\sum_{t=1}^{T-1}\sum_{\ell=1}^{\alpha n}\left\lparen\frac{O(\alpha\cdot\ell)}{n}\right\rparen^{\ell}\sum_{\begin{subarray}{c}S\in\{0,1\}^{n}\\ \|S\|=2\ell\end{subarray}}\operatorname*{\mathbb{E}}_{(M_{s})_{s=1}^{t}}\left[\lVert\widehat{f}(S)\rVert_{1}\right]$
		$\displaystyle\leq\sum_{t=1}^{T-1}\left\lparen\sum_{\ell=1}^{\beta}\left\lparen\frac{O(\ell)}{n}\right\rparen^{\ell}\cdot\left\lparen\frac{C^{t/3}\sqrt{\beta n}}{\ell}\right\rparen^{\ell}+\sum_{\ell=\beta+1}^{\alpha n}\left\lparen\frac{O(\alpha\cdot\ell)}{n}\right\rparen^{\ell}\cdot\left\lparen\frac{\operatorname*{O}\left\lparen n\right\rparen}{\ell}\right\rparen^{\ell}\right\rparen$
		$\displaystyle\leq\sum_{t=1}^{T-1}\left\lparen\sum_{\ell=1}^{\beta}C^{-t\ell/6}+\sum_{\ell=\beta+1}^{\alpha n}(1/C)^{\ell}\right\rparen$
		$\displaystyle=\operatorname*{O}\left\lparen C^{-1/6}+T/C^{\beta}\right\rparen$
		$\displaystyle<\delta$

provided $C$ is chosen to be large enough. So the protocol cannot achieve $2/3$ success probability.

We now have a constant $C>0$ such that no protocol using $\beta\in(\log T,n/C^{T})$ communication can succeed. We will now show that no protocol using $\beta<n/(2C)^{T}$ communicating can succeed, which will suffice to prove the lemma. If $(\log T,n/C^{T})$ contains at least one integer $\beta^{\prime}$ , we can “pad” any $\beta<\log T$ qubit protocol to use $\beta^{\prime}$ qubits by adding $\beta^{\prime}-\beta$ qubits that are never used, without affecting the success probability. So as no $\beta^{\prime}$ qubit protocol can succeed, neither can any $\beta$ qubit protocol. Conversely, if the interval $(\log T,n/C^{T})$ contains no integers, $n/C^{T}<\log T+1$ , and so $n/(2C)^{T}<(\log T+1)/C^{T}<1$ as $C>2$ . So then the result holds trivially. ∎

Our main result now follows as a corollary. See 1

Proof.

By setting the constant in $\operatorname*{O}\left\lparen\cdot\right\rparen$ large enough that $2^{\operatorname*{O}\left\lparen 1/\varepsilon^{2}\right\rparen}\geq\lceil C^{\prime}/\varepsilon\rceil\cdot\lceil{C^{\prime}}^{3}/\varepsilon^{2}\rceil$ , we may reduce to DIHP via Theorem 14 and then apply Theorem 23 to conclude that any algorithm for $(2-\varepsilon)$ -approximating Max-Cut with probability $2/3$ requires at least $n/C^{\lceil{C^{\prime}}^{3}/\varepsilon^{2}\rceil}-2\log n$ bits, where we use $C^{\prime}$ for the constant $C$ in Theorem 14. Then there is a constant $D$ such that $n/D^{1/\varepsilon^{2}}<\max\left\{n/C^{\lceil{C^{\prime}}^{3}/\varepsilon^{2}\rceil}-2\log n,1\right\}$ , and so the result follows (as clearly any algorithm must use at least 1 qubit of storage). ∎

7 Space Complexity Upper Bounds for Quantum Max-Cut

Unlike in the classical case, where the trivial algorithm offers the best result possible in $\operatorname*{o}\left\lparen n\right\rparen$ space, the trivial algorithm for Quantum Max-Cut offers only a 4-approximation. In this section we show how to attain a $(2+\varepsilon)$ -approximation for unweighted Quantum Max-Cut and a $(5/2+\varepsilon)$ -approximation to weighted Quantum Max-Cut. We will show this by proving (in Lemmas 27 and 28) that these approximations can be derived from two quantities, the sum of the edge weights, and the sum of the max-weight edge at each vertex (in the unweighted case, the number of edges and non-isolated vertices, respectively).

The first of these quantities can be calculated exactly with a single counter—we show that the second can also be calculated in small space (Lemma 29), giving us as a consequence the following result. See 2

7.1 Approximating Quantum Max-Cut from Simple Graph Parameters

For a (weighted) graph $G=(V,E,w)$ we will write $m=\sum_{e\in E}w_{e}$ and $W=\sum_{u\in V}\max_{v\in N(u)}w_{uv}$ . In the unweighted case we will use the same definitions with every weight considered to be $1$ (so $m$ is the number of edges and $W$ the number of non-isolated vertices). We have the following upper bound for the Quantum Max-Cut of a graph.

Lemma 24 (Lemma 5, [AGM20]).

The Quantum Max-Cut value of $G$ is at most $m/2+W/4$ .

Remark 25.

The Quantum Max-Cut terms employed in [AGM20] are twice the ones we employ. Their Lemma 5 gives a bound for stars, and taking half the sum of this bound applied to the star around each vertex in $G$ yields the bound stated in the above lemma.

We will use this to obtain approximations to Quantum Max-Cut in terms of $m$ and $W$ . We will use the following facts about Quantum Max-Cut:

Lemma 26 (Quantum Max-Cut facts).

(a)

The Quantum Max-Cut value is at least half the classical max-cut value.
(b)

For any given edge $uv$ , we can earn energy $w_{uv}$ for it by assigning a singlet to its two vertices.
(c)

For a vertex with $d$ incident weight-1 edges, there is an assignment to it and its neighbors that earns total energy $\frac{d+1}{2}$ .
(d)

For any set of assignments to disjoint subgraphs $(H_{i})_{i\in I}$ , there is an assignment that preserves the energy of these assignments on their subgraphs while earning $1/4$ for every edge between a pair of subgraphs.

Proof.

For the following we let $Q_{uv}=(I-X_{u}X_{v}-Y_{u}Y_{v}-Z_{u}Z_{v})/4$ be a Quantum Max-Cut term acting on qubits $u$ and $v$ .

For a, if $|\psi\rangle=|s_{1}\ldots s_{n}\rangle$ , with $s_{u}\in\{0,1\}$ , then $\langle\psi|X_{u}X_{v}|\psi\rangle=\langle\psi|Y_{u}Y_{v}|\psi\rangle=0$ . Thus, following Equation (1),

\langle\psi|Q_{uv}|\psi\rangle=\frac{1-\langle\psi|Z_{u}Z_{v}|\psi\rangle}{4}=\frac{1}{2}\frac{1-(1-2s_{u})(1-2s_{v})}{2},

and if we interpret each $s_{u}$ as assigning $u$ to a side of a cut, then $\langle\psi|Q_{uv}|\psi\rangle$ is precisely half the value this cut earns on edge $uv$ .

For b we recall from Equation (2) that assigning a singlet¹⁰¹⁰10Technically we mean taking the $n$ -qubit state $\rho=Q_{uv}$ . to qubits $u$ and $v$ earns a maximum weighted energy of $w_{uv}$ .

For c, consider a vertex $u$ with $d$ incident edges, $\{uv\}_{v\in N}$ ( $i$ may have additional incident edges to vertices outside $N$ ). The proof of Lemma 5 in [AGM20] demonstrates that there is a quantum state $|\psi\rangle$ on $u\cup N$ such that $\langle\psi|\sum_{uv:v\in N}Q_{uv}|\psi\rangle=\frac{d+1}{2}$ . (Moreover, $\psi$ resides in the single-excitation subspace, $\text{span}\{|10\ldots 0\rangle,|01\ldots 0\rangle,\ldots,|00\ldots 1\rangle\}$ , and its coefficients in this subspace correspond to the coefficients of a maximum eigenvector of a $(d+1)\times(d+1)$ matrix, a graph Laplacian in fact.)

For d suppose we have assigned mixed states $\rho_{i}$ to disjoint subgraphs $H_{i}$ of our graph $G$ . In other words we assign the state $\rho=\otimes_{i}\rho_{i}$ to the qubits in $\cup_{i}H_{i}$ . We show that we may replace each $\rho_{i}$ with a state $\rho^{\prime}_{i}$ so that

(i)

$\rho^{\prime}_{i}$ contains no 1-local terms, and
(ii)

$\operatorname{Tr}[Q_{uv}\rho^{\prime}_{i}]=\operatorname{Tr}[Q_{uv}\rho_{i}]$ , for all $uv\in H_{i}$ .

Property (ii) ensures that the energy earned on edges within each $H_{i}$ are preserved. Property (i) implies that $\rho^{\prime}=\otimes_{i}\rho^{\prime}_{i}$ cannot contain any terms of the form $X_{u}X_{v}$ , $Y_{u}Y_{v}$ , or $Z_{u}Z_{v}$ for $u$ and $v$ in different $H_{i}$ ; hence, $\operatorname{Tr}[X_{u}X_{v}\rho^{\prime}]=\operatorname{Tr}[Y_{u}Y_{v}\rho^{\prime}]=\operatorname{Tr}[Z_{u}Z_{v}\rho^{\prime}]=0$ , and consequently $\operatorname{Tr}[Q_{uv}\rho^{\prime}]=1/4$ , for such $uv$ .

We construct $\rho^{\prime}_{i}$ from $\rho_{i}$ as follows. For a Hermitian operator $A$ , let $A^{-}$ be the operator obtained from $A$ by negating the coefficient of each odd-local term. We have $\operatorname{Tr}[\rho^{-}_{i}]=\operatorname{Tr}[\rho_{i}]=1$ , and we next show that $\rho^{-}_{i}\succeq 0$ since $\rho_{i}\succeq 0$ . Proceed by contrapositive and assume there is a $|\psi\rangle$ such that $\langle\psi|\rho^{-}_{i}|\psi\rangle<0$ . Set $P=|\psi\rangle\langle\psi|$ . We have

\operatorname{Tr}[\rho_{i}(P^{-})^{2}]=\operatorname{Tr}[\rho_{i}(P^{2})^{-}]=\operatorname{Tr}[\rho^{-}_{i}P^{2}]=\operatorname{Tr}[\rho^{-}_{i}P]=\langle\psi|\rho^{-}|\psi\rangle<0,

(5)

where the third equality follows because $P^{2}=P$ . The first two equalities hold because for Hermitian $A$ and $B$ acting on $n$ qubits,

•

$(A^{-})^{2}=(A^{2})^{-}$ : the only terms appearing in $B^{2}$ are those of the form $ab$ where $a,b$ are commuting terms of $B$ ; consequently $ab$ is odd-local if and only if exactly one of $a,b$ is.
•

$\operatorname{Tr}[AB^{-}]=\operatorname{Tr}[A^{-}B]$ : we have $\frac{1}{2^{n}}\operatorname{Tr}[AB^{-}]=\langle u,v^{-}\rangle=\langle u^{-},v\rangle=\frac{1}{2^{n}}\operatorname{Tr}[A^{-}B]$ , where $u,v$ are Bloch vectors¹¹¹¹11A Bloch vector of a Hermitian operator $A$ acting on $n$ qubits is the vector of the $4^{n}$ real coefficients of the Pauli terms of $A$ . of $A,B$ respectively, and $w^{-}$ negates the entries of $w$ corresponding to odd-local terms.

Since $\rho\succeq 0$ , $\operatorname{Tr}[\rho_{i}A^{2}]$ must be nonnegative for any Hermitian $A$ , and Equation (5) demonstrates that $\rho^{-}_{i}\succeq 0$ . Finally we get the desired state $\rho^{\prime}_{i}=(\rho_{i}+\rho^{-}_{i})/2$ , which has no odd-local terms, and the even-local terms remain the same as $\rho_{i}$ . The latter ensures that Property (ii) holds. ∎

Lemma 27.

The Quantum Max-Cut value of $G$ is at least $m/5+W/10$ .

Proof.

We use a modified version of an argument in the proof of Theorem 3 in [AGM20]. If $m\geq 2W$ , we can use the fact that the Quantum Max-Cut value is at least $m/4$ (by a and considering a random assignment) to get a lower bound of

m/4=m/5+m/20\geq m/5+W/10\text{.}

So suppose $m<2W$ . Now order the edges of $G$ by weight (with arbitrary but consistent tiebreakers when edges have the same weight). Let $H$ be the subgraph formed by choosing the maximum weight edge incident to each vertex. Note that $H$ is a forest, as for any cycle, each edge must have greater weight than at least one of the next or the previous edge in the cycle. But maintaining this through the cycle would eventually require that the first edge in the cycle had greater weight than itself.

Let $\mathcal{M}$ denote all the edges in $H$ that were “chosen” by (had the greatest weight of any edge incident to) both their endpoints. This is then a matching. Let $\mathcal{F}$ denote the rest of $H$ . Let $M$ and $F$ denote the total weight of each, so $2M+F=W$ . As $\mathcal{M}$ is a matching we may use b and d to choose an assignment to it that earns $w_{e}$ on each edge $e$ in the matching, plus $w_{e}/4$ for every other edge $e$ in the graph, for a total Quantum Max-Cut value of $M+m/4$ .

As $\mathcal{F}\cup\mathcal{M}$ is a forest, and therefore has a value $F+M$ classical cut, a tells us that its Quantum Max-Cut value is at least $F/2+M/2$ . So substituting in $F=W-2M$ , the Quantum Max-Cut value is at least

\max\{M+m/4,W/2-M/2\}

and so as $M\geq 0$ , and $W/2>m/4$ , this is minimized when $M+m/4=W/2-M/2$ , so when $3M/2=W/2-m/4$ . We can therefore conclude that the Quantum Max-Cut value is at least

	$\displaystyle m/12+W/3$	$\displaystyle=m/5-7m/60+W/3$
		$\displaystyle\geq m/5-7W/30+W/3$
		$\displaystyle=m/5+W/10$

completing the proof. ∎

Lemma 28.

Let $G$ be unweighted. Then the Quantum Max-Cut value of $G$ is at least $m/4+W/8$ .

Proof.

We will use a technique inspired by a method of [GY21] for proving lower bounds for weighted Max-Cut. In particular we take advantage of the fact that, for any vertex in a DFS, the subtrees rooted at its children will be disconnected from each other. (If there were an edge between $u$ and $v$ in two different subtrees, and $u$ was explored before $v$ , then edge $uv$ would have been followed by the DFS, and $v$ would have been included in the same subtree as $u$ .)

We will assume $G$ is connected—by property d, the Quantum Max-Cut value of a graph is at least the sum of the Quantum Max-Cut value of its components, so as the value of $m$ and $W$ for $G$ is the sum of the values for its components, this will suffice to prove the result for general $G$ .

Now let $T$ be a DFS tree for $G$ , started from an arbitrary vertex $v$ . $T$ will contain $W-1$ edges (as $W$ is just the vertex count for an unweighted graph). For all $i\in\mathbb{N}$ , let $T_{i}$ denote the set of edges in $T$ between a vertex at depth $i$ in the tree and one at depth $i+1$ , so $T=\bigcup_{i=1}^{W}T_{i}$ . Note that each $T_{i}$ is a union of stars (formed by the depth- $i$ vertices and their children), and because of the aforementioned disconnected subtree property, there are no edges in $G\setminus T_{i}$ connecting two vertices in $T_{i}$ .

Let $T^{\prime}$ be whichever of $\bigcup_{i=1}^{W}T_{2i}$ and $\bigcup_{i=1}^{W}T_{2i+1}$ has the most edges, so $|T^{\prime}|=(W-1)/2$ . Now, $T^{\prime}$ is a union of stars, and by property c, for each star with degree $d$ there is an assignment earning $\frac{d+1}{2}$ on it. Now, as these stars are disjoint, and the edges in $G\setminus T^{\prime}$ are all between stars, property d implies that there is an assignment to $G$ earning

	$\displaystyle\frac{\|T^{\prime}\|+1}{2}+\frac{m-\|T^{\prime}\|}{4}$	$\displaystyle=\frac{m}{4}+\frac{\|T^{\prime}\|}{8}+\frac{1}{2}$
		$\displaystyle\geq\frac{m}{4}+\frac{W-1}{8}+\frac{1}{2}$
		$\displaystyle>\frac{m}{4}+\frac{W}{8}$

∎

energy, completing the proof.

7.2 Estimating $W$ in the Stream

In this section we give a simple classical algorithm for estimating $W$ in logarithmic space.

Lemma 29.

Let $G$ be a weighted graph on $n$ vertices with weights that are multiples of $1/\operatorname{poly}(n)$ . Then for any $(\varepsilon,\delta)\in(0,1)$ there is a streaming algorithm that returns an $\varepsilon m$ -additive approximation to $W$ using $\operatorname*{O}\left\lparen\frac{1}{\varepsilon^{2}}\log\frac{1}{\delta}\log n\right\rparen$ space.

We will use Algorithm 1 to obtain an estimator for $W$ which we will then amplify.

Algorithm 1 A log-space algorithm for estimating

W

in the stream.

Sample

e

from

E

with probability proportional to

w_{e}

Sample

v

from the two endpoints of

e

, each with probability

1/2

e

is the last edge to arrive incident to

v

in the stream then

\mathbf{X}\leftarrow 1

else if

w_{e}<w_{f}

for some

f

incident to

v

that arrives after

e

in the stream then

\mathbf{X}\leftarrow 0

else

w^{\prime}\leftarrow

the greatest weight of any edge to arrive incident to

v

after

e

in the stream.

\mathbf{X}\leftarrow 1-w^{\prime}/w_{e}

end if

return

\mathbf{X}

Lemma 30.

Algorithm 1 can be implemented in the stream using $O(\log n)$ space.

Proof.

By using reservoir sampling, we can sample $e$ while only storing one edge (and its weight) at a time. Then, whenever we have a candidate sample for $e$ , we can track the highest-weight edge to arrive incident to $v$ that arrives after $e$ (throwing it out if our reservoir sampling procedure gives us a new candidate for $e$ ). This requires tracking just two edges, each requiring $O(\log n)$ space to store with its weight. ∎

Lemma 31.

\operatorname*{\mathbb{E}}\left[\mathbf{X}\right]=W/2m

Proof.

Let $\mathcal{S}_{e,u}$ denote the event that the edge $e$ and its endpoint $u$ are sampled, so $\operatorname*{\mathbb{P}}\left[\mathcal{S}_{e,u}\right]=w_{e}/2m$ . We can then write

\operatorname*{\mathbb{E}}\left[\mathbf{X}\right]=\sum_{u\in V}\sum_{v\in N(u)}\operatorname*{\mathbb{E}}\left[\mathbf{X}\middle|\mathcal{S}_{uv,u}\right]w_{uv}/2m

Now, for any vertex $v\in N(u)$ such that $w_{uv}<w_{f}$ for some $f$ that appears after $uv$ in the stream and is incident to $u$ , $\operatorname*{\mathbb{E}}\left[\mathbf{X}\middle|\mathcal{S}_{uv,u}\right]=0$ .

So let $N^{\prime}$ be the set of vertices $v\in N(u)$ such that $w_{uv}\geq w_{f}$ for all $f$ incident to $u$ that appear after $uv$ in the stream. Order $N^{\prime}$ as $(v_{i})_{i=1}^{k}$ in the order they arrive in the stream, and let $w_{i}$ denote the weight of $uv_{i}$ . Then, $\operatorname*{\mathbb{E}}\left[\mathbf{X}\middle|\mathcal{S}_{uv_{k},u}\right]=1$ , while for each $i\in[k-1]$ , $\operatorname*{\mathbb{E}}\left[\mathbf{X}\middle|\mathcal{S}_{uv_{i},u}\right]=1-w_{i+1}/w_{i}$ . Therefore,

\sum_{i=1}^{k}\operatorname*{\mathbb{E}}\left[\mathbf{X}\middle|\mathcal{S}_{uv_{i},u}\right]w_{i}/2m=w_{k}/2m+\sum_{i=1}^{k-1}(w_{i}-w_{i+1})/2m=w_{1}/2m=\max_{v\in N(u)}w_{uv}/2m

and so by summing over all $u\in V$ the result follows. ∎

Lemma 32.

\operatorname{\text{{Var}}}(\mathbf{X})\leq 1

Proof.

This follows immediately from the fact that $\mathbf{X}$ takes values in the range $[0,1]$ . ∎

We can now prove Lemma 29. See 29

Proof.

We have that $2m\mathbf{X}$ is an unbiased estimator for $W$ , with variance $4m^{2}$ . By repeating Algorithm 1 $\operatorname*{\Theta}\left\lparen\varepsilon^{2}\right\rparen$ times in parallel and averaging these estimators, we may obtain a variance $\varepsilon^{2}m^{2}/9$ estimator, and so by Chebyshev, with probability $2/3$ it will be within $\varepsilon m$ of $W$ . We may then repeat this entire process $\operatorname*{\Theta}\left\lparen\log 1/\delta\right\rparen$ times and take the median to obtain a $\varepsilon m$ -additive estimator of $W$ with probability $1-\delta$ .

Each iteration can be performed in parallel and requires $\operatorname*{O}\left\lparen\log n\right\rparen$ space, completing the proof. ∎

7.3 Completing the Upper Bound

Theorem 2 now follows immediately. See 2

Proof.

By the lemmas of 7, it is sufficient to estimate $2m+W$ to $(1\pm\varepsilon^{\prime})$ -multiplicative accuracy for a sufficiently small $\varepsilon^{\prime}=\operatorname*{\Theta}\left\lparen\varepsilon\right\rparen$ . $m$ can be calculated exactly with a single counter in $bO{\log n}$ space. By Lemma 29, we can calculate $W$ to $\varepsilon^{\prime}m$ -additive accuracy in $\operatorname*{O}\left\lparen\frac{1}{\varepsilon^{2}}\log\frac{1}{\delta}\right\rparen$ space. ∎

Acknowledgements

The authors were supported by the Laboratory Directed Research and Development program at Sandia National Laboratories, a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525. Also supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research in Quantum Computing program.

References

[AAV13] Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum pcp conjecture. Acm sigact news, 44(2):47–79, 2013.
[AD21] Srinivasan Arunachalam and João F Doriguello. Matrix hypercontractivity, streaming algorithms and ldcs: the large alphabet case. arXiv preprint arXiv:2109.02600, 2021.
[AG09] K. Ahn and S. Guha. Graph sparsification in the semi-streaming model. ICALP, pages 328–338, 2009.
[AGM20] Anurag Anshu, David Gosset, and Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
[AGMKS21] Anurag Anshu, David Gosset, Karen J Morenz Korol, and Mehdi Soleimanifar. Improved approximation algorithms for bounded-degree local hamiltonians. arXiv preprint arXiv:2105.01193, 2021.
[AZ19] Dorit Aharonov and Leo Zhou. Hamiltonian sparsification and gap-simulation. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 2:1–2:21, 2019.
[BARdW08] Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008.
[BGKT19] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3):032203, 2019.
[BH16] Fernando GSL Brandão and Aram W Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47–80, 2016.
[BMO⁺15] Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 110–123, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[CGS⁺22] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. Linear space streaming lower bounds for approximating CSPs. In STOC’22, 2022.
[CM16] Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268–316, 2016.
[CW04] M. Charikar and A. Wirth. Maximizing quadratic programs: extending grothendieck’s inequality. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54–60, 2004.
[DM20] João F. Doriguello and Ashley Montanaro. Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158, pages 1:1–1:16, 2020.
[FGG14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.
[GK12] Sevag Gharibian and Julia Kempe. Approximation algorithms for qma-complete problems. SIAM Journal on Computing, 41(4):1028–1050, 2012.
[GKK⁺07] 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 Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pages 516–525, New York, NY, USA, 2007. ACM.
[GKK⁺08] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2008.
[GP19] Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[GW95] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, nov 1995.
[GY21] Gregory Gutin and Anders Yeo. Lower bounds for maximum weighted cut. arXiv preprint arXiv:2104.05536, 2021.
[HLP20] Sean Hallgren, Eunou Lee, and Ojas Parekh. An approximation algorithm for the MAX-2-Local Hamiltonian problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
[HM19] Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1–69:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[HNP⁺21] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique games hardness of quantum max-cut, and a vector-valued borell’s inequality. arXiv preprint arXiv:2111.01254, 2021.
[JN14] Rahul Jain and Ashwin Nayak. The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited. IEEE Transactions on Information Theory, 60(10):6646–6668, October 2014.
[Kal22] John Kallaugher. A quantum advantage for a natural streaming problem. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 897–908, 2022.
[KK15] Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 367–376, 2015.
[KK19] Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating max-cut. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 277–288, New York, NY, USA, 2019. Association for Computing Machinery.
[KKL88] J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, SFCS ’88, pages 68–80, Washington, DC, USA, 1988. IEEE Computer Society.
[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput., 37(1):319–357, 2007.
[KKP18] John Kallaugher, Michael Kapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 556–567. IEEE, 2018.
[KKS15] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
[KKSV17] Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. $(1+{\Omega}(1))$ -Approximation to MAX-CUT requires linear space. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1703–1722, 2017.
[Kla07] Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM Journal on Computing, 37(1):20–46, 2007.
[LG06] François Le Gall. Exponential separation of quantum and classical online space complexity. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA ’06, pages 67–73, New York, NY, USA, July 2006. Association for Computing Machinery.
[Mon16] Ashley Montanaro. The quantum complexity of approximating the frequency moments. Quantum Info. Comput., 16(13–14):1169–1190, October 2016.
[NT17] Ashwin Nayak and Dave Touchette. Augmented index and quantum streaming algorithms for dyck(2). In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[NV18] Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games pcp for qma. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 731–742. IEEE, 2018.
[O’D14] Ryan O’Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.
[PM15] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2d lattices. arXiv preprint arXiv:1506.04014, 2015.
[PT21a] Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:20, 2021.
[PT21b] Ojas Parekh and Kevin Thompson. Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems. In 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 74:1–74:18, 2021.
[Raz95] Ran Raz. Fourier analysis for probabilistic communication complexity. Computational Complexity, 5(3):205–221, 1995.
[SW12] Yaoyun Shi and Xiaodi Wu. Limits of quantum one-way communication by matrix hypercontractive inequality. 2012.
[VY11] Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other problems. SODA, pages 11–25, 2011.

$\displaystyle\langle\psi\|M\|\psi\rangle$	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-\langle\psi\|Z_{u}Z_{v}\|\psi\rangle}{2}$
	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-\langle s_{u}\|Z\|s_{u}\rangle\langle s_{v}\|Z\|s_{v}\rangle}{2}$
	$\displaystyle=\sum_{uv\in E}w_{uv}\frac{1-(1-2s_{u})(1-2s_{v})}{2},$	(1)

	$\displaystyle\lVert\phi_{t+1}-\phi_{t}\rVert_{1}$	$\displaystyle\leq\left\lVert\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\mathcal{A}_{y}\left\lparen\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rparen\right]\right\rVert_{1}$
		$\displaystyle\leq\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\left\lVert\mathcal{A}_{y}\left\lparen\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rparen\right\rVert_{1}\right]$
		$\displaystyle=\operatorname{\mathbb{E}}_{y\sim\operatorname{\mathcal{U}\left\lparen\{0,1\}^{\alpha n}\right\rparen}}\left[\left\lVert\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)(-1)^{s\cdot y}\right\rVert_{1}\right]$
		$\displaystyle\leq\sum_{s\in\{0,1\}^{\alpha n}\setminus\{\emptyset\}}\left\lVert\widehat{f}_{t}(M_{t+1}^{\text{tr}}s)\right\rVert_{1}$

	$\displaystyle\frac{1}{\lVert\widehat{f}_{t-1}(S)\rVert_{1}}\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ \|w\|=c\end{subarray}}\lVert\widehat{\mathcal{A}}^{t}_{M_{t}^{\text{tr}}(u\oplus v\oplus w)}\widehat{f}_{t-1}(S)\rVert_{1}$	$\displaystyle=\sum_{\begin{subarray}{c}w\in\{0,1\}^{\alpha n}\\ \|w\|=c\end{subarray}}\lVert\widehat{g}(w)\rVert_{1}$
		$\displaystyle\leq\begin{cases}\left\lparen\frac{\sqrt{\operatorname{O}\left\lparen\beta\cdot\alpha n\right\rparen}}{c}\right\rparen^{c}&\mbox{$c\leq\beta$}\\ \left\lparen\frac{\operatorname{O}\left\lparen\alpha n\right\rparen}{c}\right\rparen^{c/2}&\mbox{$c>\beta$}\end{cases}$
		$\displaystyle\leq\begin{cases}2^{O(c)}\cdot c^{-c}\cdot\left\lparen\beta n\right\rparen^{c/2}&\mbox{$c\leq\beta$}\\ 2^{O(c)}\cdot c^{-c/2}\cdot n^{c/2}&\mbox{$c>\beta$}\end{cases}$
		$\displaystyle=2^{O(c)}\cdot(n/c)^{c/2}\cdot\max\{(\beta/c)^{c/2},1\}\text{.}$

	$\displaystyle\operatorname*{\mathbb{E}}_{M_{t}}\left[\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}I_{S}(u)B_{S}(v)\right]$	$\displaystyle\leq\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}\frac{\binom{\ell_{1}}{2a}}{\binom{n}{2a}}\cdot 2^{b}\cdot\frac{\binom{\ell_{1}-a}{b}}{\binom{n-a}{b}}$
		$\displaystyle\leq\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}\frac{2^{\ell_{1}}}{(n/2a)^{2a}}\cdot 2^{b}\cdot\frac{2^{\ell_{1}}}{((n-a)/b)^{b}}$
		$\displaystyle=\sum_{\begin{subarray}{c}u\in\{0,1\}^{\alpha n}\\ \|u\|=a\end{subarray}}\sum_{\begin{subarray}{c}v\in\{0,1\}^{\alpha n}\\ \|v\|=b\end{subarray}}2^{O(\ell_{1})}\cdot a^{2a}b^{b}\cdot n^{-2a-b}$
		$\displaystyle=\binom{\alpha n}{a}\binom{\alpha n}{b}2^{O(\ell_{1})}\cdot a^{2a}b^{b}\cdot n^{-2a-b}$
		$\displaystyle\leq 2^{O(\ell_{1})}\cdot(\alpha\cdot a)^{a}\cdot n^{-a}$

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut

Abstract

1 Introduction

1.1 Our Contributions

Theorem 1.

Theorem 2.

Fourier Analysis for Quantum Channels

1.2 Other Related Work

Streaming bounds for Max-Cut

Quantum streaming algorithms

Approximating Quantum Max-Cut

2 Proof Overview

2.1 Lower Bounds

2.1.1 The Distributed Implicit Hidden Partition Problem

Reduction to Classical Max-Cut

Extending the Reduction to Quantum Max-Cut

2.1.2 Quantum Communication Lower Bounds for DIHP

Reduction to Boolean Fourier Analysis

The Evolution of Fourier Coefficients

2.2 Space Upper Bounds for Quantum Max-Cut

Upper Bounding the QMC Value

Lower Bounding the QMC Value in General Weighted Graphs

Lower Bounding the QMC Value in Unweighted Graphs

Estimating WW in the Stream

3 Preliminaries

3.1 Notation

3.2 Quantum Streaming Algorithms

3.3 Quantum and Classical Max-Cut

Definition 3 (Max-Cut).

Definition 4 (Quantum Max-Cut).

Approximation algorithms

3.4 Fourier Analysis

Theorem 5 (Theorem 1 in [BARdW08]).

Theorem 6 (Parseval).

Useful Lemmas

Lemma 7.

Proof.

Lemma 8.

Proof.

Lemma 9.

Proof.

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

Lemma 13.

Proof.

4 Communication Problem

5 Reducing Quantum and Classical Max-Cut to DIHP

Theorem 14.

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

Proof.

6 Quantum Lower Bound for DIHP

6.1 Reduction to Fourier Analysis

Lemma 18.

Proof.

6.2 Evolution of Fourier Coefficients

Lemma 19.

Lemma 20.

Proof.

Lemma 21.

Proof.

Lemma 22.

Proof.

Proof.

Low Degree Case

High Degree Case

6.3 Completing the Bound

Theorem 23.

Proof.

Proof.

7 Space Complexity Upper Bounds for Quantum Max-Cut

7.1 Approximating Quantum Max-Cut from Simple Graph Parameters

The Quantum and Classical Streaming Complexity of
Quantum and Classical Max-Cut

Estimating $W$ in the Stream

7.2 Estimating $W$ in the Stream