Grover's Algorithm

Integer factorization via quantum amplitude amplification on Dynex

Grover’s Algorithm on Dynex

Grover’s algorithm provides a quadratic speedup for unstructured search problems. On Dynex, it is implemented as a quantum gate circuit using PennyLane and can be used for integer factorization, database search, and optimization.

How it works

1. Hadamard gates create superposition over all candidate states in wires_p and wires_q (representing prime factor candidates)
2. Multiplication function uses the QFT and controlled phase rotations (Kfourier) to compute p × q, storing the result in wires_solution
3. FlipSign operator marks the target state (the correct factorization)
4. Grover operator performs amplitude amplification, iteratively increasing the probability of measuring the correct factors
5. The circuit returns probabilities of each factor combination

Implementation

import pennylane as qml
import numpy as np
from dynex import DynexConfig, ComputeBackend, DynexCircuit

def kfourier(value, wires):
    """Apply phase rotations for QFT-based multiplication."""
    for i, wire in enumerate(wires):
        qml.PhaseShift(value * np.pi / (2**i), wires=wire)

def flip_sign(state, wires):
    """Mark the target state with a phase flip."""
    for i, wire in enumerate(wires):
        if not (state >> i & 1):
            qml.PauliX(wires=wire)
    qml.ctrl(qml.PauliZ, control=wires[:-1])(wires=wires[-1])
    for i, wire in enumerate(wires):
        if not (state >> i & 1):
            qml.PauliX(wires=wire)

def grover_circuit(params):
    n = int(params[0])  # Number to factorize
    bits = int(np.ceil(np.log2(n + 1)))

    wires_p = list(range(bits))
    wires_q = list(range(bits, 2 * bits))
    wires_solution = list(range(2 * bits, 2 * bits + 2 * bits))

    # Step 1: Superposition over candidate factors
    for wire in wires_p + wires_q:
        qml.Hadamard(wires=wire)

    # Step 2: QFT on solution register
    qml.QFT(wires=wires_solution)

    # Step 3: Grover iterations
    iterations = int(np.floor(np.pi / 4 * np.sqrt(2**bits)))
    for _ in range(iterations):
        # Oracle: mark correct factorization
        flip_sign(n, wires_solution)
        # Diffusion: amplitude amplification
        for wire in wires_p + wires_q:
            qml.Hadamard(wires=wire)
        flip_sign(0, wires_p + wires_q)
        for wire in wires_p + wires_q:
            qml.Hadamard(wires=wire)

    return qml.probs(wires=wires_p + wires_q)

# Factorize n=15
config = DynexConfig(
    compute_backend=ComputeBackend.QPU,
    qpu_model='apollo_rc1'
)
circuit = DynexCircuit(config=config)

probs = circuit.execute(
    grover_circuit,
    params=[15],
    wires=12,
    method='probs'
)

# Find highest probability factors
best_idx = np.argmax(probs)
bits = 4
p = best_idx >> bits
q = best_idx & ((1 << bits) - 1)
print(f"Most likely factors of 15: {p} × {q} = {p*q}")

Results

Grover’s algorithm concentrates probability amplitude on the correct factor pairs. For N=15:

Factor pair	Expected probability
3 × 5	High (~0.5)
5 × 3	High (~0.5)
Others	Near zero

Full notebook

circuit_example_grover.ipynb