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

# Grover Search: Phase Oracle and Diffusion Operator

> Build certified-safe Grover search circuits using the b01t zoo's phase oracle and diffusion operator, composable as standard @coherent building blocks.

Grover's algorithm finds a marked item in an unstructured database of N entries in O(√N) queries, compared to O(N) for a classical linear scan. In b01t, the algorithm is split into two reusable `@coherent` components — a phase oracle that marks your target state with a −1 phase, and a diffusion operator that amplifies its amplitude. Both are structurally safe: ancilla qubits are allocated and fully uncomputed through the `compute`/`phase`/`uncompute` discipline.

## Imports

```python theme={null}
from b01t.zoo.grover import make_phase_oracle, phase_oracle, diffusion_operator
```

* `make_phase_oracle` — factory function that returns a `@coherent` oracle for any target bit pattern
* `phase_oracle` — pre-built oracle for the 2-qubit `|11⟩` state (equivalent to `make_phase_oracle([1, 1])`)
* `diffusion_operator` — `@coherent` Grover diffusion operator (works on any register width)

## Phase oracle

The phase oracle flips the sign of the marked basis state. You describe the target as a sequence of bits, one per qubit — `1` for qubits that must be `|1⟩` and `0` for qubits that must be `|0⟩`.

```python theme={null}
make_phase_oracle(marked_bits: Sequence[int]) -> coherent function
```

**Arguments:**

* `marked_bits` — a sequence of `0`s and `1`s, one element per qubit. Must have at least one element. All entries must be `0` or `1`.

**Returns:** a `@coherent` function `oracle(sys: QReg)` that applies the phase flip to `|marked_bits⟩`.

**Implementation details:**

* For a 1-qubit register: applies `Z` directly (wrapping with `X`/`X` if `marked_bits[0] == 0`).
* For 2+ qubits: copies system bits into a 1-qubit ancilla via `MCX` (inside a `compute` block), applies `Z` via phase kickback, then uncomputes. The ancilla is always returned to `|0⟩`.

```python theme={null}
from b01t.zoo.grover import make_phase_oracle

# Mark the state |101> on a 3-qubit register
oracle_101 = make_phase_oracle([1, 0, 1])

# Mark the state |00> on a 2-qubit register
oracle_00 = make_phase_oracle([0, 0])

# Use the pre-built |11> oracle directly
from b01t.zoo.grover import phase_oracle  # equivalent to make_phase_oracle([1, 1])
```

## Diffusion operator

The diffusion operator implements the inversion-about-average step: `2|s⟩⟨s| − I` where `|s⟩` is the uniform superposition. It works on any register width.

```python theme={null}
diffusion_operator(sys: QReg)
```

**Signature:** `@coherent` function, takes a single `QReg` of any width.

**Implementation:**

* Applies `H` then `X` on every qubit.
* Applies a multi-controlled-Z (using `CZ` for 2 qubits, or `MCX`+`CZ`+uncompute for 3+, all ancilla-clean).
* Applies `X` then `H` on every qubit.

```python theme={null}
from b01t import QReg, coherent
from b01t.zoo.grover import phase_oracle, diffusion_operator

@coherent
def my_step(sys: QReg):
    phase_oracle(sys)       # mark the target
    diffusion_operator(sys) # amplify
```

## Complete example: Grover search on 2 qubits

This example mirrors the `demos/grover_search/search.py` demo. It searches for `|11⟩` in a 2-qubit space with 2 Grover iterations, which is the optimal number for N=4.

<Steps>
  <Step title="Write the Grover step">
    Combine the oracle and diffusion into a single step using `@parametric` (required for use inside `@adaptive`).

    ```python theme={null}
    from b01t import QReg, parametric, h, x, measure_all, adaptive, repeat
    from b01t import ancilla, compute, phase, uncompute
    from b01t import ccx, z, mcx, cz

    @parametric
    def grover_step(sys: QReg):
        # Oracle: mark |11>
        with ancilla(1) as anc:
            compute(lambda: ccx(sys[0], sys[1], anc[0]))
            phase(lambda: z(anc[0]))
            uncompute()
        # Diffusion: H-X-MCZ-X-H
        for q in sys:
            h(q)
            x(q)
        with ancilla(1) as anc:
            compute(lambda: mcx(sys.wires()[:-1], anc[0]))
            phase(lambda: cz(anc[0], sys[-1]))
            uncompute()
        for q in sys:
            x(q)
            h(q)
    ```
  </Step>

  <Step title="Write the full search circuit">
    Use `@adaptive` to create a circuit that prepares a uniform superposition, runs 2 Grover iterations, and measures.

    ```python theme={null}
    @adaptive
    def grover_search(sys: QReg):
        # Uniform superposition
        for q in sys:
            h(q)
        # Two Grover iterations
        repeat(2, lambda: grover_step(sys))
        return measure_all(sys)
    ```
  </Step>

  <Step title="Build and run on Qiskit">
    Compile to a Qiskit `QuantumCircuit` and run.

    ```python theme={null}
    from b01t import QiskitBackend

    prog = grover_search.build(("sys", 2))
    backend = QiskitBackend()
    qc = backend.emit(prog)

    from qiskit import transpile
    from qiskit_aer import AerSimulator

    sim = AerSimulator()
    result = sim.run(transpile(qc, sim), shots=1024).result()
    print(result.get_counts())
    # Expect '11' to dominate (probability ~1.0 after 2 iterations on N=4)
    ```
  </Step>
</Steps>

## Using zoo components directly

If you prefer to use the zoo's `make_phase_oracle` and `diffusion_operator` directly rather than inlining gate sequences, you can call them inside a `@coherent` host:

```python theme={null}
from b01t import QReg, coherent, h, measure_all, adaptive, repeat
from b01t.zoo.grover import make_phase_oracle, diffusion_operator

oracle = make_phase_oracle([1, 1])  # marks |11>

@coherent
def grover_step(sys: QReg):
    oracle(sys)
    diffusion_operator(sys)

@adaptive
def grover_search(sys: QReg):
    for q in sys:
        h(q)
    repeat(2, lambda: grover_step(sys))
    return measure_all(sys)
```

<Note>
  The `@coherent` decorator cannot be used directly inside `@adaptive`. Wrap your `@coherent` Grover step in a `@parametric` function, or inline the gate sequences as shown in the full example above.
</Note>

## Scaling to more qubits

`make_phase_oracle` and `diffusion_operator` both scale to any number of qubits. For `n` qubits you typically want `⌊π/4 · √(2^n)⌋` iterations:

```python theme={null}
import math
from b01t import QReg, coherent, adaptive, h, measure_all, repeat
from b01t.zoo.grover import make_phase_oracle, diffusion_operator

n = 4
target = [1, 0, 1, 1]  # search for |1011>
oracle = make_phase_oracle(target)

@coherent
def step(sys: QReg):
    oracle(sys)
    diffusion_operator(sys)

num_iters = max(1, int(math.pi / 4 * math.sqrt(1 << n)))

@adaptive
def search(sys: QReg):
    for q in sys:
        h(q)
    repeat(num_iters, lambda: step(sys))
    return measure_all(sys)
```

<Tip>
  For multi-qubit oracles, b01t allocates exactly one ancilla qubit via `compute`/`phase`/`uncompute` — the circuit width grows by only 1 qubit regardless of `n`.
</Tip>