∑ | Quantum Computing
Chapter 16 / 20

Shor and order finding

Why factoring is linked to periodicity.

1. Core idea

Shor’s factoring method reduces much of the task to finding the multiplicative order r of a modulo N. Modular exponentiation creates periodic structure, and quantum phase estimation extracts information about r. Continued fractions and classical checks then recover factors when conditions are favorable.

2. Mathematical foundation

The notation describes a precise relationship among states, transformations or probabilities. Identify each symbol, check the dimensions of the objects, and distinguish amplitudes from the probabilities produced by a measurement.

3. Worked example

For N=15 and a=2, the powers 2^x mod 15 repeat with period 4. Since 2²±1 give 3 and 5, the classical post-processing succeeds. This arithmetic illustration is not a full Shor circuit.

4. Reasoning flow

  1. Define the initial register and its basis states.
  2. Apply the transformations in their intended order.
  3. Track amplitude magnitudes and relative phases.
  4. Measure in the basis that reveals the desired property.
  5. Interpret the result and check the resource assumptions.

Hands-on activity

Use a two- or three-qubit circuit to model the stated example. The worked calculation above gives a reference against which to check the simulated output.

5. Check your understanding

Practice question

Compute the order of 2 modulo 15 and verify both greatest common divisors.

6. What to watch out for

Ideal-state calculations assume perfect gates and measurements. When assessing an algorithm, separate its mathematical guarantee from the cost of building oracles, preparing inputs, repeating experiments and correcting physical noise.

All chaptersNext chapter →
◈ QubitSemantics Hub