How Simulating Balls and Springs Captures the Power of Quantum Computing

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,600
Published on ● Video Link: https://www.youtube.com/watch?v=d6LU9DYuErs


Duration: 1:27:56
514 views
6

Robin Kothari (Google)
https://simons.berkeley.edu/talks/robin-kothari-google-2023-07-11
Quantum Summer Cluster Workshop

I'll describe a classical problem related to simulating the classical time dynamics of 2^n balls and springs that can be solved by quantum computers in poly(n) time (the problem is in BQP) and which also captures the power of quantum computing (the problem is BQP-complete). This yields a new problem of interest that can be solved by quantum computers. Conversely, we can design new quantum algorithms by only analyzing classical systems of balls and springs. This talk is based on the paper https://arxiv.org/abs/2303.13012, which is joint work with Ryan Babbush, Dominic W. Berry, Rolando D. Somma, and Nathan Wiebe.



Other Videos By Simons Institute for the Theory of Computing


2023-07-15Approaching the Quantum Singleton Bound with Approximate Error Correction
2023-07-14Improved Machine Learning Algorithm for Predicting Ground State Properties
2023-07-14Learning Beyond Stabilizer States
2023-07-14Quantum Commitments and Black Hole Radiation Decoding
2023-07-14Geometry, Entropy and Complexity in Quantum Gravity (Part II)
2023-07-14Geometry, Entropy and Complexity in Quantum Gravity (Part I)
2023-07-13Dissipative State Preparation and the Dissipative Quantum Eigensolver
2023-07-13QMA and the Power of “Positivity”
2023-07-13Compiled Nonlocal Games: From CHSH to BQP Verification
2023-07-12Making the Leap to Quantum PCPs
2023-07-12How Simulating Balls and Springs Captures the Power of Quantum Computing
2023-07-12Quantum Algorithms for Approximating Partition Functions
2023-07-12Quantum Gibbs Sampling
2023-07-11Quantum Advantage with Shallow Clifford Circuits
2023-07-11Utility, Computational Cost, and Effective Quantum Volume of NISQ Experiments
2023-07-11A Phase Transition in Linear Cross-Entropy Benchmarking
2023-07-11Validated Quantum Advantage via Bell Sampling
2023-07-11Verifiable Quantum Supremacy: What I Hope Will Be Done
2023-07-01Representation Theory in TCS and Extremal Combinatorics
2023-07-01On Perfectly Friendly Bisections of Random Graphs
2023-07-01Localization Schemes


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantum Summer Cluster Workshop
Robin Kothari