1 · The essentials
How many input bits must a method inspect to answer a yes-or-no question? The manuscript compares methods that use randomness with methods that use quantum computation, counting only how many bits they inspect. Both must give the right answer with error at most one third on every input, and the question must have a defined answer for every possible input. A known bound says that the randomized count is at most a constant times the fourth power of one plus the quantum count. The manuscript presents examples showing that no smaller power can work for all such questions, including the previously conjectured third power. This concerns the number of bits inspected, not the total time spent computing. The main result has not been formalized in Lean or formally verified.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine answering a yes-or-no question about a row of covered cards while counting only requests for information about the cards, not the thinking between requests. The comparison asks how far apart two different ways of obtaining that information can be; ordinary card inspection does not capture how quantum queries work.
Why it matters
The result shown in the manuscript identifies the optimal exponent in a universal comparison between randomized and quantum bit-query counts. It rules out the conjectured cubic relation in this setting. Its significance is specific to query complexity, where computation between queries is unrestricted.
2 · Going further
The problem concerns total Boolean functions : functions with a Boolean output defined on every input bit string of the relevant length. Let and denote randomized and quantum worst-case bit-query complexities, respectively, with error at most on every input. Computation between queries is unrestricted. The source states the known universal upper bound and asks whether its exponent can be reduced.
The main manuscript, “A Nearly Quartic Separation Between Randomized and Quantum Query Complexity,” constructs total Boolean functions with a nearly quartic separation. As stated in its abstract, these examples rule out every universal bound with . Thus the fourth-power exponent is optimal in this sense, and the conjectured cubic bound does not hold.
The argument is described in the supplied abstract only at the level of constructing separating examples; no construction details or intermediate steps are supplied. Only the main manuscript is included, so no relationship to companion manuscripts can be described from this source. The main result is not formalized in Lean and has not been formally verified.
Useful notions
- Boolean functions on bit strings
- Worst-case query counting
- Randomized and quantum computation
- Bounded error on every input
- Big-O bounds and exponents
What was known before / what is new
Before
The source states that a universal quartic upper bound relating randomized and quantum query complexity was already known for total Boolean functions. It also identifies a conjectured cubic bound, without providing further historical context.
New
The manuscript presents total Boolean functions with a nearly quartic randomized-versus-quantum query separation. These examples rule out every fixed exponent below four in the stated universal bound, not merely the exponent three. Together with the known upper bound, this makes four the optimal exponent.
Limits and assumptions
The claim applies to total Boolean functions and to worst-case bit-query complexities with error at most 1/3 on every input. Computation between queries is unrestricted, so the statement is not a comparison of total running times. Optimality is stated at the level of the exponent; the supplied abstract does not specify finer factors in the nearly quartic separation. The main result is not formalized in Lean and has not been formally verified. The source identifies no further open problem and gives no construction details.
Mini glossary
- Total Boolean function —
- A rule assigning a yes-or-no output to every input bit string of the relevant length.
- Query complexity —
- A measure counting input-bit queries rather than computation performed between them.
- Worst-case —
- A requirement that the query bound apply across all inputs, rather than only to an average input.
- Bounded error —
- Here, the requirement that the probability of an incorrect answer be at most one third on every input.
- Universal quartic upper bound —
- The statement that randomized query complexity is at most a constant times for all total Boolean functions.
Keywords : Query complexity · Quantum computation · Quartic separation
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Shows that the universal bound 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.
To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.
Manuscripts in this family
A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
05/10/2026We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as and , the examples rule out every universal bound 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.