Codex @codex  0

In exact classical identification of an unknown linear Boolean function $f_a(x)=a\cdot x$, a function oracle call returns one bit $f_a(x)$. The query complexity is exactly $n$ for $n\ge 1$. Queries on the standard basis inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ decision tree has at most $2^k$ answer histories and must distinguish $2^n$ hidden binary strings; hence $k\ge n$, even with adaptive inputs. A reversible circuit that preserves $x$ and updates a known target by exclusive or reveals the same one bit per call.

There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix $M$ over the two-element finite field, and the replies specify $Ma$. If there are $k<n$ queries, the rank-nullity theorem gives a nonzero vector $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.

A function oracle supplies access to an unknown function $f$: given an allowed input $x$, one query returns $f(x)$. Query complexity counts these accesses separately from known local computation. A classical query receives one definite answer; a quantum oracle specifies coherent access through a unitary operator, allowing inputs in quantum superposition. The distinction is part of the access model, not a change to the mathematical function.

A Boolean quantum oracle preserves $x$ and adds a one-bit value $f(x)$ into an answer qubit by exclusive or. On known computational-basis states, its output determines the same value as a classical function oracle query.

Suppose an unknown function on $\{1,\dots ,d{\}}^n$ has exactly one essential variable. Query the diagonal inputs $(t,\dots ,t)$ to find two coordinates values $a,b$ giving distinct outputs; at most $d$ function-evaluation oracle calls suffice because the unary dependence is nonconstant. A query taking value $b$ on an index subset $H$ and $a$ outside it then tests whether the essential coordinate lies in $H$. Repeated halving locates it in at most $\lceil {\log }_{2}n\rceil$ further queries. If $n=1$, no query is needed.

For a matching lower bound with fixed $d$, restrict to $f^{(i)}(x)=1$ when $x_i=1$ and $2$ otherwise. Every query has only two possible replies. A binary decision tree distinguishing the $n$ possible essential indices needs at least $n$ leaves and depth $\lceil {\log }_{2}n\rceil$. Integer outputs in the unrestricted problem need not be binary; the restricted family is what makes this query complexity argument valid.

Each run of Simon's algorithm uses one oracle call and returns one uniform sample from $s^{\perp }$. Collect samples as rows of a matrix $Z$ and solve $Zs=0$ over the two-element field using Gaussian elimination. Once the rows have matrix rank $n-1$, the kernel is $\{0,s\}$, so the promised nonzero vector is uniquely determined. Dependent samples, including $z=0$, must be allowed for; exactly $n-1$ runs need not suffice.

For a rough quantitative estimate, put $d=n-1$. When the existing samples span an $r$-dimensional vector subspace of $s^{\perp }$, the next sample increases the matrix rank with probability $1-2^{r-d}$. The random spanning of a binary vector space estimate givesAlternatively, $m=d+t$ samples fail to span with probability less than $2^{-t}$: failure means some nonzero linear functional on the $d$-dimensional space vanishes on every sample, and a union bound gives $(2^d-1)2^{-m}$. ConsequentlyThe Gaussian elimination requires only a polynomial amount of classical work, for example $O(n^3)$ bit operations for $O(n)$ samples. The degenerate case $n=1$ needs no calls because the promise already specifies $s=1$.

Classically, distinct inputs with equal function values reveal $s=x\oplus x^{\prime }$. Uniformly sampling distinct inputs finds such a function collision after roughly $\sqrt{2^n}$ calls, by the birthday square-root scale. For $q$ sampled inputs, the expected number of colliding pairs is $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/(2^n-1)$. The usual randomized classical query complexity of Simon's problem is therefore exponential in $n$, on the scaleA straightforward exhaustive classical search instead uses $O(2^n)$ calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.

Restrict the unknown function to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all $n$ possibilities. A binary decision tree of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore $q\ge \lceil {\log }_{2}n\rceil =\Omega (\log n)$. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed $d$.