we-solve (beta)

Phys-84 · physics · mathematics · Physics

The optimal randomized-versus-quantum query exponent for total Boolean functions

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
For bounded-error query complexities of total Boolean functions, is the smallest universal polynomial exponent exactly four: $R(f)=O((1+Q(f))^4)$ for every f, while for every fixed $k\geq 2$ there are total functions $F_{k,m}$, along sufficiently large powers of four m, with $Q\leq C_k$ sqrt(m)(log $m)^{b_k}$ and $R\geq c_k$ $m^{2-1/k}/(\log $ $m)^2$?

Short English statement

For bounded-error query complexities of total Boolean functions, is the smallest universal polynomial exponent exactly four: $R(f)=O((1+Q(f))^4)$ for every f, while for every fixed $k\geq 2$ there are total functions $F_{k,m}$, along sufficiently large powers of four m, with $Q\leq C_k$ sqrt(m)(log $m)^{b_k}$ and $R\geq c_k$ $m^{2-1/k}/(\log $ $m)^2$?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Phys-84-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Phys-84

Total Boolean functions are claimed to separate bounded-error randomized and quantum queries by nearly the fourth power, excluding every universal exponent below four. The question retains these same parameters and conventions. Within these assumptions, this is a claimed affirmative answer to the stated question.

The optimal randomized-versus-quantum query exponent for total Boolean functions

OpenAI's claim

OpenAI presents a proof in the selected manuscript. Total Boolean functions are claimed to separate bounded-error randomized and quantum queries by nearly the fourth power, excluding every universal exponent below four.

Mathematical statement of the claimed result

Result 1.
For total Boolean functions, let $R(f)$ and $Q(f)$ be bounded-error randomized and quantum query complexities. The source claims the optimal universal power is four: \[ R(f)=O((1+Q(f))^4). \] For every fixed integer $k\ge2$, it supplies total functions $F_{k,m}$, for sufficiently large powers of four $m$, such that \[ Q(F_{k,m})\le C_k\sqrt m(\log m)^{b_k},\qquad R(F_{k,m})\ge c_km^{2-1/k}/(\log m)^2. \] Letting $k$ grow excludes any smaller universal exponent.

Outline of the argument

An addressed certificate with outward pointers totalizes a hard partial function. An exact quantum subroutine and certificate checking give the quantum upper bound, while randomized information and pointer constraints force the larger worst-case bit-query cost.

Formal verification

Family 284 has no Lean scope page in this release. Its selected result is not presented as formalized. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

Go to contribution →