How Simulating Balls and Springs Captures the Power of Quantum Computing
summary
Defines a classical decision problem: predict one coordinate of the time evolution of 2^n coupled oscillators where inputs are given by a succinct circuit encoding and sparse data; shows a quantum algorithm that prepares an energy-to-state mapping and uses Hamiltonian simulation to compute that coordinate in poly(n) time, proving the problem BQP-complete. Constructs reductions (including glued‑trees) to prove classical query lower bounds and gives rigorous proofs that the quantum construction works.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:40Outline
- 2:38Problem Overview
- 4:02Problem Explanation
- 24:28Main Result
- 26:43Why Balls and Springs
- 33:52Stable Equilibrium
- 39:21Second Order Differential Equations
- 41:51Map to Quantum System
- 43:44Map to Quantum State
- 44:17Map to Schrodinger Equation
- 48:11Map to a Quantum State
related talks
43mStrongly Universal Hamiltonian Simulators
47mQuantum Computing and You
23mCommunity keynote - Quantum Computing: Mind-bogglingly weird!
01h 02mQuantum Computing Concepts
01h 01mWhat Is "Quantum" About Quantum Computing?
41mQuantum Computing
22mClassical Simulation of Quantum Circuits with Partial Interference Effects
46mQuantum computing