SA Shor's Algorithm Simulation

Circuit Diagrams

This file explains the circuit diagrams generated by the repository. It keeps one drawing for each concept:

The oracle decomposition is intentionally tiny. It shows how an oracle can be built from controlled bit flips for a small displayed input register; it is not a scalable modular exponentiation circuit.

Generating Diagrams

Generate the standard circuit diagram set with:

python -m examples.circuit_diagrams_example --N 15 --a 2

or call the module directly:

python -m shors_algorithm_simulation.quantum.circuits --N 15 --a 2 --output-dir images

This creates:

The compact circuit used in the README can be regenerated with:

python -m shors_algorithm_simulation.quantum.quantum_circuit

Register Layout

For an input N, the simulator uses:

n = ceil(log2(N))
period register:  2n qubits
function register: n qubits

The period register needs about N^2 basis states so continued fractions can recover the period from measured values c / Q.

For N = 15:

n = 4
period register = 8 qubits
function register = 4 qubits
total = 12 qubits

High-Level Period-Finding Circuit

The high-level circuit has four stages:

  1. Apply Hadamard gates to the period register.
  2. Apply the modular exponentiation oracle.
  3. Apply inverse QFT to the period register.
  4. Measure the period register.

High-level period-finding circuit for N=15, a=2

This diagram is the main circuit-level view of Shor period finding. The oracle is drawn as one labeled block because a full gate-level modular exponentiation circuit would be much larger than the rest of the diagram.

Hadamard Layer

The period register starts in |0⟩. Applying Hadamards creates:

(1 / sqrt(Q)) sum_x |x⟩|0⟩

This is the equal superposition over all candidate exponents x. In the high-level diagram, this is the row of H gates at the start of the period register.

Inverse QFT Gate Composition

The inverse QFT acts only on the period register. It converts periodic structure in the amplitudes into peaks in the measured first-register states.

Likely measurements satisfy:

c / Q ~= s / r

where r is the period and s is an integer.

The diagram below expands a 4-qubit inverse QFT into swaps, controlled phase rotations, and Hadamard gates:

Inverse QFT decomposition

The full simulator may use more first-register qubits. This 4-qubit drawing is included because the gate pattern is readable and scales by repeating the same controlled-phase structure.

Explicit Oracle Gate Composition

The oracle encodes:

f(x) = a^x mod N

The matrix-mode oracle uses the reversible XOR form:

|x⟩|y⟩ -> |x⟩|y xor (a^x mod N)⟩

For a tiny displayed exponent register, this can be decomposed as a truth table. For each displayed x, the circuit toggles the output bits that are 1 in a^x mod N, using multi-controlled X gates.

For N=15, a=2, and a 2-qubit displayed exponent register:

x = 0 -> 2^0 mod 15 = 1  -> toggle output bit 0
x = 1 -> 2^1 mod 15 = 2  -> toggle output bit 1
x = 2 -> 2^2 mod 15 = 4  -> toggle output bit 2
x = 3 -> 2^3 mod 15 = 8  -> toggle output bit 3

Explicit oracle decomposition for N=15, a=2

This is an explicit gate composition, but only for the small displayed truth table. The full Shor modular exponentiation oracle for large registers would require a much more elaborate arithmetic circuit.

Matrix Mode and Distribution Mode

Both simulator modes correspond to the high-level period-finding circuit.

The separate matrix/distribution block diagrams are not repeated here because they differ mostly in labels and qubit count. The important structural circuit is the high-level period-finding diagram above.

References