Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2206.00213

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

John Kallaugher, Ojas Parekh

Published Jun 1, 2022• 0 citations
arXivHTMLPDF

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 \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.

DOI
10.48550/arxiv.2206.00213

Related papers

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•1 citation

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, 2023•2 citations

A Quantum Advantage for a Natural Streaming Problem.

John Kallaugher

Data streaming, in which a large dataset is received as a stream of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

•Jan 1, 2022•1 citation

Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

Minbo Gao, Chenghua Liu, Guangxu Yang +1 more

We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight $Ω(N^{1/4})$ one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $Ω(N^{1/12})$ due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of $Ω\left(\sqrt{Δ_V}\right)$ for graphs with $m$ edges, $Θ(m)$ triangles, and constant $Δ_E$, where $Δ_V$ and $Δ_E$ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that $1\le Δ_V\le m^{2/3}$. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.

quant-pharXiv:2607.08517•Jul 10, 2026•0 citations

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Huang, Jeremy Ahrens, Young Kun Ko, Chunhao Wang

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap Max-Cut, problem) to γ-CVP_p for γ = O(1) and finite p ≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP_p are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^{0.78n}-time or 2^{0.3n}-time algorithm would improve upon state-of-the-art algorithms such as Williams' 2004 algorithm [TCS 2005] or Arora, Barak, and Steurer’s 2010 algorithm [JACM 2015]. This provides evidence that γ-CVP_p for γ = O(1) requires exponential time, improving upon the previous exponential lower-bound for γ-CVP₂ with γ < 3 by Bennett, Golovnev, and Stephens-Davidowitz [FOCS 2017]. (ii) A new almost 2^{(1/2 + ε/4ς + o(1)) n}-time classical algorithm and a new almost 2^{(1/3 + ε/6ς + o(1)) n}-time quantum algorithm for (1-ε, 1-ς)-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steurer [JACM 2015], as well as the algorithm of Williams [TCS 2005], and the algorithm of Manurangsi and Trevisan [APPROX 2018] when c₀ ε < ς < c₁ ε for constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^{δ n}-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ > 0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result complements the no-go results of Aggarwal and Kumar [FOCS 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).

arXiv:2411.04124•Leibniz international proceedings in informatics•Nov 6, 2024•0 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906•Oct 12, 2026•0 citations
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−ε)(2 - \varepsilon)(2−ε)-approximation requires Ω(n)Ω(n)Ω(n) space (a 222-approximation is trivial with O(log⁡n)\textrm{O}(\log n)O(logn) space). We generalize both of these qualifiers, demonstrating Ω(n)Ω(n)Ω(n) space lower bounds for (2−ε)(2 - \varepsilon)(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 444-approximation, we show tightness with an algorithm that returns a (2+ε)(2 + \varepsilon)(2+ε)-approximation to the Quantum Max-Cut value of a graph in O(log⁡n)\textrm{O}(\log n)O(logn) space. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using o(n)\textrm{o}(n)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.
Data streaming, in which a large dataset is received as a stream of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N1/4)Ω(N^{1/4})Ω(N1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N1/12)Ω(N^{1/12})Ω(N1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(ΔV)Ω\left(\sqrt{Δ_V}\right)Ω(ΔV​​) for graphs with mmm edges, Θ(m)Θ(m)Θ(m) triangles, and constant ΔEΔ_EΔE​, where ΔVΔ_VΔV​ and ΔEΔ_EΔE​ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ΔV≤m2/31\le Δ_V\le m^{2/3}1≤ΔV​≤m2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap Max-Cut, problem) to γ-CVP_p for γ = O(1) and finite p ≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP_p are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^{0.78n}-time or 2^{0.3n}-time algorithm would improve upon state-of-the-art algorithms such as Williams' 2004 algorithm [TCS 2005] or Arora, Barak, and Steurer’s 2010 algorithm [JACM 2015]. This provides evidence that γ-CVP_p for γ = O(1) requires exponential time, improving upon the previous exponential lower-bound for γ-CVP₂ with γ < 3 by Bennett, Golovnev, and Stephens-Davidowitz [FOCS 2017]. (ii) A new almost 2^{(1/2 + ε/4ς + o(1)) n}-time classical algorithm and a new almost 2^{(1/3 + ε/6ς + o(1)) n}-time quantum algorithm for (1-ε, 1-ς)-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steurer [JACM 2015], as well as the algorithm of Williams [TCS 2005], and the algorithm of Manurangsi and Trevisan [APPROX 2018] when c₀ ε < ς < c₁ ε for constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^{δ n}-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ > 0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result complements the no-go results of Aggarwal and Kumar [FOCS 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-Graph Collision, the reduction yields a lower bound matching our upper bound above.