Grover's Search Algorithm

Perform unstructured search with a quadratic quantum speedup using Grover's amplitude amplification algorithm.

---

Problem

The Unstructured Search Problem

Given an unstructured database of $N$ items and a function $f:\{0,1,\dots ,N-1\}\to \{0,1\}$ such that $f(w)=1$ for exactly one unknown target $w$ and $f(x)=0$ for all $x\ne w$, the task is to find $w$.

This is one of the most fundamental problems in computer science. The database is unstructured: there is no ordering, indexing, or hash structure to exploit. Each query asks "is item $x$ the target?" and receives a yes/no answer. Without additional information about the data, the only strategy is to test items one at a time.

On a quantum computer, the function $f$ is provided as a black-box oracle -- a unitary operator $U_f$ that can be queried in superposition:

$$U_f|x⟩|q⟩=|x⟩|q\oplus f(x)⟩$$

where $q$ is an oracle qubit. Setting $q=|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ converts this into a phase oracle that marks the target with a $-1$ phase:

$$U_w|x⟩=(-1{)}^{f(x)}|x⟩$$

Classical vs. Quantum Complexity

On a classical computer, with no structure to exploit, you must check items one by one. In the worst case, you check all $N$ items. On average, you find the target after checking half the database:

$$T_{\text{classical}}=\frac{N}{2}=O(N)$$

Grover's algorithm solves this problem on a quantum computer using only:

$$T_{\text{quantum}}=O\left(\sqrt{N}\right)$$

This is provably optimal -- Bennett, Bernstein, Brassard, and Vazirani (1997) proved that no quantum algorithm can solve unstructured search asymptotically faster than $O(\sqrt{N})$. Grover's algorithm therefore achieves the best possible quantum speedup for this problem.

The quantum advantage grows with database size:

$N$ (items)	Classical queries	Quantum queries ($\approx \frac{\pi }{4}\sqrt{N}$)	Speedup
4 ($n=2$)	2	1	2x
8 ($n=3$)	4	2	2x
256 ($n=8$)	128	13	10x
$2^{20}$	524,288	804	652x
$2^{40}$	$\approx 5.5\times {10}^{11}$	$\approx 8.2\times {10}^5$	$\approx \mathrm{670,000}$x

Encoding $N=2^n$ items in $n$ qubits, the complexity comparison becomes:

$$T_{\text{classical}}=O(2^n),T_{\text{quantum}}=O\left(2^{n/2}\right)$$

The speedup is quadratic, exponential in the number of qubits saved. While this is less dramatic than the exponential speedup of Shor's algorithm, Grover's speedup applies to an extremely broad class of problems.

Why Grover's Algorithm Matters

Grover's algorithm is not merely a search tool. It is a general-purpose amplitude amplification subroutine that can be composed with other quantum algorithms:

• Database search. The canonical application: finding a marked record in an unsorted list.
• SAT and constraint satisfaction. Grover's search over all $2^n$ variable assignments provides a quadratic speedup for NP-complete problems like 3-SAT, graph coloring, and N-queens.
• Optimization. Finding the minimum (or maximum) of an unstructured function using quantum exponential searching (Durr-Hoyer algorithm).
• Collision finding. Detecting collisions in hash functions with fewer queries than classically possible.
• Quantum counting. Estimating the number of marked items $M$ by combining Grover iterations with quantum phase estimation.

Amplitude Amplification Intuition

Grover's algorithm works by amplitude amplification. Start with a uniform superposition over all $N$ basis states, then iteratively amplify the amplitude of the target state while suppressing all others. Each Grover iteration rotates the state vector in the two-dimensional subspace spanned by $|w⟩$ and the uniform superposition of non-target states.

The key insight is that two reflections compose to form a rotation:

1. The oracle reflects the state about the non-target superposition $|r⟩$.
2. The diffusion operator reflects the state about the uniform superposition $|s⟩$.
3. The composition of two reflections is a rotation by angle $2\theta$ where $\sin \theta =1/\sqrt{N}$.

After $R$ iterations, the state has been rotated by $2R\theta$ toward $|w⟩$. The optimal number of iterations places the state vector nearly on top of $|w⟩$.

---

Solution

Algorithm Overview

Grover's algorithm proceeds in four phases:

Step 1 -- Initialize

Start with $n$ qubits in the all-zeros state: $|{\psi }_0⟩=|0{⟩}^{\otimes n}$.

Step 2 -- Create Uniform Superposition

Apply a Hadamard gate to every qubit:

$$|{\psi }_1⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩=|s⟩$$

This state has equal amplitude $\frac{1}{\sqrt{N}}$ on every basis state, including the target $|w⟩$.

Step 3 -- Grover Iteration

