A Combinatorial Approach to Complexity Transitions in Quantum Physics
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22·
summary
Deterministic polynomial time algorithms approximate Ising partition functions on graphs of maximum degree Δ when interactions and small external fields lie within a zero free region roughly up to about 1/8·(1/Δ) interaction strength, which converts to efficient classical approximation of IQP probability amplitudes for rotations up to about arcsin(1/8Δ). Beyond a larger constant scale related to 3π/(2Δ) the problem becomes gapP hard and relative error approximation becomes intractable, using zero-free regions, Barvinok methods and interpolation.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:38Quantum vs Classical Computation
- 1:43What does a quantum computer do?
- 3:54The fundamental object in quantum computing is the qubit
- 6:27The Hadamard test is an efficient quantum algorithm for producing a random variable Z with
- 7:08Complexity of Quantum Computing
- 12:05The Ising Model Partition Function
- 13:54Probability amplitudes are equivalent to sing model partition functions with imaginary weights
- 18:02Approximating the Partition Function
- 21:22Deterministic polynomial-time algorithm for
- 21:51Efficient classical simulation of probability amplitudes of the form (e), for graphs of maximum
- 25:28Hardness
- 29:04Open Problems
- 31:47Quantum Lovász Local Lemma
related talks
01h 06mQuantum Algorithms for Approximating Partition Functions
37m(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
46mLocal Minima in Quantum Systems
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
01h 07mClassical algorithms for quantum Gibbs states
24mA subpolynomial-time algorithm for the free energy of one-dimensional...
01h 10mQuantum Advantage with Shallow Clifford Circuits