Exponential Quantum Space Advantage for Approximating Max-kSAT in the Streaming Setting

In this paper, we give a one-pass quantum streaming algorithm for Max-kSAT that uses operatornamepolylog(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 √2/2 ≈ 0.7071 for Max-kSAT requires Omega(√n) space for any classical streaming algorithm. Therefore, it yields an exponential quantum space advantage for Max-kSAT in the streaming setting. We further give a one-pass quantum streaming algorithm for Max-2OR that uses operatornamepolylog(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.