{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-03","reactions":{}}