Grover's Search

Quantum Search

Grover's algorithm searches an unsorted database of $N$ items in $O(sqrt{N})$ steps — a quadratic speedup over classical $O(N)$ linear search.

The algorithm works on a uniform superposition of all $N$ states and amplifies the amplitude of the target state through two operations:

1. Oracle — Flips the phase of the target state (marks it):

def oracle(state, target):
    result = state[:]
    result[target] = -result[target]
    return result

2. Diffusion — "Inversion about the mean" — amplifies the marked state:

def diffusion(state):
    n = len(state)
    avg = sum(state) / n
    return [2 * avg - a for a in state]

For $N = 4$ states, one iteration is enough to find the target with certainty:

import math

state = [0.5, 0.5, 0.5, 0.5]  # Uniform superposition
state = oracle(state, 2)        # Mark target = 2
state = diffusion(state)        # Amplify
# → [0.0, 0.0, 1.0, 0.0] — target found!

Your Task

Implement oracle(state, target) and diffusion(state). Then run Grover's search and print the amplitudes.