Skip to main content

​
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