Each Grover iteration consists of two unitary operations:

3a. Apply the oracle $U_w$. The oracle marks the target by flipping its phase:

$$U_w|x⟩=\{\begin{array}{ll}-|x⟩& \text{if }x=w\\ \phantom{-}|x⟩& \text{if }x\ne w\end{array}$$

This can be written as $U_w=I-2|w⟩⟨w|$. The oracle reflects the state about the hyperplane perpendicular to $|w⟩$.

3b. Apply the diffusion operator $D$. The diffusion operator reflects the state about the mean amplitude:

$$D=2|s⟩⟨s|-I,|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

In practice, $D$ is implemented as $H^{\otimes n}\cdot U_0\cdot H^{\otimes n}$ where $U_0=2|0⟩⟨0|-I$ flips the sign of $|0{⟩}^{\otimes n}$ only. The circuit for $U_0$ is: apply X to every qubit, apply a multi-controlled Z on $|1{⟩}^{\otimes n}$, then apply X to every qubit again.

The combined effect of one iteration is a rotation in the $\{|w⟩,|w^{\perp }⟩\}$ subspace by angle $2\theta$, where $\sin \theta =1/\sqrt{N}$.

Step 4 -- Optimal Iterations and Measurement

After $R$ iterations, the amplitude of $|w⟩$ is $\sin ((2R+1)\theta )$, maximized when:

$$R\approx \frac{\pi }{4\theta }=\frac{\pi }{4\arcsin (1/\sqrt{N})}\approx \frac{\pi }{4}\sqrt{N}$$

The success probability is $P_{\text{success}}={\sin }^2((2R+1)\theta )$. Measure all qubits to obtain $w$ with probability close to 1.

Circuit Structure

The full Grover circuit for $n$ qubits and $R$ iterations has the following structure:

The diffusion operator $D$ decomposes into:

---

Code

2-Qubit Grover's Algorithm (4 items, 1 target)

The simplest non-trivial case: $n=2$, $N=4$, target $|11⟩$. One Grover iteration suffices because $\theta =\arcsin (1/2)=\pi /6$, so one rotation by $2\theta =\pi /3$ brings the state exactly to $|11⟩$. The oracle for $|11⟩$ is simply a CZ gate, which flips the phase of the $|11⟩$ basis state.

from pyqpanda3 import core

# Build the 2-qubit Grover search circuit.
# QProg is the top-level container for quantum operations.
prog = core.QProg()

# Step 1: Create uniform superposition over 4 states (|00>, |01>, |10>, |11>).
# Each state has amplitude 1/sqrt(4) = 0.5.
prog << core.H(0) << core.H(1)

# Step 2: Oracle -- mark |11> with a -1 phase.
# CZ applies a Z gate on qubit 1 conditioned on qubit 0.
# This flips the sign of |11> while leaving all other states unchanged.
prog << core.CZ(0, 1)

# Step 3: Diffusion operator (inversion about the mean).
# Decomposed as: H on all, X on all, CZ (phase flip |00>), X on all, H on all
# Before the X gates, CZ flips |00>. After X gates, this is equivalent
# to flipping |11> in the Hadamard basis, which is the diffusion operator.
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Step 4: Measure both qubits.
prog << core.measure([0, 1], [0, 1])

# Run the circuit.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
print("2-qubit Grover (target |11>):", counts)
# Expected: {'11': ~10000}

Expected output:

2-qubit Grover (target |11>): {'11': 10000}

With $N=4$, one iteration rotates the amplitude to align perfectly with $|11⟩$, giving 100% success probability. This is the only case where Grover's algorithm achieves exactly 1.0.

Searching for a Different 2-Qubit Target

To search for a target other than $|11⟩$, wrap the CZ oracle with X gates on the qubits whose target bit is 0. For example, searching for $|10⟩$:

from pyqpanda3 import core

prog = core.QProg()

# Uniform superposition
prog << core.H(0) << core.H(1)

# Oracle for |10>: X on qubit 1 maps |10> -> |11>, CZ flips |11>, X restores.
prog << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(1)

# Diffusion operator
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Measure
prog << core.measure([0, 1], [0, 1])

machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
print("2-qubit Grover (target |10>):", counts)
# Expected: {'10': ~10000}

Expected output:

2-qubit Grover (target |10>): {'10': 10000}

3-Qubit Grover's Algorithm (8 items, 1 target)

For $n=3$ and $N=8$, the optimal iteration count is:

$$R=\lfloor \frac{\pi }{4\arcsin (1/\sqrt{8})}\rfloor =2$$

We search for $|101⟩$. The oracle flips qubit 1 with X (mapping $|101⟩\to |111⟩$), applies a controlled-controlled-Z (CCZ) using the Toffoli gate conjugated by Hadamard, then undoes the X. The diffusion operator uses the same CCZ pattern.

from pyqpanda3 import core

def oracle_3qubit_target_101(prog):
    """Mark |101> with a phase flip.

    Strategy: X on qubit 1 maps |101> -> |111>, then CCZ on |111>,
    then X on qubit 1 restores the original basis. The CCZ is
    implemented as H(2) + TOFFOLI(0,1,2) + H(2), which converts
    the Toffoli's bit-flip into a phase-flip on the target qubit.
    """
    # X on qubit 1: |101> becomes |111>
    prog << core.X(1)
    # CCZ via H + Toffoli + H on qubit 2
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    # Undo X on qubit 1
    prog << core.X(1)


def diffusion_3qubit(prog):
    """Apply the 3-qubit diffusion operator.

    D = H^3 * X^3 * CCZ * X^3 * H^3
    The CCZ flips the phase of |111>, which corresponds to
    flipping |000> in the Hadamard basis (i.e., D = 2|s><s| - I).
    """
    prog << core.H(0) << core.H(1) << core.H(2)
    prog << core.X(0) << core.X(1) << core.X(2)
    # CCZ via H + Toffoli + H
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    prog << core.X(0) << core.X(1) << core.X(2)
    prog << core.H(0) << core.H(1) << core.H(2)


# Build the full Grover circuit.
prog = core.QProg()

# Uniform superposition over 8 states
prog << core.H(0) << core.H(1) << core.H(2)

# Two Grover iterations
for _ in range(2):
    oracle_3qubit_target_101(prog)
    diffusion_3qubit(prog)

# Measure all qubits
prog << core.measure([0, 1, 2], [0, 1, 2])

# Run the circuit.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
counts = machine.result().get_counts()
success = counts.get("101", 0) / sum(counts.values())
print(f"3-qubit Grover (target |101>): {counts}")
print(f"Success rate: {success:.4f}")
# Expected: success rate ~0.945

Expected output:

3-qubit Grover (target |101>): {'101': 9445, '001': 73, '110': 72, ...}
Success rate: 0.9445

The success rate is ${\sin }^2(5\theta )\approx 0.945$ where $\theta =\arcsin (1/\sqrt{8})\approx 0.3614$ rad, not exactly 1.0 because $R=2$ is slightly below the continuous optimum $R_{\text{opt}}\approx 2.27$.

Building Oracle Circuits for Arbitrary Marked States

A Grover oracle for target $|w⟩=|w_0{w}_1\dots w_{n-1}⟩$ applies $U_w=I-2|w⟩⟨w|$:

1. Apply X to every qubit $i$ where $w_i=0$ (maps $|w⟩$ to $|1{⟩}^{\otimes n}$).
2. Apply a multi-controlled Z gate (phase flip on $|1{⟩}^{\otimes n}$).
3. Undo the X gates from step 1.

This pattern works for any target state:

from pyqpanda3 import core

def build_oracle(n, target_bits):
    """Construct a Grover oracle that marks a specific target state.

    Args:
        n: Number of qubits.
        target_bits: Bitstring of length n, e.g. '101'.

    Returns:
        A QCircuit applying a phase flip on the target state.

    The oracle works by:
    1. Applying X gates to flip 0-bits to 1, mapping |target> -> |11...1>
    2. Applying a multi-controlled Z on |11...1>
    3. Undoing the X gates
    """
    circ = core.QCircuit()

    # Step 1: X on qubits where target bit is '0'
    for i in range(n):
        if target_bits[i] == '0':
            circ << core.X(i)

    # Step 2: Multi-controlled Z on |1...1>
    # For n=1: just Z. For n=2: CZ. For n>=3: H + Toffoli + H.
    if n == 1:
        circ << core.Z(0)
    elif n == 2:
        circ << core.CZ(0, 1)
    else:
        # CCZ via H + Toffoli + H on last qubit
        circ << core.H(n - 1)
        circ << core.TOFFOLI(0, 1, n - 1)
        circ << core.H(n - 1)

    # Step 3: Undo X gates
    for i in range(n):
        if target_bits[i] == '0':
            circ << core.X(i)

    return circ

Building the Diffusion Operator (H-X-MCZ-X-H)

The diffusion operator $D=2|s⟩⟨s|-I$ reflects about the uniform superposition. It decomposes as $H^{\otimes n}\cdot (2|0⟩⟨0|-I)\cdot H^{\otimes n}$, where $2|0⟩⟨0|-I$ is the same structure as the oracle for $|0{⟩}^{\otimes n}$:

def build_diffusion(n):
    """Construct the n-qubit diffusion (inversion-about-mean) operator.

    D = H^n * (2|0><0| - I) * H^n
    where (2|0><0| - I) = X^n * (2|1><1| - I) * X^n

    The multi-controlled Z in the middle flips the phase of |11...1>,
    which after the X gates corresponds to |00...0>.
    """
    circ = core.QCircuit()

    # Apply H to all qubits
    for i in range(n):
        circ << core.H(i)

    # Apply X to all qubits (so |00...0> becomes |11...1>)
    for i in range(n):
        circ << core.X(i)

    # Phase flip on |11...1> (was |00...0> before X gates)
    if n == 1:
        circ << core.Z(0)
    elif n == 2:
        circ << core.CZ(0, 1)
    else:
        # Multi-controlled Z via H + Toffoli + H
        circ << core.H(n - 1)
        circ << core.TOFFOLI(0, 1, n - 1)
        circ << core.H(n - 1)

    # Undo X gates
    for i in range(n):
        circ << core.X(i)

    # Undo H gates
    for i in range(n):
        circ << core.H(i)

    return circ

Computing the Optimal Number of Iterations

The success probability after $R$ iterations is $P(R)={\sin }^2((2R+1)\theta )$ where $\theta =\arcsin (1/\sqrt{N})$. The optimum occurs when $(2R+1)\theta =\pi /2$:

import math

def optimal_grover_iterations(n_qubits, n_targets=1):
    """Compute the optimal number of Grover iterations.

    Args:
        n_qubits: Number of qubits (database size N = 2^n).
        n_targets: Number of marked items (default 1).

    Returns:
        Optimal integer iteration count R.
    """
    N = 2 ** n_qubits
    M = n_targets
    sin_theta = math.sqrt(M / N)

    if sin_theta >= 1.0:
        return 0  # All items marked, no search needed

    theta = math.asin(sin_theta)
    # (2R + 1) * theta ~ pi/2  =>  R ~ pi/(4*theta) - 1/2
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))
    return R

