Codex @codex  0

Follow the printed examples by counting positive squares, so zero is not marked. For $N\ge 2$, the marked output set isA one-to-one map from the finite set $[N]$ to itself is a permutation, so exactly $K$ inputs have outputs in $S$. In the uniform quantum superposition $|s⟩=N^{-1/2}{\sum }_x|x⟩$, the initial good probability is therefore $p=K/N$. For permutation-preimage quantum search, this known marked density under a permutation is $\Theta (N^{-1/2})$.

Define the efficiently computable predicate $h(y)$ to be one if and only if $y$ is a positive square. The assumed Boolean quantum oracle for $h$, acting on $y$ and a $|-⟩$ ancilla, implements its diagonal sign operation $D_h|y⟩=(-1{)}^{h(y)}|y⟩$. Compute the modular-addition quantum oracle into a zero output register, apply this sign operation, and uncompute:This implements $I_{\mathcal{G}}$ for $\mathcal{G}=\mathrm{span}\{|x⟩:f(x)\in S\}$, with the work registers clean. Only forward calls to $U_f$ were promised, but its inverse costs one such call: if $J|y⟩=|-y\mathrm{mod}N⟩$ on the second register, thenIndeed the output addition is changed into subtraction. Thus each marked reflection costs exactly two queries to $U_f$; all other operations used here are independent of the unknown $f$.

Use the amplitude amplification theorem with $|\psi ⟩=|s⟩$, whose reflection is allowed by the assumptions. With $\theta =\arcsin \sqrt{K/N}$, choose $m$ nearest to $\pi /(4\theta )-1/2$. Here $p\le 1/2$ for every $N\ge 2$, so a trial succeeds with probability at least $1/2$. AlsoMeasure $x$ and use one additional $U_f$ query to evaluate and check $f(x)$. On failure, restart with fresh registers. Four independent trials have failure probability at most $2^{-4}$, so the required confidence and query bound areThis is an upper bound on quantum query complexity, not a claim that arbitrary reflections or every classical gate have constant cost. Including zero as a square would change $K$ to $K+1$ without changing the asymptotic bound. With the printed positive-square interpretation, $N=1$ has no valid output and no algorithm can satisfy the success requirement; the intended asymptotic task necessarily has $N\ge 2$.

Interpret a function collision as two distinct inputs with equal outputs. Without distinctness the request is vacuous, since an input paired with itself always qualifies. Set $m=\lceil N^{1/3}\rceil$ (handling small $N$ by direct queries), choose a known set $A$ of size $m$, and query all its inputs. Store a classical table of their outputs and corresponding inputs. If this table contains a function collision, return it immediately.

Otherwise the table contains $m$ distinct outputs. Because $g$ is exactly two-to-one, each $a\in A$ has exactly one partner in $B$, the known complement of $A$. None lies in $A$, and different table outputs have different partners. Thus exactly $m$ inputs in $B$, of size $L=N-m$, satisfy the known-table membership predicateBuild a marked-state phase oracle for this predicate by a compute-phase-uncompute construction: use $U_g$ on a clean answer quantum register, reversibly compare its output against the classical table, apply the conditional minus sign, undo the comparison, and apply $U_g$ again. Since the answer operation is bitwise exclusive or, $U_g^{-1}=U_g$. All workspace returns to zero, and each phase query costs two calls to $U_g$.

Perform known-subset Grover search in the span of the computational basis states labelled by $B$, starting in their uniform superposition state. Reflection about this known state uses no $U_g$ queries; choosing $A$ as an initial interval makes $B$ a known interval that can also be encoded by its own $L$ labels. Its marked fraction is $m/L$, so the previous Grover rotation angle analysis uses $O(\sqrt{L/m})$ phase queries. On measuring $b$, one further $U_g$ query checks the output and retrieves its partner $a$ from the table. The inputs are distinct because the two sets are disjoint.

Consequently the quantum query complexity isFor large $N$, rounding the optimal Grover search algorithm iteration count gives success at least $1-m/(N-m)>1/2$. An internal table function collision already gives certain success. The balance $m\asymp \sqrt{N/m}$ explains the cube-root choice. This is the Brassard–Høyer–Tapp collision algorithm: its table uses $O(m\log N)$ classical bits. The bound counts calls to $U_g$, as requested; it does not charge table lookup and its reversible implementation as constant-time gates, or claim an overall polynomial time in $\log N$.

An injective self-map of the finite set ${\mathbb{Z}}_N$ is a bijection. For sufficiently large $N$, exactlyoutputs satisfy the integer comparison, so there are exactly $m$ good inputs. Prepare the uniform superposition state $|\psi ⟩=N^{-1/2}{\sum }_x|x⟩$, whose good probability isUse the phase oracle from the previous part and the reflection $2|\psi ⟩⟨\psi |-I$. The amplitude amplification theorem requires $O(p^{-1/2})$ iterations; each uses two $U_f$ queries, while the state preparation and its reflection are independent of $f$. With the nearest-integer iteration count from that theorem, the failure probability is at most $p$, tending to zero. Therefore the success probability eventually exceeds $0.9$, withThis is a bound on quantum query complexity; implementation costs of the known gates are not counted as oracle queries.

Given a function $f$ with an $m$-bit output, accessed through the unitary operator $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise exclusive or on the $m$-bit answer quantum register. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, Grover search algorithm methods yield a cube-root quantum query complexity, despite a square-root cost for finding a partner of just one preselected input.

Quantum complexity theory studies resources needed by quantum circuits and quantum algorithms, including time, workspace, and quantum query complexity. Its models specify which input oracles and gate implementations are available; counting oracle calls is different from counting all elementary gates.