Quantum Lab Session 7 — Finale Simulation Q20
⚖️ Before we begin — the honest map of quantum advantage
After everything you've learned about quantum computing — superposition, entanglement, Grover's algorithm, Shor's algorithm, VQE, QAOA — it's tempting to think: "quantum computers will be better at everything." They won't. Quantum computers are not universally faster than classical computers. They are faster at a specific and well-defined set of problems.

Sorting a billion numbers? Classical wins — quantum offers no advantage. Searching an unstructured database? Quantum wins by √N. Factoring a 2048-bit number? Quantum wins exponentially. Simulating a 50-electron molecule? Quantum wins exponentially. Playing chess? Classical wins — no quantum advantage known. Writing text or generating images? Classical wins for now.

Understanding which problems benefit from quantum computing — and why — is the mark of genuine quantum literacy. This simulation gives you the honest scorecard.
🌀 The complexity theory perspective
Computer scientists classify problems by how hard they are. P = solvable in polynomial time classically. NP = solutions checkable in polynomial time. BQP = solvable in polynomial time on a quantum computer. The central open question: is BQP strictly larger than P? We believe yes — but proving it rigorously remains one of the greatest open problems in mathematics.
⚖️ Quantum Advantage · Session 7 · Q20

Quantum vs Classical Showdown

The honest map — for which problems does quantum actually win, by how much, and why? Complexity classes, quantum supremacy, and the challenge quiz that tests your quantum literacy.

🏁 Race
📊 Complexity
🔬 Supremacy
❓ Challenge
🏆 Badge
🏁

Head-to-head

Sorting: no quantum advantage. Search: √N quantum speedup. Factoring: exponential quantum speedup. Simulation: exponential quantum speedup.

📊

Complexity classes

P (classical poly-time), BQP (quantum poly-time), NP (verifiable), QMA (quantum verifiable). BQP contains Shor's and Grover's algorithms.

🔬

Quantum supremacy

Google's 2019 Sycamore: 200 seconds vs 10,000 classical years. Controversial but milestone. "Practical advantage" on useful problems is still ahead.

❓

The honest truth

Quantum advantage is real but narrow. Most everyday computing stays classical. The problems that benefit are specific, important, and growing.

⚖️
Wizzy · Quantum Guide
Let's race! For each problem type, watch the scaling comparison: how does the time required grow with problem size N? Classical (red) vs Quantum (blue). The width of the bar shows the speedup at N=10⁶. Some races aren't even close — others have no quantum advantage at all.

Classical vs Quantum — Time Scaling

📋 Sorting N numbers
Classical
O(N log N)
Quantum
O(N log N) — SAME
No quantum advantage — proven. Classical sorting algorithms are already optimal.
🔍 Searching N unsorted items (Grover)
Classical
O(N) — linear
Quantum
O(√N) — quadratic
Quadratic quantum speedup. For N=10¹², classical: 10¹² steps, quantum: 10⁶ steps.
🔑 Factoring N-bit number (Shor)
Classical
sub-exponential
Quantum
O(N³) — polynomial!
Exponential quantum speedup. RSA-2048: classical = 300 trillion years, quantum = ~8 hours.
⚗️ Simulating N-electron molecule (VQE)
Classical
O(2ᴺ) — exponential
Quantum
O(poly(N)) — polynomial
Exponential quantum speedup. This is why drug discovery is the killer quantum app.
⚖️
Wizzy · Quantum Guide
Computer scientists classify computational problems into complexity classes based on how hard they are. P = easy for classical computers. NP = hard to solve but easy to verify. BQP = easy for quantum computers. Shor's algorithm proves that factoring (believed to be in NP but not P) is in BQP — an enormous result.
🌀 The million-dollar question: P vs NP
One of the seven Millennium Prize Problems (worth $1 million to solve): is P = NP? Most computer scientists believe P ≠ NP — that some problems are genuinely harder than others — but no proof exists. Quantum computers introduce BQP into this picture. We believe P ⊆ BQP ⊆ NP (quantum computers are faster than classical but can't solve all NP problems), but this too is unproven.

Complexity Classes — Where Problems Live

P — Easy classically

Polynomial time on a classical computer. Always fast enough.

  • Sorting, searching sorted data
  • Matrix multiplication
  • Shortest path (Dijkstra)
  • Linear programming
NP — Hard to solve, easy to verify

No known polynomial-time solution, but answers are easy to check.

  • Travelling Salesman (exact)
  • Sudoku, protein folding
  • Boolean satisfiability
BQP — Easy for quantum computers

Polynomial time on a quantum computer. This is where quantum wins.

  • Factoring integers (Shor)
  • Discrete logarithm
  • Unstructured search (Grover — sort of)
  • Quantum simulation
QMA — Hard even for quantum

The quantum equivalent of NP — problems a quantum computer can verify but not necessarily solve efficiently.

  • Local Hamiltonian problem
  • Quantum satisfiability
  • Many-body quantum physics
The key relationship: P ⊆ BQP means quantum computers can do everything classical computers can. BQP ≠ NP means quantum computers probably can't solve all hard problems. The sweet spot — problems in BQP but not in P — is where quantum advantage lives.
⚖️
Wizzy · Quantum Guide
"Quantum supremacy" means a quantum computer has performed a task that no classical computer can do in reasonable time. Google claimed this in 2019 with Sycamore. But was it real? Was it useful? The honest answer is: yes, and no — and understanding the difference is crucial quantum literacy.
🌀 The supremacy controversy
Google's 2019 claim: Sycamore completed a random circuit sampling task in 200 seconds that would take Summit (world's fastest supercomputer) 10,000 years. IBM disputed this immediately, arguing their classical algorithms could do it in 2.5 days. Later classical algorithms improved further. The task itself was constructed to be hard for classical computers — it has no known practical application. True "practical quantum advantage" on useful problems remains ahead of us.