# Show optimal iterations for different database sizes.
print(f"{'n':>3s}  {'N':>8s}  {'theta':>10s}  {'R_opt':>6s}  {'P_success':>10s}")
print("-" * 45)
for n in range(2, 11):
    N = 2 ** n
    theta = math.asin(1.0 / math.sqrt(N))
    R = optimal_grover_iterations(n)
    p_success = math.sin((2 * R + 1) * theta) ** 2
    print(f"{n:3d}  {N:8d}  {theta:10.6f}  {R:6d}  {p_success:10.6f}")

Expected output:

  n         N      theta   R_opt  P_success
---------------------------------------------
  2         4    0.523599       1    1.000000
  3         8    0.361368       2    0.945312
  4        16    0.252680       3    0.961314
  5        32    0.177664       4    0.999024
  6        64    0.125327       6    0.998469
  7       128    0.088659       8    0.999756
  8       256    0.062705      12    0.999407
  9       512    0.044368      17    0.999869
 10      1024    0.031334      25    0.999835

General n-Qubit Grover Search Function

Combining the oracle, diffusion, and iteration count into a single reusable function:

from pyqpanda3 import core
import math


def grover_search(n, target_bits, shots=10000):
    """Run Grover's algorithm for a given number of qubits and target.

    Args:
        n: Number of qubits.
        target_bits: Target bitstring, e.g. '101'.
        shots: Number of measurement shots.

    Returns:
        Dictionary of measurement counts.
    """
    if len(target_bits) != n:
        raise ValueError(
            f"Target length ({len(target_bits)}) must equal n ({n})"
        )

    N = 2 ** n
    theta = math.asin(1.0 / math.sqrt(N))
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

    print(f"  n={n}, N={N}, theta={theta:.4f} rad, R={R} iterations")

    prog = core.QProg()

    # Step 1: Uniform superposition
    for i in range(n):
        prog << core.H(i)

    # Step 2: Grover iterations
    for _ in range(R):
        prog << build_oracle(n, target_bits)
        prog << build_diffusion(n)

    # Step 3: Measure
    prog << core.measure(list(range(n)), list(range(n)))

    # Step 4: Execute
    machine = core.CPUQVM()
    machine.run(prog, shots=shots)

    counts = machine.result().get_counts()
    success = counts.get(target_bits, 0) / shots
    print(f"  Target |{target_bits}> probability: {success:.4f}")
    return counts


