The optimal quartic separation between randomized and quantum queries
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
Shows that the universal bound R(f)=O((1+Q(f))^4) for total Boolean functions is sharp in its exponent, ruling out every smaller power and disproving the conjectured cubic relation. Here R and Q are randomized and quantum worst-case bit-query complexities with error at most 1/3; computation between queries is unrestricted.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
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))^α) with α < 4. Thus the known quartic upper bound has the…
Full source abstract
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))^α) 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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.