> ## 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.

# Grover's Algorithm

> Integer factorization via quantum amplitude amplification on Dynex

# Grover's Algorithm on Dynex

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

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