10.5 Eigenvalue and phase estimation

The next tool we need for Shor’s factoring algorithm is a way to estimate the eigenvalues of a special unitary operation we construct.

Let U be an n-by-n square matrix with complex entries. From section 5.10, the solutions λ of the equation algorithm$phase estimation

are the eigenvalues {λ₁, …, λ_N} of U. Some of the λ_j may be equal. If a particular eigenvalue λ_j shows up k times among the N values, we say λ_j has multiplicity k. multiplicity

Each eigenvalue λ_j corresponds to an eigenvector v_j so that

We can take each v_j to be a unit vector. When U is unitary, each λ_j is a complex unit.

We have so far represented an eigenvalue λ of a unitary matrix as e^φi with 0 ≤ φ < 2π. We now, instead, think of the eigenvalue as e^2πφi with 0 ≤ φ < 1.

This change allows...