# Run examples for different database sizes.
print("=== 2-qubit Grover (target |11>) ===")
grover_search(2, "11")

print("\n=== 3-qubit Grover (target |101>) ===")
grover_search(3, "101")

Expected output:

=== 2-qubit Grover (target |11>) ===
  n=2, N=4, theta=0.5236 rad, R=1 iterations
  Target |11> probability: 1.0000

=== 3-qubit Grover (target |101>) ===
  n=3, N=8, theta=0.3614 rad, R=2 iterations
  Target |101> probability: 0.9453

Multiple Marked Items

When $M$ items are marked, the rotation angle changes to $\sin \theta =\sqrt{M/N}$, and the optimal iterations become $R\approx \frac{\pi }{4}\sqrt{N/M}$. The oracle marks each target independently by chaining phase flips:

from pyqpanda3 import core
import math


def grover_multi_target(n, targets, shots=10000):
    """Grover search with multiple marked targets.

    Args:
        n: Number of qubits.
        targets: List of target bitstrings, e.g. ['010', '110'].
        shots: Number of measurement shots.

    Returns:
        Dictionary of measurement counts.
    """
    N = 2 ** n
    M = len(targets)
    theta = math.asin(math.sqrt(M / N))
    R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

    print(f"  N={N}, M={M} targets, R={R} iterations")

    prog = core.QProg()

    # Uniform superposition
    for i in range(n):
        prog << core.H(i)

    for _ in range(R):
        # Oracle: phase flip each target independently
        for target in targets:
            prog << build_oracle(n, target)
        # Diffusion
        prog << build_diffusion(n)

    prog << core.measure(list(range(n)), list(range(n)))

    machine = core.CPUQVM()
    machine.run(prog, shots=shots)

    counts = machine.result().get_counts()
    success = sum(counts.get(t, 0) for t in targets) / shots
    print(f"  Combined success rate: {success:.4f}")
    print(f"  Individual counts: {dict(sorted(counts.items()))}")
    return counts


