> ## Documentation Index
> Fetch the complete documentation index at: https://dynex.mintlify.app/llms.txt
> Use this file to discover all available pages before exploring further.

# Shor's Algorithm

> Period-finding for efficient integer factorization on Dynex

# Shor's Algorithm on Dynex

[Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_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

```python theme={null}
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](https://github.com/Dynex-Development/awesome-dynex/blob/main/quantum_circuits/circuit_example_shor.ipynb)