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

arXiv: https://arxiv.org/abs/2606.05366 · HTML: https://mlsanity.com/paper/2606.05366/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory](https://mlsanity.com/paper/2608.11066/) (2026)

## Abstract (arXiv)

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.