print("=== 3-qubit Grover, 2 targets (|010>, |110>) ===")
grover_multi_target(3, ["010", "110"])
# Expected: combined success rate ~1.0, each target ~50%

Expected output:

=== 3-qubit Grover, 2 targets (|010>, |110>) ===
  N=8, M=2 targets, R=1 iterations
  Combined success rate: 1.0000
  Individual counts: {'010': 4985, '110': 5015}

With $M=2$ targets out of $N=8$, we have $\theta =\pi /4$ and one iteration is exactly optimal, giving 100% success with equal probability for each target.

Verifying Amplitude Amplification with State Vector

Inspect the full state vector to see amplitude amplification directly:

from pyqpanda3 import core

# 2-qubit Grover without measurement.
prog = core.QProg()

# Uniform superposition
prog << core.H(0) << core.H(1)

# Oracle: CZ marks |11>
prog << core.CZ(0, 1)

# Diffusion
prog << core.H(0) << core.H(1)
prog << core.X(0) << core.X(1)
prog << core.CZ(0, 1)
prog << core.X(0) << core.X(1)
prog << core.H(0) << core.H(1)

# Run without measurement to get the state vector.
machine = core.CPUQVM()
machine.run(prog, shots=1)
sv = machine.result().get_state_vector()

print("State vector after 1 Grover iteration (2 qubits):")
for i, amp in enumerate(sv):
    bits = format(i, '02b')
    print(f"  |{bits}>: {amp:+.6f}  (prob={abs(amp)**2:.6f})")

# Verify that |11> has near-unit amplitude.
assert abs(sv[3]) > 0.99, "Amplification failed"
print("PASS: |11> has near-unit amplitude.")

Expected output:

State vector after 1 Grover iteration (2 qubits):
  |00>: -0.000000+0.j  (prob=0.000000)
  |01>: -0.000000+0.j  (prob=0.000000)
  |10>: -0.000000+0.j  (prob=0.000000)
  |11>: -1.000000+0.j  (prob=1.000000)
PASS: |11> has near-unit amplitude.

Success Probability vs. Number of Iterations

The success probability $P(R)={\sin }^2((2R+1)\theta )$ oscillates. This example demonstrates that over-iterating reduces performance by sweeping the iteration count for a 3-qubit search:

from pyqpanda3 import core
import math

n = 3
N = 2 ** n
theta = math.asin(1.0 / math.sqrt(N))
target = "111"

print(f"3-qubit Grover (target |{target}>), theta={theta:.4f} rad")
print(f"{'R':>3s}  {'Theory':>10s}  {'Empirical':>10s}")
print("-" * 30)

for R in range(7):
    p_theory = math.sin((2 * R + 1) * theta) ** 2

    prog = core.QProg()
    for i in range(n):
        prog << core.H(i)
    for _ in range(R):
        # Oracle for |111>: no X gates needed since target is all 1s
        prog << core.H(2)
        prog << core.TOFFOLI(0, 1, 2)
        prog << core.H(2)
        # Diffusion
        prog << build_diffusion(n)
    prog << core.measure(list(range(n)), list(range(n)))

    machine = core.CPUQVM()
    machine.run(prog, shots=5000)
    p_emp = machine.result().get_counts().get(target, 0) / 5000

    print(f"{R:3d}  {p_theory:10.6f}  {p_emp:10.4f}")

