physics2u
PhysicsMathsChemistryBiology
Tier
⌕ Search ⌘K
Derivation

Grover Search and Its Optimality

D-412 Home PU-404 Threads chance · waves · symmetry Depends on Universality of CNOT with Single-Qubit Gates
Statement

Given an unstructured search space of \(N\) items with a single marked item \(\lvert w\rangle\), accessed only through a phase oracle \(O_w=\mathbf{I}-2\lvert w\rangle\langle w\rvert\), the Grover iterate \(G=D\,O_w\) (with diffusion \(D=2\lvert s\rangle\langle s\rvert-\mathbf{I}\)) applied \(k\approx\tfrac{\pi}{4}\sqrt{N}\) times to the uniform superposition \(\lvert s\rangle\) drives the success amplitude to \(\mathcal{O}(1)\), so the marked item is found in \(\Theta(\sqrt{N})\) oracle queries. Moreover, no quantum algorithm can identify the marked item with bounded error using fewer than \(\Omega(\sqrt{N})\) queries, so this query complexity is provably optimal.

Why it matters

Grover's algorithm is the canonical example of a provable, general-purpose quantum speedup: any problem expressible as "find the needle in a structureless haystack" — database lookup, SAT witness search, collision finding, inverting a one-way function — inherits a quadratic advantage over the best possible classical strategy. Unlike Shor's algorithm, the speedup is not exponential, but it is universal (it makes no assumption about the oracle's internal structure) and it is tight.

The matching lower bound is equally important: it tells us the quadratic speedup is the most a quantum computer can extract from an unstructured oracle. This delineates a sharp boundary — exponential quantum speedups require exploitable structure (periodicity, hidden subgroups), never brute-force search alone.

Assumptions
The marked item is unique and known to exist.If \(M>1\) items are marked or \(M\) is unknown, the rotation angle changes to \(\sin\theta=\sqrt{M/N}\) and a fixed iteration count over-rotates past the target; one needs quantum counting or fixed-point amplitude amplification.
The oracle is available as a coherent unitary \(O_w\) that phase-flips the marked basis state.Without reversible, superposition-respecting query access the query model is void and the algorithm cannot even be stated; a classical membership test gives no amplitude interference.
The uniform superposition \(\lvert s\rangle=\tfrac{1}{\sqrt{N}}\sum_{x}\lvert x\rangle\) is preparable, e.g. by Hadamards on \(n=\log_2 N\) qubits.This uses only single-qubit gates from a universal set; if the initial state is not \(\lvert s\rangle\) the geometric angle \(\theta\) between start state and target is different and the optimal \(k\) shifts.
Evolution is coherent: no decoherence or gate error over the \(\sim\sqrt{N}\) queries.Amplitude amplification relies on constructive interference across all \(k\) iterations; a phase-flip or amplitude-damping event partway through collapses the 2D rotation and degrades success probability, in the worst case back to the classical \(1/N\).
Cost is measured in oracle queries, with intervening gates counted separately (and polynomial in \(n\)).If one instead charges for the internal gate complexity of \(O_w\), or for the \(D\) reflection, the "\(\Theta(\sqrt{N})\)" statement refers to a different resource and the optimality theorem (which is about queries) no longer directly applies.
Derivation
1
\[ O_w=\mathbf{I}-2\lvert w\rangle\langle w\rvert,\qquad D=2\lvert s\rangle\langle s\rvert-\mathbf{I},\qquad G=D\,O_w \]
Define the two unitaries. \(O_w\) flips the sign of the amplitude on \(\lvert w\rangle\) only; \(D\) (the diffusion operator) inverts every amplitude about their mean. Both are Hermitian and unitary, hence reflections. A
2
\[ \lvert r\rangle=\frac{1}{\sqrt{N-1}}\sum_{x\neq w}\lvert x\rangle,\qquad \lvert s\rangle=\sin\theta\,\lvert w\rangle+\cos\theta\,\lvert r\rangle,\qquad \sin\theta=\frac{1}{\sqrt{N}} \]
Every state reached by \(G\) stays in the real 2D plane \(\mathrm{span}\{\lvert w\rangle,\lvert r\rangle\}\), since \(O_w\) and \(D\) each map this plane to itself. Projecting \(\lvert s\rangle\) onto \(\lvert w\rangle\) gives \(\langle w\vert s\rangle=1/\sqrt{N}=\sin\theta\). B
3
\[ O_w\big(a\lvert w\rangle+b\lvert r\rangle\big)=-a\lvert w\rangle+b\lvert r\rangle \]
Within the plane, \(O_w\) is the reflection about the axis \(\lvert r\rangle\) (it negates the \(\lvert w\rangle\) component, fixes the \(\lvert r\rangle\) component). A reflection about a line at angle \(\alpha\) is an orthogonal map with determinant \(-1\). C
4
\[ D=2\lvert s\rangle\langle s\rvert-\mathbf{I}\ \Longrightarrow\ D\,\lvert s\rangle=\lvert s\rangle,\quad D\,\lvert s^{\perp}\rangle=-\lvert s^{\perp}\rangle \]
\(D\) is the reflection about the axis \(\lvert s\rangle\): it fixes \(\lvert s\rangle\) and negates the orthogonal in-plane direction \(\lvert s^{\perp}\rangle\). Equivalently it is inversion about the mean amplitude, the geometric content of "diffusion". C
5
\[ G=D\,O_w=\text{(reflection about }\lvert s\rangle)\circ(\text{reflection about }\lvert r\rangle)=R(2\theta) \]
The composition of two reflections whose axes meet at angle \(\theta\) is a rotation by \(2\theta\). Since \(\lvert s\rangle\) makes angle \(\theta\) with \(\lvert r\rangle\), each Grover iterate rotates the state by \(+2\theta\) toward \(\lvert w\rangle\) in the plane. C
6
\[ \lvert\psi_k\rangle=G^{k}\lvert s\rangle=\sin\!\big((2k+1)\theta\big)\,\lvert w\rangle+\cos\!\big((2k+1)\theta\big)\,\lvert r\rangle \]
Starting at angle \(\theta\) from \(\lvert r\rangle\) and adding \(2\theta\) per iterate, after \(k\) iterates the state sits at angle \((2k+1)\theta\). The amplitude on \(\lvert w\rangle\) is \(\sin\!\big((2k+1)\theta\big)\). B
7
\[ P_{\text{succ}}(k)=\sin^{2}\!\big((2k+1)\theta\big),\qquad (2k_{\ast}+1)\theta=\frac{\pi}{2}\ \Rightarrow\ k_{\ast}=\frac{\pi}{4\theta}-\frac{1}{2} \]
Measuring in the computational basis yields \(\lvert w\rangle\) with probability \(\sin^2\). This is maximized (equal to 1) when the total rotation reaches \(\pi/2\), i.e. the state is aligned with \(\lvert w\rangle\). Since \(k\) must be an integer, take \(k=\lfloor k_{\ast}\rceil\). B
8
\[ N\gg1:\quad \theta=\arcsin\frac{1}{\sqrt{N}}\approx\frac{1}{\sqrt{N}}\quad\Longrightarrow\quad k_{\ast}\approx\frac{\pi}{4}\sqrt{N}=\Theta(\sqrt{N}) \]
For large \(N\) the angle is small, \(\theta\approx 1/\sqrt N\), so the optimal number of iterations — and hence oracle queries — scales as \(\tfrac{\pi}{4}\sqrt N\). This establishes the upper bound. A
9
\[ (O_x-\mathbf{I})\lvert\phi\rangle=-2\langle x\vert\phi\rangle\lvert x\rangle\ \Rightarrow\ \big\lVert\,\lvert\psi_x^{T}\rangle-\lvert\phi_T\rangle\big\rVert\le 2\sum_{t=0}^{T-1}\big|\langle x\vert\phi_t\rangle\big| \]
Optimality (BBBV hybrid argument). Compare an algorithm running with the true oracle \(O_x\) (state \(\lvert\psi_x^T\rangle\) after \(T\) queries) against the same circuit with an empty oracle \(\mathbf{I}\) (state \(\lvert\phi_t\rangle\)). Swapping \(\mathbf{I}\to O_x\) at step \(t\) perturbs the state by \(2|\langle x\vert\phi_t\rangle|\); unitaries preserve norm, so the triangle inequality accumulates the perturbations. C
10
\[ \sum_{x}\big\lVert\lvert\psi_x^{T}\rangle-\lvert\phi_T\rangle\big\rVert^{2}\le 4\sum_{x}\Big(\sum_{t}|\langle x\vert\phi_t\rangle|\Big)^{2}\le 4T\sum_{t}\sum_{x}|\langle x\vert\phi_t\rangle|^{2}=4T^{2} \]
Cauchy–Schwarz turns \(\big(\sum_t a_t\big)^2\le T\sum_t a_t^2\); then interchange sums and use \(\sum_x|\langle x\vert\phi_t\rangle|^2=1\) (normalization) for each of the \(T\) steps, giving \(\sum_t 1=T\). The total deviation over all \(N\) possible marks is bounded by \(4T^2\). C
11
\[ \text{success}\Rightarrow\big\lVert\lvert\psi_x^{T}\rangle-\lvert\phi_T\rangle\big\rVert^{2}\ge c\ \ \forall x\ \Rightarrow\ cN\le 4T^{2}\ \Rightarrow\ T\ge\tfrac{1}{2}\sqrt{cN}=\Omega(\sqrt{N}) \]
To identify each possible marked \(x\) with bounded error, the final state must be distinguishable from the mark-free run, forcing a constant deviation \(c>0\) for every \(x\). Combined with the \(4T^2\) ceiling this yields \(T=\Omega(\sqrt N)\), matching the upper bound. C
Result
\[ Q(N)=\Theta(\sqrt{N}),\qquad k_{\ast}=\left\lfloor\frac{\pi}{4\theta}-\frac{1}{2}\right\rceil,\quad \sin\theta=\frac{1}{\sqrt{N}} \]

Reading. The number of oracle queries needed to find a unique marked item among \(N\) is asymptotically \(\tfrac{\pi}{4}\sqrt N\), a quadratic improvement over the classical \(\Theta(N)\) (expected \(N/2\) probes). The lower bound \(\Omega(\sqrt N)\) proves no quantum strategy does better for an unstructured oracle: the amplitude that any \(T\)-query algorithm can build up on a specific target grows only as \(T/\sqrt N\), so distinguishing all \(N\) marks demands \(T\gtrsim\sqrt N\).

Units check. Every quantity is dimensionless. \(\theta\) is an angle (radians); \(k\) and \(T\) are pure counts of oracle calls; amplitudes and their squares (probabilities) are dimensionless numbers in \([-1,1]\) and \([0,1]\). \(\sqrt N\) is dimensionless, so \(\tfrac{\pi}{4}\sqrt N\) correctly has units of "queries" (a count). Both sides of the complexity bound are counts, consistent.

Limiting cases
  • \(N=4\): \(\sin\theta=\tfrac12\Rightarrow\theta=\tfrac{\pi}{6}\), and \(k_\ast=1\) exactly, giving \(\sin^2(3\cdot30^\circ)=\sin^2 90^\circ=1\) — a single query finds the item with certainty.
  • \(N\to\infty\): \(\theta\approx 1/\sqrt N\to0\), \(k_\ast\to\tfrac{\pi}{4}\sqrt N\), and peak success probability \(\to1\); the discretization loss from rounding \(k_\ast\) vanishes as \(\mathcal O(1/N)\).
  • \(M\) marked items, \(M\ll N\): \(\sin\theta=\sqrt{M/N}\Rightarrow k_\ast\approx\tfrac{\pi}{4}\sqrt{N/M}\); more solutions means fewer queries, scaling as \(\sqrt{N/M}\).
  • \(M=N/2\): \(\theta=\pi/4\) and \(k_\ast=\tfrac{\pi}{4\cdot(\pi/4)}-\tfrac12=\tfrac12\); zero iterations already give success probability \(1/2\) — search is trivial when half the items are marked.
Breaks when
  • The oracle has exploitable structure. If the marked item is not hidden behind a black box but carries algebraic structure (periodicity, a hidden subgroup), specialized algorithms (Shor, Simon) achieve exponential speedup and the \(\Omega(\sqrt N)\) query bound simply does not apply — it is a statement about unstructured search only.
  • The number of solutions \(M\) is unknown. A fixed \(k=\tfrac{\pi}{4}\sqrt N\) over-rotates past \(\lvert w\rangle\) when \(M>1\), dropping success probability (the "soufflé": undercook or overcook and it collapses). One must first estimate \(M\) by quantum counting or use fixed-point/oblivious amplitude amplification.
  • Decoherence acts on the \(\sqrt N\)-long coherent run. The quadratic speedup requires phase coherence across all \(\Theta(\sqrt N)\) iterations; a decoherence time shorter than the runtime destroys the interference and no speedup survives without full error correction.
  • Only classical (non-superposed) oracle access is allowed. If the oracle cannot be queried in superposition, there is no interference to amplify and the problem reverts to classical \(\Theta(N)\).
Failure modes
  • Over-iteration ("more is better"). Running well beyond \(k_\ast\) rotates the state past \(\lvert w\rangle\); success probability oscillates as \(\sin^2\), so extra queries can drop it toward zero, not raise it.
  • Forgetting the \(-\tfrac12\) / rounding. Using \(k=\tfrac{\pi}{4}\sqrt N\) blindly instead of \(\lfloor\tfrac{\pi}{4\theta}-\tfrac12\rceil\) mis-times the peak for small \(N\); at \(N=4\) this matters (correct \(k=1\), not \(1.57\)).
  • Using \(\theta\approx1/\sqrt N\) at small \(N\). The small-angle approximation is only asymptotic; for \(N=2,4\) one must use \(\theta=\arcsin(1/\sqrt N)\) exactly or the iteration count is wrong.
  • Claiming an exponential speedup. Confusing Grover with Shor — the quadratic bound is provably optimal, so \(\Theta(\sqrt N)\) cannot be improved to \(\mathrm{polylog}(N)\) for unstructured search.
  • Miscounting queries vs. gates. Reporting the gate complexity of \(D\) (which needs \(\mathcal O(\log N)\) gates per iterate) as if it were the query count; the optimality theorem bounds queries, and the gate overhead is a separate polynomial factor.
  • Assuming \(M=1\) when solutions are plural. Applying the unique-item timing to a multi-solution instance over-rotates; the correct angle uses \(\sin\theta=\sqrt{M/N}\).
Discussion

The whole algorithm is a rigid-body rotation in a two-dimensional real plane. Once one recognizes that \(O_w\) and \(D\) are reflections and that two reflections compose to a rotation by twice the angle between their axes, the "magic" of Grover collapses into elementary plane geometry: you rotate a unit vector from \(\lvert s\rangle\) toward \(\lvert w\rangle\) in steps of \(2\theta\), and you stop when you have swept \(\pi/2\). The \(\sqrt N\) arises purely because the starting overlap \(\langle w\vert s\rangle=1/\sqrt N\) makes \(\theta\approx1/\sqrt N\) small, so it takes \(\sim\tfrac{\pi}{2}/(2\theta)\approx\tfrac{\pi}{4}\sqrt N\) rotations to traverse the quadrant.

The three physics threads meet here. Chance: the output is probabilistic, \(P=\sin^2\), and the algorithm engineers the probability distribution rather than a deterministic answer. Waves: the mechanism is interference — the diffusion operator is inversion about the mean, constructively building amplitude on \(\lvert w\rangle\) while destructively suppressing the rest, exactly analogous to a wave refocusing. Symmetry: the reduction to a 2D plane is a symmetry statement — all \(N-1\) unmarked states are permutation-symmetric, so they collapse into the single collective coordinate \(\lvert r\rangle\), and the dynamics is governed by the residual \(SO(2)\) rotation symmetry of the plane.

Amplitude amplification is the general lesson: given any procedure \(A\) that produces a "good" state with amplitude \(a\), the reflection sandwich \(-A S_0 A^{\dagger} S_f\) rotates by \(2\arcsin(a)\) per step, so \(\mathcal O(1/a)\) repetitions suffice — a quadratic saving over the \(\mathcal O(1/a^2)\) classical repetitions needed to see the good outcome by sampling. Grover is the special case \(A=H^{\otimes n}\), \(a=1/\sqrt N\). This is why the technique appears as a subroutine throughout quantum algorithms (collision finding, mean estimation, quantum walks).

The optimality half is deeper than the algorithm. The BBBV hybrid argument bounds how fast any quantum query algorithm can concentrate amplitude on a hidden target: each query can move the state by at most \(2|\langle x\vert\phi_t\rangle|\), and the total query weight is conserved, \(\sum_x\sum_t|\langle x\vert\phi_t\rangle|^2=T\). A Cauchy–Schwarz counting argument then forces \(T=\Omega(\sqrt N)\). The same idea, sharpened into the polynomial method (Beals et al.) and the adversary method (Ambainis), gives tight query lower bounds across quantum complexity theory — the search bound is the prototype. It also connects to physics via the adiabatic and quantum-speed-limit viewpoints: the minimal time to rotate an initial state to an orthogonal target under a bounded-norm generator is a Mandelstam–Tamm/Margolus–Levitin bound, and Grover saturates it.

Common misconceptions. Grover does not "check all \(N\) items in parallel and pick the right one" — it never even reaches amplitude 1 without \(\sim\sqrt N\) carefully timed queries, and running longer makes it worse. Nor is the speedup exponential; the \(\Omega(\sqrt N)\) lower bound rules that out for unstructured oracles. And the "database" framing is misleading: Grover speeds up problems where the oracle is a computation (e.g. "does this assignment satisfy the formula?"), not the reading of a stored, indexed table — a genuine memory lookup is already \(\mathcal O(1)\) classically.

Worked examples
1
\[ \textbf{Search among } N=4,\ M=1. \]
Two qubits, one marked item, exact treatment. Find \(\theta\), the optimal \(k\), and the success probability. A
2
\[ \sin\theta=\frac{1}{\sqrt N}=\frac{1}{\sqrt4}=\frac12\ \Rightarrow\ \theta=\frac{\pi}{6}=30^\circ \]
Exact angle from the overlap \(\langle w\vert s\rangle\); no small-angle approximation needed. A
3
\[ k_\ast=\frac{\pi}{4\theta}-\frac12=\frac{\pi}{4\cdot(\pi/6)}-\frac12=\frac{6}{4}-\frac12=1 \]
The optimal iteration count is an exact integer, no rounding loss. A
4
\[ P_{\text{succ}}=\sin^2\!\big((2k+1)\theta\big)=\sin^2(3\cdot30^\circ)=\sin^2 90^\circ=1 \]
A single Grover iterate rotates \(\lvert s\rangle\) exactly onto \(\lvert w\rangle\). A
\[ k_\ast=1,\qquad P_{\text{succ}}=100\% \]

Reading. With four items, one oracle query finds the marked item with certainty — the celebrated exact case. A classical algorithm needs up to 3 probes (expected 2.25).

Units check. \(\theta\) in radians, \(k\) a count, \(P\) a dimensionless probability equal to 1. Consistent.

1
\[ \textbf{Search among } N=10^{6},\ M=1. \]
A million-item unstructured search; find the query count and compare to classical. B
2
\[ \theta=\arcsin\frac{1}{\sqrt{10^6}}=\arcsin(10^{-3})\approx 1.0000\times10^{-3}\ \text{rad} \]
Small-angle regime; \(\arcsin(10^{-3})\approx10^{-3}\) to one part in \(10^6\). B
3
\[ k_\ast=\frac{\pi}{4\theta}-\frac12=\frac{\pi}{4(10^{-3})}-\frac12\approx 785.40-0.5=784.9\ \Rightarrow\ k=785 \]
Round to the nearest integer number of iterations. B
4
\[ P_{\text{succ}}=\sin^2\!\big((2\cdot785+1)\,\theta\big)=\sin^2(1571\times10^{-3})=\sin^2(1.5710)\approx 0.99999 \]
Total rotation \(1.5710\) rad is within \(2\times10^{-4}\) of \(\pi/2=1.5708\), so alignment with \(\lvert w\rangle\) is near-perfect. B
\[ k\approx 785\ \text{queries},\qquad P_{\text{succ}}\approx 99.999\% \]

Reading. The marked item among a million is found in \(\approx785\) queries versus a classical expectation of \(500{,}000\) probes — a speedup factor \(\approx637\approx\tfrac{2}{\pi}\sqrt N\). Increasing \(N\) hundredfold raises the query count only tenfold.

Units check. \(k\) and the classical \(N/2\) are both query counts; their ratio is dimensionless, \(\theta\) in radians, \(P\) dimensionless. Consistent.

Problems
  1. Search among \(N=8\) with a single marked item. Compute \(\theta\) exactly, find the best integer \(k\), and give the success probability for that \(k\) (and for \(k-1\)).
    Solution \(\sin\theta=1/\sqrt8=0.35355\Rightarrow\theta=\arcsin(0.35355)=0.36136\) rad \((=20.70^\circ)\). Then \(k_\ast=\pi/(4\theta)-\tfrac12=2.1735-0.5=1.6735\), so the nearest integer is \(k=2\). Success: \(P(2)=\sin^2((2\cdot2+1)\theta)=\sin^2(5\times0.36136)=\sin^2(1.8068)=(0.9723)^2=0.9454\). For \(k=1\): \(P(1)=\sin^2(3\times0.36136)=\sin^2(1.0841)=(0.8839)^2=0.7813\). So \(k=2\) is optimal, giving \(\approx94.5\%\).
  2. Generalize to \(M\ge1\) marked items among \(N\), with \(M\ll N\). Derive the rotation angle and the optimal query count, and state the speedup factor over classical search.
    Solution The uniform superposition has overlap \(\sin\theta=\sqrt{M/N}\) with the (normalized) equal superposition of the \(M\) marked states, since \(\sum_{\text{marked}}|\langle x\vert s\rangle|^2=M/N\). Each iterate still rotates by \(2\theta\), so \(k_\ast=\pi/(4\theta)-\tfrac12\approx\tfrac{\pi}{4}\sqrt{N/M}\) for small \(\theta\). Classical expected probes to hit one of \(M\) marks \(\approx N/M\), so the speedup is \(\dfrac{N/M}{(\pi/4)\sqrt{N/M}}=\dfrac{4}{\pi}\sqrt{N/M}\), i.e. quadratic in \(\sqrt{N/M}\). Example \(N=10^6,M=100\): \(k_\ast\approx\tfrac{\pi}{4}\sqrt{10^4}=\tfrac{\pi}{4}\cdot100\approx79\) queries.
  3. Show that the diffusion operator \(D=2\lvert s\rangle\langle s\rvert-\mathbf I\) is unitary and Hermitian, and prove it performs "inversion about the mean" on amplitudes: if \(\lvert\psi\rangle=\sum_x a_x\lvert x\rangle\) then \(D\lvert\psi\rangle=\sum_x(2\bar a-a_x)\lvert x\rangle\) with \(\bar a=\tfrac1N\sum_x a_x\).
    Solution Hermitian: \((2\lvert s\rangle\langle s\rvert-\mathbf I)^\dagger=2\lvert s\rangle\langle s\rvert-\mathbf I=D\) since \(\lvert s\rangle\langle s\rvert\) is a projector (Hermitian). Unitary: \(D^2=4\lvert s\rangle\langle s\rvert^2-4\lvert s\rangle\langle s\rvert+\mathbf I=4P-4P+\mathbf I=\mathbf I\) using \(P^2=P\) for the projector \(P=\lvert s\rangle\langle s\rvert\); with \(D=D^\dagger\) this gives \(D^\dagger D=\mathbf I\). Mean: \(\langle s\vert\psi\rangle=\tfrac{1}{\sqrt N}\sum_x a_x=\sqrt N\,\bar a\). Then \(D\lvert\psi\rangle=2\lvert s\rangle(\sqrt N\bar a)-\lvert\psi\rangle=2\bar a\sum_x\lvert x\rangle-\sum_x a_x\lvert x\rangle=\sum_x(2\bar a-a_x)\lvert x\rangle\). Each amplitude \(a_x\) is reflected about the mean \(\bar a\), i.e. \(a_x\mapsto\bar a-(a_x-\bar a)=2\bar a-a_x\). QED.
  4. (Over-cooking.) For \(N=4\) (so \(\theta=30^\circ\)), tabulate the success probability for \(k=0,1,2,3\) iterations and explain the oscillation. What does this show about "running longer is better"?
    Solution \(P(k)=\sin^2((2k+1)\cdot30^\circ)\). \(k=0\): \(\sin^2 30^\circ=0.25\). \(k=1\): \(\sin^2 90^\circ=1.00\). \(k=2\): \(\sin^2 150^\circ=(0.5)^2=0.25\). \(k=3\): \(\sin^2 210^\circ=(-0.5)^2=0.25\)... more precisely \(210^\circ\) gives \(\sin=-0.5\), \(P=0.25\); \(k=4\): \(\sin^2 270^\circ=1.00\). The probability oscillates with period \(k\to k+3\) (since \(6\theta=180^\circ\)). Running past the peak at \(k=1\) rotates the state past \(\lvert w\rangle\), so \(P\) drops back to \(0.25\) at \(k=2\). Conclusion: Grover is not monotone — you must stop at \(k_\ast\); extra iterations waste queries and can destroy the answer (the "soufflé" behaviour).
  5. (Lower bound.) Using the BBBV bound \(\sum_x\lVert\lvert\psi_x^T\rangle-\lvert\phi_T\rangle\rVert^2\le 4T^2\), suppose an algorithm succeeds with probability \(\ge\tfrac12\) for every marked \(x\), which forces \(\lVert\lvert\psi_x^T\rangle-\lvert\phi_T\rangle\rVert^2\ge\tfrac12\). Derive the resulting lower bound on \(T\) and identify the constant.
    Solution Summing the per-\(x\) lower bound over all \(N\) marks: \(\sum_x\tfrac12=\tfrac N2\le\sum_x\lVert\cdots\rVert^2\le 4T^2\). Hence \(4T^2\ge N/2\), i.e. \(T^2\ge N/8\), giving \(T\ge\sqrt{N/8}=\tfrac{1}{2\sqrt2}\sqrt N\approx0.354\sqrt N\). So \(T=\Omega(\sqrt N)\) with constant \(1/(2\sqrt2)\). This matches the Grover upper bound \(\tfrac{\pi}{4}\sqrt N\approx0.785\sqrt N\) up to the constant factor \(\pi/4\) vs \(1/(2\sqrt2)\); sharper adversary/polynomial arguments close the gap and prove \(\tfrac{\pi}{4}\sqrt N\) is exactly optimal to leading order.