Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting
For streaming algorithm designers, it demonstrates an exponential quantum advantage over classical algorithms for approximating Max-kSAT, a fundamental NP-hard problem.
The paper presents a quantum streaming algorithm for Max-kSAT that uses polylog(n) space and achieves a 0.7172-approximation, exponentially better than the classical lower bound of Ω(√n) space for approximation above 0.7071. It also gives a quantum streaming algorithm for Max-2OR with 0.7425-approximation, completing the classification of quantum advantages for Boolean Max-2CSPs.
In this paper, we give a one-pass quantum streaming algorithm for Max-$k$SAT that uses $\operatorname{polylog}(n)$ space and achieves a $0.7172$-approximation on instances with $n$ variables. In contrast, prior work by Chou, Golovnev, and Velusamy (FOCS 2020) implies that achieving an approximation ratio better than $\sqrt{2}/2 \approx 0.7071$ for Max-$k$SAT requires $Ω(\sqrt{n})$ space for any classical streaming algorithm. Therefore, it yields an exponential quantum space advantage for Max-$k$SAT in the streaming setting. We further give a one-pass quantum streaming algorithm for Max-2OR that uses $\operatorname{polylog}(n)$ space and achieves a $0.7425$-approximation on instances with $n$ variables. Combining with the known results, it gives a complete classification of quantum space advantages for all Boolean Max-2CSPs.