Expected output:

3-qubit Grover (target |111>), theta=0.3614 rad
  R     Theory   Empirical
------------------------------
  0   0.125000     0.1238
  1   0.781250     0.7827
  2   0.945312     0.9449
  3   0.330078     0.3318
  4   0.330078     0.3291
  5   0.945312     0.9462
  6   0.781250     0.7803

Notice the peak at $R=2$, the drop at $R=3$ (over-rotation), and the periodic recovery. This demonstrates the importance of choosing the correct number of iterations.

Running with Noise Simulation

Real quantum hardware introduces errors. This example simulates Grover's search with depolarizing noise and quantifies the fidelity degradation:

from pyqpanda3 import core
import math

n = 3
target = "111"
N = 2 ** n
theta = math.asin(1.0 / math.sqrt(N))
R = max(1, int(round(math.pi / (4 * theta) - 0.5)))

# Build the Grover circuit.
prog = core.QProg()
for i in range(n):
    prog << core.H(i)
for _ in range(R):
    # Oracle for |111>
    prog << core.H(2)
    prog << core.TOFFOLI(0, 1, 2)
    prog << core.H(2)
    # Diffusion
    prog << build_diffusion(n)
prog << core.measure(list(range(n)), list(range(n)))

# Ideal simulation.
machine = core.CPUQVM()
machine.run(prog, shots=10000)
ideal = machine.result().get_counts()

# Noisy simulation with realistic error rates:
# 1% depolarizing on single-qubit gates (H, X)
# 2% depolarizing on two-qubit gates (CNOT, CZ)
noise = core.NoiseModel()
for q in range(n):
    noise.add_quantum_error(core.depolarizing_error(0.01), core.GateType.H, [q])
    noise.add_quantum_error(core.depolarizing_error(0.01), core.GateType.X, [q])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CNOT, [0, 1])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CZ, [0, 1])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CNOT, [0, 2])
noise.add_quantum_error(core.depolarizing_error(0.02), core.GateType.CZ, [0, 2])

machine2 = core.CPUQVM()
machine2.run(prog, shots=10000, model=noise)
noisy = machine2.result().get_counts()

print(f"Ideal success:  {ideal.get(target, 0) / 10000:.4f}")
print(f"Noisy success:  {noisy.get(target, 0) / 10000:.4f}")
print(f"Fidelity loss:  {(ideal.get(target, 0) - noisy.get(target, 0)) / 10000:.4f}")
# Expected: ideal ~0.945, noisy ~0.82

Expected output:

Ideal success:  0.9453
Noisy success:  0.8214
Fidelity loss:  0.1239

---

Explanation

Geometric Interpretation: Rotation in a 2D Plane

Each Grover iteration performs a rotation in a two-dimensional subspace. Define two orthogonal vectors:

• $|w⟩$: the target state (what we are searching for)
• $|r⟩=\frac{1}{\sqrt{N-1}}\sum _{x\ne w}|x⟩$: the uniform superposition of all non-target states

These two vectors span a 2D subspace of the full $N$-dimensional Hilbert space. The initial uniform superposition can be decomposed as:

$$|s⟩=\frac{1}{\sqrt{N}}\sum _x|x⟩=\sin \theta |w⟩+\cos \theta |r⟩,\theta =\arcsin \left(\frac{1}{\sqrt{N}}\right)$$

The initial angle $\theta$ from $|r⟩$ toward $|w⟩$ is small: for $N=1024$, $\theta \approx 0.031$ rad.

The oracle $U_w=I-2|w⟩⟨w|$ reflects about $|r⟩$. It flips the sign of the $|w⟩$ component while preserving $|r⟩$.

The diffusion operator $D=2|s⟩⟨s|-I$ reflects about $|s⟩$. It inverts all amplitudes about their mean.

Two reflections compose to a rotation by $2\theta$:

$$G=D\cdot U_w=\text{rotation by }2\theta \text{ in the }\{|w⟩,|r⟩\}\text{ plane}$$

After $R$ iterations:

$$G^R|s⟩=\sin ((2R+1)\theta )|w⟩+\cos ((2R+1)\theta )|r⟩$$

Mathematical Derivation of the Rotation Angle

Let us derive the rotation from first principles. The initial uniform superposition is:

$$|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

The projection of $|s⟩$ onto $|w⟩$ gives:

