Velusamy

Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting

Announce Type: new Abstract: 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 $\Omega(\sqrt{n})$ space for any classical streaming algorithm. Therefore, it yields an...