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

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 \emph{classical} problem, showing that any $(2 - \varepsilon)$ -approximation requires $Ω(n)$ space (a $2$ -approximation is trivial with $\textrm{O}(\log n)$ space). We generalize both of these qualifiers, demonstrating $Ω(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.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 \emph{classical} problem, showing that any $(2 - \varepsilon)$-approximation requires $Ω(n)$ space (a $2$-approximation is trivial with $\textrm{O}(\log n)$ space). We generalize both of these qualifiers, demonstrating $Ω(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.

arXiv:2206.00213Jun 1, 20220 citations

Quantum Time Complexity and Algorithms for Pattern Matching on Labeled Graphs

Parisa Darbari, Daniel Gibney, Sharma V. Thankachan

Lecture notes in computer scienceJan 1, 20222 citations

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

John Kallaugher, Ojas Parekh

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 – ε)-approximation requires Ω(n) space (a 2-approximation is trivial with O(log n) space). We generalize both of these qualifiers, demonstrating Ω(n) space lower bounds for (2 – ε)-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 + ε)-approximation to the QUANTUM MAX-CUT value of a graph in O(log n) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using 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.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 – ε)-approximation requires Ω(n) space (a 2-approximation is trivial with O(log n) space). We generalize both of these qualifiers, demonstrating Ω(n) space lower bounds for (2 – ε)-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 + ε)-approximation to the QUANTUM MAX-CUT value of a graph in O(log n) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using 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.

Annual Symposium on Foundations of Computer ScienceOct 1, 20221 citation

Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

Stuart Wayland, Zackary Jorquera, Alexandra Kolla

Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin- $\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$ . The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$ . We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.

quant-pharXiv:2610.03670Oct 5, 20260 citations

Approximate Quantum 3-Colorings of Graphs and the Quantum Max 3-Cut Problem

Samuel J. Harris

arXiv:2412.19405Communications in Mathematical PhysicsApr 4, 20260 citations

(2 - \varepsilon)

-approximation requires

Ω(n)

space (a

2

-approximation is trivial with

\textrm{O}(\log n)

space). We generalize both of these qualifiers, demonstrating

Ω(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.

\tfrac12

antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes

G(n,n,p)

with high probability for every fixed

p>0

. The algorithm estimates the ground energy and any ground state edge correlation to additive error

\varepsilon

in time polynomial in

n

and

1/\varepsilon

. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.