Shor's Algorithm

Period-finding for efficient integer factorization on Dynex

Shor’s Algorithm on Dynex

Shor’s algorithm factorizes integers exponentially faster than the best known classical algorithm. It reduces factorization to period finding using the quantum Fourier transform.

How it works

1. Quantum state preparation — superposition via Hadamard gates on estimate qubits; target qubit initialized to |1⟩ via Pauli-X
2. Controlled unitaries — powers of modular exponentiation unitary U_NA (from integers a and N) applied to target qubits, controlled by estimate qubits
3. Inverse QFT — extracts phase information related to the period r of f(x) = a^x mod N
4. Measurement — samples encode period information
5. Post-processing — continued fractions + GCD to extract prime factors from period r

Example: Factorize N=35

import pennylane as qml
import numpy as np
from fractions import Fraction
from math import gcd
from dynex import DynexConfig, ComputeBackend, DynexCircuit

N = 35   # Number to factorize
a = 12   # Randomly chosen base (gcd(a, N) == 1)

def build_U_NA(a, N, wires):
    """Construct controlled modular exponentiation matrix."""
    dim = 2 ** len(wires)
    U = np.eye(dim, dtype=complex)
    for x in range(dim):
        y = pow(a, x, N)
        U[x, x] = 0
        U[y, x] = 1
    return U

def shor_circuit(params):
    n_estimate = 8   # Qubits for period estimation
    n_target = 1

    estimate_wires = list(range(n_estimate))
    target_wires = [n_estimate]

    # Initialize target qubit to |1⟩
    qml.PauliX(wires=target_wires[0])

    # Superposition on estimate qubits
    for wire in estimate_wires:
        qml.Hadamard(wires=wire)

    # Controlled modular exponentiation
    for i, wire in enumerate(estimate_wires):
        power = 2 ** i
        U = build_U_NA(pow(a, power, N), N, target_wires)
        qml.ctrl(qml.QubitUnitary, control=wire)(U, wires=target_wires)

    # Inverse QFT on estimate register
    qml.adjoint(qml.QFT)(wires=estimate_wires)

    return qml.sample(wires=estimate_wires)

config = DynexConfig(
    compute_backend=ComputeBackend.QPU,
    qpu_model='apollo_rc1'
)
circuit = DynexCircuit(config=config)
sample = circuit.execute(shor_circuit, params=[], wires=9, method='measure')

# Post-process: find period via continued fractions
measured = int(''.join(str(int(b)) for b in sample), 2)
phase = measured / (2 ** 8)
frac = Fraction(phase).limit_denominator(N)
r = frac.denominator

# Extract factors
if r % 2 == 0:
    factor1 = gcd(pow(a, r//2) - 1, N)
    factor2 = gcd(pow(a, r//2) + 1, N)
    print(f"N={N} = {factor1} × {factor2}")

Full notebook

circuit_example_shor.ipynb