Results on exact circuits, the phase transform, the order trial, primality, the factoring process and deferred filters, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

Reversible evaluation — Lemma 2.1. A Boolean circuit with s gates for f: {0,1}^m -> {0,1}^k gives a circuit of at most 4s + k gates from NOT, CNOT and Toffoli mapping |x, 0^s, z> to |x, 0^s, z xor f(x)>. No hypothesis.
Unrolling a Turing machine computation — Lemma 2.2. A function computed by a Turing machine within T steps has a Boolean circuit of at most c(T+1)^2 gates, written down in time polynomial in m + T. No hypothesis.
Exact dyadic sampling — Lemma 3.1. A flag that is 1 with probability exactly A/2^T, computed from a classical label in polynomial time, is appended by a polynomial-size circuit over the fixed gate set. No hypothesis.
Retained records — Lemma 3.2. A procedure of polynomially many gates chosen by classical data, measurements and classical computations is a polynomial-size uniform circuit over the gate set with the same distribution of its classical data; its inverse is a circuit over the gate set. No hypothesis.
One step of amplification — Lemma 4.1. If |Pi psi|^2 = 1/4 for psi = V|0>, then (2|psi><psi| - I)(I - 2 Pi) psi = 2 Pi psi, a unit vector in the range of Pi. No hypothesis.
Exact quantum factoring (OpenAI) — Theorem 5.1. A polynomial-time uniform family of polynomial-size circuits over one fixed finite gate set outputs the complete prime factorization of every N >= 2 with probability one; proved in the sixth lesson. No hypothesis.
Overlaps of the phase register — Lemma 2.1. For every integer D, <chi|T_D|chi> = g(D/Q), where g interpolates exp(-2 pi i z) linearly between the quarter-integers. No hypothesis.
A transform with a piecewise-linear phase — Lemma 3.1. A circuit over the gate set of size polynomial in b has the matrix Q^(-1/2) g(kx/Q), Q = 2^b, on a designated success outcome of its auxiliary qubits. No hypothesis.
Recovering labels — Lemma 4.2. For Q = B^16 the bins k(d,j) of the reduced fractions j/d with d < B are distinct, and continued fractions decide in polynomial time whether a given k is such a bin and find (d,j). No hypothesis.
Order sampling with the transform — Proposition 5.1. At the true order r, the probability of success and output k(r,j) is the sum over t < r of P(r,j,t). No hypothesis.
Residue-class sums — Lemma 1.3. P(d,j,t) is a dyadic rational computable in polynomial time, |P(d,j,t) - J(jt mod d)| <= 32/Q, and 1/(8d) <= |I(u)| <= 1/d. No hypothesis.
A dyadic majorant with an exact sum — Lemma 2.1. There are dyadic U(d,j,u) with 0 <= U(d,j,jt mod d) - P(d,j,t) <= 128/Q and 1/(128d) <= S(d,j) <= 2, where S(d,j) is half their sum and is computed in polynomial time without enumerating the d terms. No hypothesis.
An order trial with prescribed probability (OpenAI) — Proposition 3.1. A uniform quantum trial of polynomial cost returns no candidate or a multiple d < B of the order r of a unit, and returns d = r with probability exactly phi(r) 2^(-ceil(log2 r) - 10), without using r. No hypothesis.
A deterministic primality test — Theorem 1.1. A deterministic algorithm decides whether 2 <= m < 2^n is prime in a number of bit operations polynomial in n >= 128, with the congruences (X + a)^m = X^m + a modulo m and X^s - 1 for a prime s <= n^8 and 1 <= a <= 8s. No hypothesis.
An auxiliary prime — Lemma 2.1. For n >= 128 and 2 <= m < 2^n there is a prime s <= n^8 not dividing m with ord_s(m) > n^2. No hypothesis.
Composites fail the test — Proposition 3.2. The test rejects every composite m: the values at a root of unity of order s of products of the tested linear factors would be at least 8^(h-1) and fewer than 2^(2h) in number. No hypothesis.
Orders from factorizations — Lemma 1.2. Given the factorization of phi(m), the order of a unit modulo m and its factorization are computed with fewer than 2n modular powerings. No hypothesis.
Unequal two-adic levels are frequent — Lemma 2.2. For odd m with at least two prime factors, the units whose orders at the prime-power components have unequal 2-adic valuations number F(m) = phi(m) - sum_t prod_i c_i(t) >= phi(m)/2. No hypothesis.
Splitting by the order — Lemma 2.3. For a unit a with unequal levels and order r, r is even and gcd(a^(r/2) - 1, m) is a divisor of m other than 1 and m. No hypothesis.
A factoring process with verifiable transition probabilities (OpenAI) — Proposition 4.1. A process with exactly L = n^10 transition slots either aborts or generates the occurrence tree D(N); from D(N) one computes for every transition a test for good outputs, a canonical output and the exact dyadic probability s >= 1 - 2^(-2n) of a good output; good outputs always complete the run. No hypothesis.
Dyadic completion — Lemma 1.1. A transition with good-output probability s is filtered, with a rare uniform guess that must equal one good output, to pass with any dyadic probability z <= (1 - delta)s exactly. No hypothesis.
Known probability from deferred filters (OpenAI) — Proposition 2.1. A polynomial-size preparation succeeds with probability exactly (1 - 2^(-n))^(n^10) and outputs the prime factorization of N on success. No hypothesis.
A quarter of success — Lemma 3.1. A polynomial-size uniform circuit has success probability exactly 1/4 and holds the prime factorization of N in its output register on every successful branch. No hypothesis.

Reading order

Six lessons. The first fixes the model (gates, uniform circuits, reversible computation, exact dyadic sampling, retained records, one amplification step) and states the theorem; the second and third build the order trial; the fourth proves the primality test, which is classical and can be read on its own; the fifth builds the factoring process; the sixth proves the theorem. Everything used is proved in the course, apart from linear algebra over the complex numbers and the elementary algebra of the core courses Abstract Algebra I and II.