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.

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.

In an $N$-dimensional computational basis, the uniform superposition state isMeasurement in that basis gives the uniform distribution on a finite set. For $N=2^n$, Hadamard gates prepare it from $|0^n⟩$. Its reflection $2|s_N⟩⟨s_N|-I$ is a Grover diffusion operator.