One run of Shor's period-finding circuit reveals the period with probability Omega(1/log log N)
ProvedQAlgorithms.DeWolf.shor_periodFindingThe period-finding problem: we are given for which there is an unknown with if and only if .
Let be the power of two with and . Let be the unitary on qubits, with read as an -bit number and written in bits, and let be the quantum Fourier transform on the first register. One run of Shor's algorithm prepares
(one evaluation of and two Fourier transforms) and measures the first register in the computational basis, obtaining . Call good if
Then:
- There are constants and such that for every , every and every as above with period , the outcome is good with probability at least . Hence an expected number of independent runs (each with one evaluation of and two QFTs) produces a good outcome.
- If with , and , then is the only fraction with within distance of , and the denominator of in lowest terms is .
So a good outcome determines : continued-fraction expansion of finds the unique fraction with denominator at most near , and its denominator is the period. This is the quantum core of Shor's factoring algorithm.
Formalization Note The state is the shared shorRunState, with (which gives ) and second register qubits. The intermediate measurement of the second register is omitted: it does not change the distribution of the first register. The probability of a good outcome is the total weight of the basis states whose first register is good. The constants and are quantified before , and . The source's per-run constant is not stated (see notes).
import Definitions.Def_QAlgorithms_Defs_Fourier set_option autoImplicit false
namespace QAlgorithms.DeWolf
open Classical in
/-- de Wolf §5.3, PDF pp.50–53 (unnumbered): Shor's period-finding algorithm. Let
`f : ℕ → {0, …, N − 1}` have period `r ∈ {1, …, N}` (`f(a) = f(b)` iff `a ≡ b mod r`, p.50), let
`q = 2^ℓ` with `N² < q ≤ 2N²` (`ℓ = shorEll N`), and run the circuit of Figure 5.1 once:
`F_q` on the first (`ℓ`-qubit) register of `|0^ℓ⟩|0^n⟩` (`n = ⌈log N⌉`), one application of
`O_f : |a⟩|z⟩ ↦ |a⟩|z ⊕ f(a)⟩`, `F_q` on the first register, and measure the first register,
obtaining `b`. Then:
1. there are constants `C > 0` and `N₀`, independent of `N`, `r`, `f`, such that for all `N ≥ N₀`
the outcome `b` satisfies `|b/q − c/r| ≤ 1/(2q)` for some `c ∈ {0, …, r − 1}` coprime to `r`
with probability at least `C / log log N` (so `O(log log N)` expected repetitions suffice);
2. whenever `|b/q − c/r| ≤ 1/(2q)` with `c` coprime to `r ≤ N`, the fraction `c/r` is the only
fraction with denominator `≤ N` within `1/(2q)` of `b/q`, and its lowest-terms denominator
is `r`. -/
theorem shor_periodFinding :
(∃ C : ℝ, 0 < C ∧ ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → ∀ r : ℕ, 1 ≤ r → r ≤ N →
∀ f : ℕ → ℕ, (∀ a, f a < N) → HasPeriod f r →
C / Real.log (Real.log N) ≤ probEvent (shorRunState N f) fun z =>
∃ c : ℕ, c < r ∧ Nat.Coprime c r ∧
|(bitsToNat z.1 : ℝ) / (2 : ℝ) ^ shorEll N - (c : ℝ) / r| ≤
1 / (2 * (2 : ℝ) ^ shorEll N)) ∧
(∀ N r c b : ℕ, 1 ≤ r → r ≤ N → c < r → Nat.Coprime c r →
|(b : ℝ) / (2 : ℝ) ^ shorEll N - (c : ℝ) / r| ≤ 1 / (2 * (2 : ℝ) ^ shorEll N) →
((c : ℚ) / r).den = r ∧
∀ (p : ℤ) (s : ℕ), 1 ≤ s → s ≤ N →
|(b : ℝ) / (2 : ℝ) ^ shorEll N - (p : ℝ) / s| ≤ 1 / (2 * (2 : ℝ) ^ shorEll N) →
(p : ℝ) / s = (c : ℝ) / r) := by
sorry
end QAlgorithms.DeWolf
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Register sizes. For a natural number :
- is the least with , i.e. with ;
- ;
- is the least with .
Bit strings. A computational-basis label of a -qubit register is a bit string . Its value is , so is the most significant bit. For a natural number , is the -bit string whose value is .
The state. For , the state lives on two registers of and qubits. It is obtained from by applying three operators in order:
- . Here is the Fourier matrix, indexed via the value map :
- The XOR oracle. It maps
where is bitwise XOR. 3. again. This is the forward Fourier matrix both times, not its inverse.
The good event. A basis outcome is a pair . The event says that satisfies: there exists a natural with and
For , the only admissible is . The probability of is the sum, over all outcomes in , of the squared moduli of the amplitudes of . The statement is the conjunction of two claims.
-
Success probability. There exist a real and a natural such that the following holds for:
- every natural ;
- every natural with ;
- every with for all , and with exact period , meaning that for all naturals , .
For all of these,
with natural logarithms. When the left side is , and division by zero is read as ; either way the bound is then trivial. Since is existentially chosen, such may simply be excluded. Because , involves no reduction modulo .
-
Uniqueness of the approximating fraction. Let be any natural numbers with:
- (in particular );
- and ;
- , with and not required to be below .
Then both of the following hold:
- the rational number written in lowest terms has denominator exactly ;
- for every integer and every natural with , if then
as real numbers.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.