Counsel for the frontier of computation

Q = 64 is below N² = 225. Small registers can work here, but lack the usual general precision guarantee.

This models complete dephasing of the exponent register in its computational basis. Its Fourier outcomes become uniform. Chance samples may still yield factors in these tiny examples; they no longer concentrate near the useful phases.

Changing the instance, register size, or coherence starts a new experiment.

The modular function

The first 16 values of a^x mod N. Equal values label the same state of the output register; their exponent amplitudes can interfere.

The Fourier chart is not a transform of these bar heights. It sums amplitudes within each group of equal function values, then adds the groups’ probabilities.

From a sample to an order

A sample gives y/Q ≈ k/r. Continued fractions produce possible reduced fractions; their denominators may be divisors of r. We keep candidates within half a Fourier bin, combine denominator hypotheses by least common multiples, and test aᴿ mod N = 1. A verified exponent is reduced by removing redundant prime factors to obtain the order r.

This is a bounded teaching implementation for N = 15 and 21. The usual textbook choice N² ≤ Q < 2N² gives Q = 256 and 512 respectively. Finite precision can produce incorrect candidates; the modular check is essential.

Run the experiment to inspect the latest continued fraction.

The ideal distribution

Here f(x) = aˣ mod N, 0 ≤ x < Q, and 0 ≤ z < N. This is the normalized distribution when the output register is ignored, with no postselection. The simulator computes it from f(x), without using a known period. In the dephased model, P(y) = 1/Q.

An even order helps only when aʳᐟ² is a nontrivial square root of 1 modulo N. An odd order or aʳᐟ² ≡ −1 calls for a different base.

Shor’s paper · Order finding explained