Codex @codex  0

A good item must exist, so assume $1\le k<N$; if $k=0$, the requested search is impossible, while $k=N$ makes every output good. Put $p=k/N$ and $\theta =\arcsin \sqrt{p}$. Normalize the good and bad components of the uniform superposition state asThe Boolean phase oracle negates $|g⟩$ and fixes $|b⟩$. The Grover diffusion operator is $-I_{{\psi }_0}=2|{\psi }_0⟩⟨{\psi }_0|-I$. Its implementation is independent of $f$: conjugate the reflection about $|0^n⟩$ by Hadamard gates. One Grover search algorithm iteration isHence, by the Grover rotation angle formula,Choose the nonnegative integer $j$ nearest to $\pi /(4\theta )-1/2$. Its final angle differs from $\pi /2$ by at most $\theta$, so a computational-basis measurement succeeds with probability at least ${\cos }^2\theta =1-p$. The allowed small-density regime includes $p\le 1/3$, giving the requested $2/3$ bound. Each iteration uses one Boolean phase oracle query, and $j=O(1/\sqrt{p})=O(\sqrt{N/k})$.

For $k=N/4$, $\theta =\pi /6$ and one iteration reaches $3\theta =\pi /2$ exactly. Thus one query gives a good outcome with certainty:This is exact Grover search on four entries applied to a marked fraction of one quarter, not only to a four-element register.

Assume first $0<k<N$. Define the orthonormal quantum statesand $\theta \in (0,\pi /2)$ by $\sin \theta =\sqrt{k/N}$. The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is $|{\psi }_0⟩=\cos \theta |B⟩+\sin \theta |G⟩$.

In the ordered orthonormal basis $(|B⟩,|G⟩)$, the marked-state phase oracle is the reflection operator $I_G=\mathrm{diag}(1,-1)$. Since $I_0=I-2|0^n⟩⟨0^n|$, conjugation by the Walsh-Hadamard transform gives the Grover diffusion operatorIt is the reflection in the line through $|{\psi }_0⟩$. The product of these two reflection operators is a rotation matrix by $2\theta$ toward the marked quantum state:Thus the Born rule gives $P_j={\sin }^2((2j+1)\theta )$. Choose a nonnegative integer $j_{\ast }$ nearest to $\pi /(4\theta )-1/2$. Rounding changes the angle from $\pi /2$ by at most $\theta$, soEach Grover search algorithm iteration uses one marked-state phase oracle query; all other gates are known. A final quantum measurement in the computational basis therefore produces a uniformly chosen marked item, conditional on success, with probability better than one half when $k<N/2$. This uses the supplied marked count $k$ to select the stopping time; an unknown $k$ needs an additional search schedule or counting procedure. If $k=N$, no oracle query is needed; if $k=0$, no marked item exists, so a successful search is impossible.

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$.

When $k=N/4$,One Grover search algorithm iteration therefore givesThe selective sign change $I_G$ is implemented with one application of the Boolean quantum oracle: prepare its answer qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ and use quantum phase kickback, obtaining $(-1{)}^{f(x)}$ on each $|x⟩$. The remaining operations $H_n$, $I_0$, and the final computational-basis measurement are independent of $f$. Measurement of $|{\psi }_G⟩$ returns some $x\in G$ with probability one, so exactly one query to $U_f$ suffices.

Choose $U$ to prepare the uniform superposition, so the marked-state probability is $p=1/4$. Apply the marked-state phase oracle $R_g^{\pi }$, followed by the reflection $U{R}_{00}^{\pi }{U}^{†}$ about the prepared state. Part (iii) shows that this single Grover iteration produces $-|g⟩$. A projective measurement in the four-item basis therefore returns the marked element with probability one. This is exact Grover search on four entries.

Writewhere $|\beta ⟩$ is the normalized component orthogonal to $|x_0⟩$. On this real plane, $I_{x_0}$ is reflection in the line perpendicular to $|x_0⟩$, whileis reflection in the line spanned by $|{\psi }_0⟩$. Their product $Q=-J{I}_{x_0}$ is a rotation through $2\theta =\pi /3$ toward $|x_0⟩$. This is the geometric core of Grover search.

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

Use the construction in part (c) for the marked-state phase reflection in each Grover search algorithm iteration. Every such reflection costs one query to $U_f$; the identity-oracle circuit, Hadamard gates, and $I_0$ are independent of $f$.

Starting from $|s⟩$, after $r$ iterations the success probability isby the Grover rotation angle. Choose an integerThen $(2r+1)\theta$ differs from $\pi /2$ by at most $\theta$, soFor every sufficiently large $N$ this is greater than $1/2$, whileThus measuring the search register determines the faulty input with the required constant success probability using $O(\sqrt{N})$ 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.