Grover Search: Phase Oracle and Diffusion Operator

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

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

make_phase_oracle(marked_bits: Sequence[int]) -> coherent function

Arguments:

marked_bits — a sequence of 0s and 1s, 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⟩.

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.

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.

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.

Write the Grover step

Combine the oracle and diffusion into a single step using @parametric (required for use inside @adaptive).

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)

Write the full search circuit

Use @adaptive to create a circuit that prepares a uniform superposition, runs 2 Grover iterations, and measures.

@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)

Build and run on Qiskit

Compile to a Qiskit QuantumCircuit and run.

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)

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:

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)

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.

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:

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)

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.

Get Started

Core Concepts

Guides

Algorithm Zoo

Grover Search: Phase Oracle and Diffusion Operator

Imports

Phase oracle

Diffusion operator

Complete example: Grover search on 2 qubits

Using zoo components directly

Scaling to more qubits

​Imports

​Phase oracle

​Diffusion operator

​Complete example: Grover search on 2 qubits

​Using zoo components directly

​Scaling to more qubits

Imports

Phase oracle

Diffusion operator

Complete example: Grover search on 2 qubits

Using zoo components directly

Scaling to more qubits