A quantum speedup is not obtained merely by preparing a superposition. Measurement returns one outcome. An algorithm must arrange interference so that useful outcomes have large probability, and its complexity claim must specify the input model and the resources counted.
The quantum Fourier transform
Definition 2.2.1
(Quantum Fourier transform)
For , let . The quantum Fourier transform on qubits is the linear map
Proposition 2.2.2
(Unitarity of the Fourier transform)
is unitary.
Proof
(Orthonormal columns)
The inner product of its and columns is . If the sum is . Otherwise it is a finite geometric sum with ratio not equal to one but with th power one, and is zero. Thus the columns are orthonormal and .
Worked example 2.2.3
(The transform of a basis state)
For and input , the output is . Measurement alone gives each label with probability ; relative phases become useful when a subsequent transformation makes them interfere.
The inverse transform replaces by . The transform admits an exact circuit of Hadamard gates and controlled phase rotations with such gates, counting each rotation as a gate; an implementation over a fixed discrete gate set instead needs approximation and an accuracy-dependent cost.
Phase estimation and order finding
Suppose , with , and the eigenstate is available. Prepare control qubits in and apply Hadamards. Controlled powers then create
If exactly, the first register is ; applying and measuring returns with certainty. For a phase that is not an integer multiple of the inverse transform gives a distribution concentrated near , not a guaranteed exact answer. The availability and cost of controlled powers of are part of the algorithm's resource assumptions.
Worked example 2.2.4
(A phase between two grid points)
Let , so , and take , which is not a multiple of . After the inverse transform, outcome has amplitude . With its probability is . For this gives probabilities , about , and about for , which sum to one. The most likely outcome has nearest to , but its probability is only about : for such phases the procedure returns a distribution, not an exact answer.
Common mistake
(Reading the outcome as the phase)
The measured outcome is an integer with , and the phase estimate is , not . With three control qubits and the outcome is (binary ), and the estimate is .
Definition 2.2.5
(Order modulo M and its eigenstates)
Order finding uses a particular unitary. For coprime to an integer , multiplication by modulo permutes the residues, and hence defines a unitary on a register containing those residues, extended by the identity to unused basis states. If is the least positive integer with , then for ,
The eigenvalue follows by shifting the index cyclically. The efficiently prepared state is the equal superposition of these eigenstates; phase estimation samples information about fractions , from which continued fractions can recover a candidate order under suitable precision and coprimality conditions. Repetition and classical verification are needed; a single sample need not reveal .
Proposition 2.2.6
(Factors from an even order)
Let be coprime to and let be the order of modulo . If is even and , then and are both nontrivial factors of , that is, different from and from .
Proof
(A product divisible by M with no factor divisible by M)
Write and , so is divisible by . Since and is the least positive exponent, ; by hypothesis . Hence and . If , then forces , a contradiction; if , then , also a contradiction. So both gcds lie strictly between and .
Proof X-ray
Where each hypothesis is used
Each hypothesis is used exactly once. Minimality of gives . Evenness is needed so that exists as an integer power. The condition is precisely . The one non-obvious move is the coprimality step: a factor coprime to would force to divide the other factor, which the two hypotheses just listed forbid. Remove the condition and may divide entirely, so the product gives no splitting.
Worked example 2.2.7
(Splitting 15 with the base 2)
The powers of modulo are , so the order is , which is even. Then . Therefore and , and indeed .
Counterexample mode
Not every base splits M
A tempting claim is that every coprime to splits in this way. For and we have , so the order is and . Then and , both trivial. The hypothesis cannot be dropped. Odd orders fail differently: for and the order is , so is not defined. Such bases must be discarded and another base tried.
This is the classical reduction underlying Shor's factoring method, not a claim that every choice of succeeds.
Grover search as rotation
Definition 2.2.8
(Marked and unmarked components)
Suppose a known number of the basis labels are marked, where , and a phase oracle flips the sign exactly on marked labels. Let be the uniform superposition of marked labels and the uniform superposition of unmarked ones. The uniform initial state is
Theorem 2.2.9
(Grover success probability)
In this setting let be one Grover iteration: the sign flip on marked labels followed by . Then , so after iterations the success probability is .
Proof
(Two reflections make a rotation)
The oracle is reflection in the axis, and is reflection in the axis. Both preserve the plane spanned by . In the ordered basis the oracle is , and has matrix with entries , and , so
Applied to this gives . Starting from , induction on gives the stated formula.
Choosing near gives high success probability using oracle calls when . More iterations can decrease success: the rotation overshoots. The bound counts oracle queries, not the cost of implementing the oracle or preparing input data. When or , the two-dimensional formula above needs separate treatment.
Worked example 2.2.10
(Four labels with one marked)
For with one marked label, , so one iteration gives . Measuring then returns the marked label with certainty in this idealized model.
Practice with solutions
Quick check
(Compute and .)
Solution · Answer
; unitarity gives .
Quick check
(In exact phase estimation with three control qubits, what outcome corresponds to eigenvalue ?)
Solution · Answer
The control register before the inverse transform is ; the measured result is binary with certainty.
Quick check
(With and one marked item, what is the success probability after two Grover iterations?)
Solution · Answer
Here , so the probability is . The second iteration has rotated past the optimal point.