Order Finding

Find when modular multiplication repeats

Order finding asks how many times a number must be multiplied by itself before its remainder returns to one. For integers a and N with no common factor, the order r is the smallest positive integer satisfying a to the power r congruent to one modulo N. Quantum order finding turns this repetition into an eigenphase-estimation problem.

Review phase estimation and the QFT. The classical prerequisites are modular arithmetic, greatest common divisors and fractions. You do not need advanced number theory to follow the small example; the important step is separating the quantum phase sample from the classical recovery and verification of r.

WORKED DIAGRAM · A13Order of two modulo fifteen

The order is four. A sample 1/2 has reduced denominator two and is insufficient by itself; checking 2² mod 15=4 detects the wrong candidate.

The contract

The inputs a and N are ordinary classical integers with greatest common divisor one. The desired output is the smallest positive order r. The quantum procedure uses reversible modular multiplication on a register holding remainders. The relevant unitary maps y to a times y modulo N on valid residue labels, with a reversible extension on any unused computational-basis labels.

Because a is coprime to N, multiplication permutes the residues and is invertible. If the common divisor were greater than one, that permutation construction would fail, but in factoring the divisor would already be useful classical information. Check the coprimality condition before applying the quantum subroutine.

The access model is more concrete than an arbitrary truth-table oracle: modular powers can be computed by structured arithmetic. A full algorithm must implement that arithmetic reversibly, account for workspace and uncompute temporary information. The quantum register width alone does not determine its gate cost.

Worked example: powers of two modulo fifteen

The sequence begins one, two, four, eight, then one again. The order is four. Define U to multiply by two modulo fifteen. On the orbit containing one, U cycles through four basis states. Linear combinations of those orbit states form eigenstates with eigenvalues corresponding to the four quarter-turn phases.

The easy-to-prepare basis state one is an equal superposition of those four eigenstates. Phase estimation therefore samples phases zero, one quarter, one half and three quarters with equal probability in an exactly resolved ideal example. If the counting grid has eight points, the numeric labels are zero, two, four and six.

The one-quarter sample has reduced denominator four, suggesting r equal to four. The three-quarter sample does too. The one-half sample has denominator two, which is only a divisor of the true order. Checking two squared modulo fifteen gives four, not one, so two is not an acceptable final answer. The zero sample gives no useful denominator for this run. Repetition and classical reconstruction are essential parts of the procedure.

Why the phases encode the order

On a cycle of length r, the modular multiplication operator is a cyclic shift. Its eigenvectors are Fourier combinations around that cycle, and their eigenvalues are exp of two pi i j over r for j from zero to r minus one. Preparing the orbit’s first basis state gives overlap with all those eigenvectors.

QPE samples an approximation to j over r. If j and r are coprime and the approximation is sufficiently precise, continued fractions can recover the reduced denominator r. If they share a factor, the reduced denominator can be smaller. Combining information from runs and verifying candidate orders addresses that issue. The algorithm learns a period through a spectrum, not by waiting for a measured trajectory to complete r physical steps.

Recover a rational number carefully

Continued fractions express a real approximation through simple rational convergents. In order finding, the denominator is known to be bounded by N, and sufficiently accurate phase estimation makes the relevant rational distinguishable. A familiar sufficient closeness scale is less than one over twice the square of the true denominator. This explains why the counting precision grows with the bit-length of N.

The measured grid value is not always exactly j over r. For an order such as six, fractions like one sixth cannot be represented exactly by a power-of-two grid. The output distribution concentrates near them, and the classical rational reconstruction uses that approximation. A tiny textbook instance whose period divides the grid hides this important finite-resolution step.

Do not simply take the denominator of the raw binary-grid fraction. That denominator is usually a power of two chosen by the experiment, not the unknown order. Continued fractions search for a nearby small-denominator rational, and modular exponentiation verifies whether a proposed period actually returns one.

Implement controlled powers efficiently

Canonical QPE calls for U raised to powers of two. Repeating a base multiplication that many times would suggest an exponential circuit. Instead, compute constants a raised to those powers modulo N classically by repeated squaring, then build controlled modular multiplication by each constant. The arithmetic has structure that permits polynomial-size reversible implementations in the input bit-length.

This is a crucial example of an algorithm-specific power shortcut. General phase estimation does not guarantee cheap access to every high power of an arbitrary unitary. Order finding supplies a mathematical representation that makes the required powers efficient. Its advantage depends on that structure and on reliable execution of the arithmetic, not only on a Fourier transform.

Complexity and interpretation

The input size is the number of bits needed for N, not the magnitude of N. Quantum order finding has polynomial algorithmic cost in that bit-length using appropriate arithmetic and sufficient precision. Physical resource estimates add error correction, gate synthesis, timing and success amplification. Those additions are major engineering questions for cryptographically sized numbers.

This subroutine returns an order, not automatically a factor. Shor’s factoring reduction uses a suitable even order and greatest-common-divisor calculations to obtain factors. Some choices of a are unhelpful, so the larger factoring algorithm includes classical preprocessing and repetition. Keeping the subroutine contract narrow makes the overall proof easier to follow.

Exercises

1. Compute the order of two modulo seven by listing successive powers. Does the order have to be even?

2. In the fifteen example, QPE returns a phase of one half. Why is reporting order two immediately incorrect, and what verification detects the problem?

Worked answers

1. The powers are two, four and one modulo seven, so the order is three. Orders need not be even. Factoring reductions therefore have conditions beyond merely obtaining some order.

2. The reduced denominator can be a divisor of the true order when the sampled numerator shares a factor with it. Two squared modulo fifteen is four, so the candidate fails the defining order condition. Another run yielding one quarter or three quarters reveals denominator four, which passes verification.

Sources

Shor’s original paper develops the polynomial-time arithmetic and factoring framework. IBM’s Shor lesson explains order finding through phase estimation and classical reconstruction.

Check your understanding

PAUSE & THINK

QPE returns phase 1/2 for the order of two modulo fifteen. Why must denominator two be checked?

Choose your answer

It may be only a divisor of the true orderEvery measured phase is exact zeroAn order cannot be even

Check my answer

Answer: It may be only a divisor of the true order. The sampled numerator and true order can share a factor. Two squared is four modulo fifteen, so order two fails verification; the true order is four.