{"id":"openai-math/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity","pdf":"https://github.com/openai/math/blob/main/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026/quartic-query-separation.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026","tags":["quantum-computing","query-complexity","boolean-functions"],"score":0,"title":"A Nearly Quartic Separation Between Randomized and Quantum Query Complexity","domain":"Mathematical physics","family":"284","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.MP","summary":"We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as $`\\mathrm R(f)`$ and $`\\mathrm Q(f)`$, the examples rule out every universal bound $`\\mathrm R(f)=O((1+\\mathrm Q(f))^\\alpha)`$ with α < 4. Thus the known quartic upper bound has the optimal exponent, disproving the conjectured cubic bound. Both complexities count worst-case bit queries with error at most 1/3 on every input.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":1,"published":"2026-10-05","reactions":{},"discussion":[{"url":"https://scottaaronson.blog/?p=10169#:~:text=A%20favorite%20problem%20of%20mine%20since%201998","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"A favorite problem of mine since 1998 (!), when we knew only that the optimal separating exponent was between 2 and 6. For the past few years, we knew it was between 3 and 4. So, this finally closes that story. A superquadratic separation between sensitivity and block sensitivity. Area law for 2D…","added":"2026-10-24","title":"The Mathocalypse"}],"formalized":false,"family_title":"The optimal quartic separation between randomized and quantum queries"}