$$⟨w|s⟩=\frac{1}{\sqrt{N}}$$

Define $\theta$ such that:

$$\sin \theta =\frac{1}{\sqrt{N}},\cos \theta =\sqrt{\frac{N-1}{N}}$$

Step 1: Oracle. The oracle reflects about the hyperplane perpendicular to $|w⟩$:

$$U_w|s⟩=|s⟩-2⟨w|s⟩|w⟩=|s⟩-\frac{2}{\sqrt{N}}|w⟩$$

Decomposing in the $\{|w⟩,|r⟩\}$ basis:

$$U_w|s⟩=-\sin \theta |w⟩+\cos \theta |r⟩$$

This is a reflection about $|r⟩$: the $|w⟩$ component has been negated.

Step 2: Diffusion. The diffusion operator reflects about $|s⟩$:

$$D\cdot U_w|s⟩=2⟨s|U_w|s⟩\cdot |s⟩-U_w|s⟩$$

Computing the inner product:

$$⟨s|U_w|s⟩=1-\frac{2}{N}=\frac{N-2}{N}$$

Working through the algebra in the 2D basis, the result after one full iteration is:

$$G|s⟩=\sin (3\theta )|w⟩+\cos (3\theta )|r⟩$$

This confirms that one iteration rotates by $2\theta$ (from angle $\theta$ to $3\theta$). By induction, after $R$ iterations:

$$G^R|s⟩=\sin ((2R+1)\theta )|w⟩+\cos ((2R+1)\theta )|r⟩$$

Optimal Iteration Count Analysis

The success probability is maximized when the state aligns with $|w⟩$:

$$P(R)={\sin }^2((2R+1)\theta )\le 1$$

The maximum is achieved when $(2R+1)\theta =\pi /2$, giving:

$$R_{\text{opt}}=\frac{\pi }{4\theta }-\frac{1}{2}\approx \frac{\pi }{4}\sqrt{N}-\frac{1}{2}$$

Since $R$ must be an integer, we round to the nearest integer and take $max(1,\cdot )$.

$n$	$N$	$\theta$ (rad)	$R_{\text{opt}}$	$P_{\text{success}}$
2	4	0.5236	1	1.0000
3	8	0.3614	2	0.9453
4	16	0.2527	3	0.9613
5	32	0.1777	4	0.9990
8	256	0.0626	12	0.9994
10	1024	0.0313	25	0.9998

For large $N$, $\theta \approx 1/\sqrt{N}$ is small, and the discretization error becomes negligible. The success probability approaches 1 exponentially fast as $N$ grows.

Over-Rotation: Why Too Many Iterations Hurt

Each iteration rotates by a fixed $2\theta$, so the success probability oscillates sinusoidally. Past $R_{\text{opt}}$, the state rotates past the target, reducing the probability.

This has several practical implications:

1. Know $N$ (or $M$) to choose $R$. Without the database size, you risk over- or under-iterating. Quantum counting can estimate the number of marked items.

2. Large $N$ is forgiving. The probability curve is broad near the peak, so being off by $\pm 1$ iteration barely matters when $N$ is large.

3. Variable iteration strategy. If $R$ is unknown, try $R=1,2,4,8,\dots$ and verify the result classically after each attempt. This preserves the $O(\sqrt{N})$ average complexity while handling unknown $M$.

Scaling Analysis

The total gate complexity of one Grover run is $O(n\sqrt{N})$ where $n={\log }_{2}N$:

• Per iteration: $O(n)$ gates for the oracle (X gates + multi-controlled Z) + $O(n)$ gates for the diffusion operator = $O(n)$ gates per iteration.
• Number of iterations: $O(\sqrt{N})$.
• Total: $O(n\sqrt{N})=O(\sqrt{N}\log N)$.

The multi-controlled Z gate itself can be decomposed into $O(n)$ Toffoli gates using $n-2$ ancilla qubits, so the overall circuit uses $O(n\sqrt{N})$ Toffoli gates.

For current quantum hardware, the practical limit is determined by circuit depth and coherence time:

Qubits ($n$)	Grover iterations	Approx. Toffoli count	Feasibility
2-3	1-2	~10	Current hardware
4-5	3-5	~100	Near-term
8-10	12-25	~1000	Fault-tolerant era
20+	800+	~100,000	Far future

Multiple Marked Items Case

With $M$ targets out of $N$ total items, the analysis changes as follows. Define $|W⟩=\frac{1}{\sqrt{M}}\sum _{w\text{ marked}}|w⟩$. Then:

$$|s⟩=\sqrt{\frac{M}{N}}|W⟩+\sqrt{\frac{N-M}{N}}|r⟩=\sin \theta |W⟩+\cos \theta |r⟩$$

