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

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

The Asymptotics of Quantum Max-Flow Min-Cut

Matthew B. Hastings

arXiv:1603.03717Communications in Mathematical PhysicsNov 16, 201611 citations

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

John Kallaugher, Ojas Parekh

Algorithms for graphs received one edge at a time.

Feb 1, 20232 citations

Max-flow min-cut theorem in quantum computing

Nongmeikapam Brajabidhu Singh, Arnab Roy, Anish Kumar Saha

Physica A Statistical Mechanics and its ApplicationsJul 24, 20242 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.