Id: arxiv/2606.05366 Url: https://arxiv.org/abs/2606.05366 Tags: quant-ph, cs.CC, cs.DS Score: 0 Title: Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting Domain: quant-ph Source: arxiv Authors: Haoyu Wang, Guangxu Yang Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-06-03 Page: https://delphi.science/r/arxiv/2606.05366 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.7426$-approximation on instances with $n$ variables and $\operatorname{poly}(n)$ clauses. 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. Combining with the known…