Complexity Theory and why Quantum Computing is more interesting than AI
summary
Claim: quantum changes which problems are feasibly solvable by turning some exponential tasks into polynomial ones. Evidence: Google report of a task solved 13,000× faster than the fastest supercomputer, and recent machines hitting 6,100 qubits (but noisy physical qubits versus ~4,000 logical qubits needed to break common encryption). Tools and limits: transformer models on GPUs show diminishing returns, GPTs struggle on a simple maze, quantum chips need near‑absolute‑zero cooling and error correction. Result: promising algorithms exist but scaling and noise remain the hard engineering hurdles.
AI-written summary · about
chapters (10)
- 0:00Complexity theory intro
- 3:56Computational complexity explained
- 8:28Turing machines
- 10:58Turing to complexity classes
- 14:49AI limitations
- 21:10AI in practice
- 24:42Quantum vs AI
- 30:20Quantum computers solving hard problems faster
- 33:30Quantum challenges
- 35:35Closing thoughts
related talks
55mQuantum computers and quantum programming
42mIntroduction to Quantum Computing
28mThe future of computing with Quantum Computing
28mQuantum Computing: The next new technology in computing
24mQuantum Computing: a Treasure Hunt, not a Gold Rush
01h 01mQuantum Computing Concepts
12mThe Physics of AI
25mWhich applications will profit from a quantum computer?