Grover search starts from a uniform superposition, but the underlying rotation works for a much broader preparation. If an algorithm already produces a desired outcome with known nonzero probability , amplitude amplification can increase that probability by reflecting about both the desired subspace and the prepared state. The price is that the preparation and its inverse must be implemented coherently, not merely sampled as a black box.
Preparing good and bad components
Definition 2.8.1
(Good and bad components)
Let be a unitary on a finite-dimensional register, and set . Let be the orthogonal projector onto the good subspace. For now assume , where
The normalized vectors are orthogonal. Set with . Then
Definition 2.8.2
(Phase oracle, preparation reflection and iteration)
Define the phase oracle and the prepared-state reflection . The latter is implemented as . One amplification iteration is : the rightmost oracle acts first. The here denotes the entire register's all-zero initial basis state.
Concept lensGeometric
Two reflections as one rotation
The same iteration has a plane-geometry description. In the plane spanned by , the oracle fixes and negates , so it is the reflection in the line through ; and is the reflection in the line through . These two lines meet at angle , and two reflections in lines at angle compose to a rotation through . Hence each iteration turns the state by toward , while starts at angle from . The matrices in the next section turn this picture into a computation.
Why two reflections rotate
Theorem 2.8.3
(Amplitude-amplification formula)
After integer iterations,
A measurement that distinguishes the good subspace succeeds with probability .
Proof
(Two reflections compose to a rotation)
Both reflections preserve the plane spanned by . In that ordered basis, abbreviating , ,
Multiplication gives
Applied to , this yields . The same angle-addition identity inductively proves the formula. Squaring the coefficient of gives the success probability.
Proof X-ray
Where the proof uses each hypothesis
The argument has three parts. First, invariance of the plane: negates and fixes because and , and stays in the plane because lies in it. This needs , which is what makes a well-defined orthonormal pair. Second, the only non-routine step is the double-angle simplification , , , which turns the product into a rotation matrix. Third, the induction closes because a rotation by adds to the angle of , so the starting angle becomes after steps. Nothing is approximated, and the rotation acts only on the two coefficients, so relative weights inside the original good projection are preserved: conditional on success, a finer computational-basis measurement has the distribution of .
Worked example 2.8.4
(Certainty after one iteration)
Suppose
and are good. Then , so . One iteration has good amplitude and succeeds with certainty. Conditional on success, and have probabilities and , not equal probabilities. The state preparation determines the distribution within the good subspace.
Common mistake
(Confusing with )
The angle is defined by , not by . For the correct angle is , because ; using gives a wrong angle and a wrong success probability. After iterations the success probability is , which in general equals only for .
Choosing an iteration count
When is known, choose a nonnegative integer nearest to ; break ties arbitrarily. The target number is nonnegative because , and rounding gives
The success probability is at least . In particular, when is small this is close to one. Since , this choice has . Each iteration uses one call to , one to , one to , and one reflection about ; the initial preparation requires one additional call to . These are ideal coherent operations; the query count does not include their problem-dependent implementation cost.
Worked example 2.8.5
(Searching eight items with one marked)
Take and let mark one basis state, so , , and . Then and , so the rule chooses . With we have , hence
This exceeds the guaranteed . For comparison, gives and gives about , so is the best choice.
Worked example 2.8.6
(A tie: success stays at one half)
Let , so and lies exactly halfway between and ; the rule allows either. The success probability is , and is an odd multiple of , so the value is for every . The guarantee holds with equality, and no number of iterations gives certainty: the state turns in steps of , which here never lands on the good axis.
Counterexample mode
More iterations can undo the improvement
A tempting rule says that every further iteration can only improve the success probability. If , then . Measuring the prepared state immediately succeeds with probability . One iteration instead gives success . The state has rotated past the good direction. Repeating the same iteration indefinitely is not a monotone improvement rule.
If , the normalized is undefined and the prepared state has no good component: these reflections alone cannot create one. If , the initial measurement already succeeds with certainty. These endpoint cases must be separated from the two-dimensional formula.
What the guarantee assumes
Knowing enables the stated choice of ; an unknown success probability needs a different strategy and analysis. The oracle must apply the correct phase coherently, and must actually be available. Preparing independent classical samples from the output of is not enough to implement reflection about . The guarantee concerns an ideal circuit and counts oracle/preparation uses; imperfect operations and the complexity of recognizing good outputs require additional analysis.
Common mistake
(Reflecting about instead of about )
The operator alone reflects about the all-zero state, which is generally not the prepared state. The reflection about is the conjugate . Omitting and gives a different operator, for which the rotation formula does not hold.
This general statement includes uniform search: take and let mark of basis states, so . It also allows a nonuniform prepared state and an arbitrary good subspace, as long as the required reflections can be implemented.
Practice with solutions
Quick check
(For , find and the success probability after two iterations.)
Solution · Answer
Here and : the second iteration overshoots, since one iteration already reached probability .
Quick check
(For , which does the rule choose, and what is the success probability?)
Solution · Answer
Now and , so and . With , , so the success probability is , above the guaranteed .
Quick check
(In the first worked example, what is the probability of measuring after one iteration?)
Solution · Answer
It is : the good subspace is reached with probability , and the conditional probability of inside it is .
Quick check
(Why does access to classical samples from the distribution of not by itself provide the stated reflection?)
Solution · Answer
The construction requires coherent access to both and its inverse, including phase information absent from a classical sample distribution.