= Solution
Assume first $0<k<N$. Define the orthonormal <quantum states>
$$
|B\rangle=\frac1{\sqrt{N-k}}\sum_{x\notin G}|x\rangle,\qquad |G\rangle=\frac1{\sqrt k}\sum_{x\in G}|x\rangle,
$$
and $\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\rangle=\cos\theta|B\rangle+\sin\theta|G\rangle$.
In the ordered <orthonormal basis> $(|B\rangle,|G\rangle)$, the <marked-state phase oracle> is the <reflection operator> $I_G=\operatorname{diag}(1,-1)$. Since $I_0=I-2|0^n\rangle\langle0^n|$, conjugation by the <Walsh-Hadamard transform> gives the <Grover diffusion operator>
$$
D=-H_nI_0H_n=2|\psi_0\rangle\langle\psi_0|-I.
$$
It is the reflection in the line through $|\psi_0\rangle$. The product of these two <reflection operators> is a <rotation matrix> by $2\theta$ toward the marked <quantum state>:
$$
Q=DI_G=\begin{pmatrix}\cos2\theta&-\sin2\theta\\\sin2\theta&\cos2\theta\end{pmatrix},\qquad Q^j|\psi_0\rangle=\cos((2j+1)\theta)|B\rangle+\sin((2j+1)\theta)|G\rangle.
$$
Thus the <Born rule> gives $P_j=\sin^2((2j+1)\theta)$. Choose a nonnegative integer $j_*$ nearest to $\pi/(4\theta)-1/2$. Rounding changes the angle from $\pi/2$ by at most $\theta$, so
$$
\boxed{P_{j_*}\geq\cos^2\theta=1-\frac kN,\qquad j_*=O\!\left(\sqrt{\frac Nk}\right).}
$$
Each <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.
Back to article page
