Finding a Needle in a Haystack: Simulating Grover's Search Algorithm

Project Overview:

Imagine searching for one specific name in an unsorted phone book with a million entries. Classically, in the worst case, you might have to check every single entry, one by one. Grover's algorithm is a quantum search method that can find the right answer using roughly the square root of that many steps instead, a real and provable speedup, not just theoretical hype. In this project, you will build a small quantum circuit using Qiskit that searches a tiny "database" of 4 possibilities and finds the correct one in a single step, then see why this scales into a genuine advantage as the search space grows.

Materials Required:

A computer with internet access

A free Google account, to use Google Colab, no installation needed

Basic comfort reading Python

Background: How Grover's Algorithm Actually Works

Think of your search space as a set of boxes, and only one box has the prize inside. A classical computer has to open boxes one at a time, checking each one, until it finds the right box. On average this takes many tries.

Grover's algorithm instead puts a quantum system into a superposition where it is examining all boxes at once. It then applies two repeating steps. The first step, called the oracle, marks the correct answer by flipping its sign, without revealing which one it is. The second step, called amplitude amplification, takes that hidden marking and uses it to boost the probability of measuring the correct answer while shrinking the probability of the wrong ones. Repeating these two steps a small number of times concentrates almost all the probability onto the right answer, so that when you finally measure the system, you get the correct result with very high likelihood.

For a search space of 4 items, this only takes one repetition of the two steps to nearly guarantee the correct answer, which is what you will build below.

Step by Step Instructions

Set up your notebook.

Go to Google Colab at colab.research.google.com and create a new notebook.

Install Qiskit.

Type the following into a code cell and run it:

pip install qiskit qiskit-aer

Build the starting superposition.

This uses 2 qubits, giving you 4 possible answers, 00, 01, 10, and 11. Let's say the answer we are secretly searching for is 11.

from qiskit import QuantumCircuit

from qiskit_aer import AerSimulator

qc = QuantumCircuit(2, 2)

qc.h(0)

qc.h(1)

qc.barrier()

Add the oracle that marks the answer 11.

This step flips the sign of the state 11 only, without telling us directly which one it marked.

qc.cz(0, 1)

qc.barrier()

Add the amplitude amplification step, also called the diffuser.

This step boosts the probability of the marked answer.

qc.h(0)

qc.h(1)

qc.x(0)

qc.x(1)

qc.cz(0, 1)

qc.x(0)

qc.x(1)

qc.h(0)

qc.h(1)

qc.barrier()

Measure the result.

qc.measure([0, 1], [0, 1])

print(qc.draw())

Run the circuit many times and check the results.

simulator = AerSimulator()

result = simulator.run(qc, shots=1000).result()

counts = result.get_counts()

print(counts)

Look at your output.

You should see something close to nearly all 1000 shots landing on 11, the answer we secretly marked, with very few or no results on 00, 01, or 10. Compare this to a classical search, where you would expect to check an average of 2 to 3 boxes out of 4 before finding the right one. Here, a single application of the algorithm found it almost every time.

Stretch step, try marking a different answer.

Change the oracle step to mark a different 2 qubit state instead of 11, for example by adding x gates before and after the cz gate to shift which state gets flipped, then rerun and confirm the results now cluster around your new target instead.

Congratulations, you just built and ran a real quantum search algorithm, the same algorithm that provides a proven speedup for unstructured search problems and is one of the foundational results that first proved quantum computers can outperform classical ones on certain tasks.

Fun Fact:

For a search space of 1 million items, a classical computer needs an average of about 500,000 checks to find the answer, but Grover's algorithm needs only about 1,000 steps, since the speedup scales with the square root of the search size, meaning the advantage gets dramatically larger the bigger the problem becomes.