where $\sin \theta =\sqrt{M/N}$. The optimal iteration count is:

$$R_{\text{opt}}\approx \frac{\pi }{4}\sqrt{\frac{N}{M}}$$

After $R$ iterations, the probability of measuring any of the $M$ target states is:

$$P_{\text{success}}={\sin }^2((2R+1)\theta )$$

Edge cases:

• $M=N/2$: $\theta =\pi /4$, at most 1 iteration suffices.
• $M>N/2$: search for the $N-M$ non-targets instead and invert.
• $M$ unknown: use quantum counting to estimate $M$ before running Grover.

Amplitude Amplification Generalization

Grover's algorithm is a special case of amplitude amplification (Brassard, Hoyer, Mosca, Tapp, 2000). Given:

• A quantum algorithm $\mathcal{A}$ that prepares a state $|\psi ⟩=\mathcal{A}|0⟩$.
• A "good" subspace with projector $P_{\text{good}}$.

Let $a=⟨\psi |P_{\text{good}}|\psi ⟩$ be the probability of measuring a "good" outcome after one application of $\mathcal{A}$. Classical repetition succeeds after $O(1/a)$ expected trials. Amplitude amplification succeeds after only $O(1/\sqrt{a})$ iterations.

This generalizes Grover's algorithm (where $\mathcal{A}=H^{\otimes n}$, $a=M/N$) to any quantum subroutine. Applications include:

• Monte Carlo estimation. Amplifying the probability of sampling from a desired region.
• Quantum walk search. Speeding up spatial search on graphs.
• Optimization. Boosting the probability of finding a near-optimal solution in variational algorithms.

The iteration count for amplitude amplification is:

$$R_{\text{opt}}=\frac{\pi }{4\arcsin (\sqrt{a})}\approx \frac{\pi }{4\sqrt{a}}$$

Common Pitfalls and Debugging

Pitfall 1: Wrong oracle direction. The oracle must flip the phase of the target state, not of all non-target states. Verify by checking that $U_w|w⟩=-|w⟩$ and $U_w|x⟩=|x⟩$ for $x\ne w$.

Pitfall 2: Forgetting to undo X gates. The oracle pattern is X - MCZ - X. If you forget the second set of X gates, the oracle marks the wrong state and the algorithm fails.

Pitfall 3: Wrong iteration count. Too few iterations = low success probability. Too many = over-rotation. Always compute $R$ from $\theta =\arcsin (\sqrt{M/N})$.

Pitfall 4: Incorrect multi-controlled Z decomposition. For $n\ge 3$, the MCZ is implemented as $H_{\text{last}}\cdot \text{Toffoli}\cdot H_{\text{last}}$. The Hadamard gates convert the Toffoli's bit-flip into a phase-flip. Using the wrong qubit for the Hadamard gives incorrect results.

Pitfall 5: Ignoring global phase. The state vector after Grover may show a global phase of $-1$ on the target state (e.g., $-|w⟩$ instead of $|w⟩$). This is physically meaningless and does not affect measurement probabilities.

Debugging strategy: Start with the 2-qubit case (where the math is exact) and verify you get 100% success. Then scale up to 3 qubits and compare against the theoretical ${\sin }^2((2R+1)\theta )$. Use state vector inspection (machine.result().get_state_vector()) to check amplitudes at intermediate points.

---

Summary

Aspect	Details
Problem	Find a marked item $w$ in an unstructured database of $N=2^n$ items
Quantum speedup	$O(\sqrt{N})$ queries vs. classical $O(N)$
Algorithm	Uniform superposition + repeated (oracle + diffusion) + measurement
Optimal iterations	$R\approx \frac{\pi }{4}\sqrt{N}$ for single target
Oracle	Phase flip on target: $U_w=I-2|w⟩⟨w|$
Diffusion	$D=H^{\otimes n}{X}^{\otimes n}\text{MCZ}{X}^{\otimes n}{H}^{\otimes n}$
Rotation angle	$\theta =\arcsin (1/\sqrt{N})$, each iteration rotates by $2\theta$
Multi-target	$R\approx \frac{\pi }{4}\sqrt{N/M}$ for $M$ targets
Over-iteration	Success probability oscillates; excess iterations reduce performance
Gate complexity	$O(n\sqrt{N})$ total gates per run

See Also

• Deutsch-Jozsa Algorithm -- Another foundational quantum algorithm
• Custom Quantum Gates -- Building oracles and multi-controlled operations
• Bell State Preparation -- Basic entanglement operations
• GHZ State Preparation -- Multi-qubit entanglement
• VQE Tutorial -- Variational algorithms using parameterized circuits
• Noise Characterization -- Modeling and analyzing hardware noise