 Solution

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.