Quantum Supremacy Timeline

1994
Shor's Algorithm — Theoretical supremacy

Peter Shor proves quantum computers can factor integers exponentially faster. First proof that BQP contains problems outside known efficient classical algorithms.

2016
China's Micius Satellite — QKD supremacy

First satellite-to-ground quantum key distribution. No classical equivalent possible — quantum communication milestone, not computing.

2019
🔥 Google Sycamore — "Quantum Supremacy" claimed

Random circuit sampling in 200 seconds vs claimed 10,000 classical years. IBM disputed. Task has no practical application. But milestone hardware: 53 qubits, 0.1% gate errors.

2021
China's Jiuzhang 2.0 — Photonic supremacy

Photonic boson sampling task. 10²⁴ faster than classical for that specific problem. Again, not practically useful — but demonstrates quantum hardware progress.

?
✅ Practical quantum advantage — still ahead

First time a quantum computer solves a real commercially useful problem faster than any classical computer. Most experts estimate 2028–2035, requiring fault-tolerant quantum hardware.

⚖️
Wizzy · Quantum Guide
Test your quantum literacy! For each problem description, decide: would a quantum computer help here? This is what real quantum scientists and engineers must assess every day. Score 5/5 to prove you can tell quantum hype from quantum reality!

Quantum Advantage Challenge

Score: 0/5
⚖️
Wizzy · Quantum Guide
🎊 You now have genuine quantum literacy — you know not just what quantum computers CAN do, but also what they can't do and why. This honest, critical understanding is what separates a real quantum scientist from someone who just repeats headlines.
🧠 What you actually learned today
  • Quantum advantage is real but narrow: sorting (none), search (√N speedup), factoring (exponential), simulation (exponential). Most everyday computing stays classical.
  • Complexity classes: P (classical poly-time), BQP (quantum poly-time), NP (hard to solve, easy to verify), QMA (hard even for quantum). P ⊆ BQP, BQP ≠ NP.
  • Google's 2019 "supremacy" was real hardware progress but on a contrived problem with no practical use. True practical quantum advantage on useful problems is still ahead.
  • The "killer" quantum applications are factoring (breaking RSA), quantum simulation (drug discovery), and specific optimisation problems — not general AI or sorting or database queries.
  • A quantum scientist's key skill: given a problem, determine whether quantum hardware offers an algorithmic advantage — and if so, how much and under what conditions.
⚖️

Quantum Realist Badge!

You can tell the difference between quantum hype and quantum reality!

⚖️ WhizzStep Quantum Lab
This certifies that
Student Name
has mastered Quantum vs Classical — Complexity Theory, Supremacy & Quantum Advantage
Quantum Realist
BQP Scholar
Complexity Expert
📖 Quantum Vocabulary
BQP KEY

Bounded-error Quantum Polynomial time — the class of problems solvable efficiently on a quantum computer. Contains factoring (Shor) and quantum simulation. Believed to be strictly larger than P.

Quantum supremacy

The point at which a quantum computer performs a task faster than any classical computer could. Google claimed this in 2019. The task was contrived — practical advantage on useful problems is still ahead.

Quantum advantage

A quantum computer solving a practically useful problem faster than classical computers. Stronger than supremacy — requires the problem to be genuinely useful. Not yet demonstrated as of 2025.

P vs NP KEY

The most famous open problem in computer science. P: efficiently solvable. NP: efficiently verifiable. If P = NP, everything verifiable is also efficiently solvable — most believe P ≠ NP.

QMA

Quantum Merlin Arthur — the quantum equivalent of NP. Problems for which quantum computers can efficiently verify solutions but not necessarily find them. Includes many quantum physics problems.

Key Concepts from Q20

Quantum advantage

🎯 Narrow but real

Quantum advantage is proven for factoring (exponential), simulation (exponential), and search (quadratic). For most computing tasks — sorting, writing, image generation — classical remains optimal.

Complexity

📊 P ⊆ BQP ⊆ PSPACE

Quantum computers are faster than classical for problems in BQP but not in P. The boundaries between these classes — especially whether BQP contains any NP-hard problems — are the central open questions.

Supremacy

🔬 Real milestone, wrong framing

Google 2019 proved quantum hardware is real and powerful. But the task was artificial. Practical advantage — on a problem someone actually needs solved — is the real finish line.

Literacy

📖 Read headlines critically

"Quantum computers will solve all problems" — false. "Quantum computers will break all encryption" — eventually true for RSA, but post-quantum cryptography will replace it. Nuance is everything.