{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaezhda6fbeifgs32j57xuoxjureh7fqa3ijh5n3exfdh57m72wiy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnhjuz6ozll2"
  },
  "path": "/report/2026/092",
  "publishedAt": "2026-06-03T23:48:20.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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 $\\Omega(\\sqrt{n})$ space for any classical streaming algorithm. Therefore, it yields an exponential quantum space advantage for Max-$k$SAT in the streaming setting.\n\nWe further give a one-pass quantum streaming algorithm for Max-2OR that uses 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.",
  "title": "TR26-092 |  Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting | \n\n\tGuangxu Yang"
}