{"ID":3084639,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-06T19:15:30.205453645Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05366","arxiv_id":"2606.05366","title":"Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting","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 $Ω(\\sqrt{n})$ space for any classical streaming algorithm. Therefore, it yields an exponential quantum space advantage for Max-$k$SAT in the streaming setting. We further give a one-pass quantum streaming algorithm for Max-2OR that uses $\\operatorname{polylog}(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.","short_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 $\\...","url_abs":"https://arxiv.org/abs/2606.05366","url_pdf":"https://arxiv.org/pdf/2606.05366v1","authors":"[\"Haoyu Wang\",\"Guangxu Yang\"]","published":"2026-06-03T19:15:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}