ExperimentsExperiment 8 · Quantum search

Grover Scaling

N = 4 … 1024: classical O(N) vs Grover O(√N).

1. Learn
2. Watch
3. Interact
4. Predict
5. Run
6. Observe
7. Record
8. Answer
9. Research

① What is the problem?

How does the work grow as the search space grows?

② How does a classical computer approach it?

Worst case N checks, average (N+1)/2.

③ How does the quantum approach differ?

About (π/4)√N oracle queries.

🔮 Make a prediction

For N = 1024, about how many Grover iterations are needed?

Each row is a fresh statevector simulation with a random target.

Query complexity, not wall-clock speed

These numbers count oracle queries. Doubling N doubles the classical checks but multiplies Grover's queries by only √2. A real device also pays for building the oracle circuit and for error correction, and this simulation itself runs on a classical computer — it shows the maths, not a physical speedup.

④ What is happening mathematically?

Doubling N doubles classical work but multiplies Grover's queries by only √2 ≈ 1.41.

⑤ What does the simulation show?

A table and graphs of actual simulations for each N.

⑥ What did we learn?

The gap widens with N — but this is query complexity; building the oracle and error correction carry real costs.

⑦ What can you experiment with?

Predict the Grover iterations for N=1024 before running.

📓 Record: my lab notebook

Write your observations. Notes are saved only in this browser.