Seminario del 2024

Dicembre
12
2024
Alexander Zlokapa
Slow mixing from quantum bottlenecks
nell'ambito della serie: SEMINARS IN MATHEMATICAL PHYSICS AND BEYOND
nel ciclo di seminari: SEMINARS IN MATHEMATICAL PHYSICS AND BEYOND
fisica matematica
In classical algorithms, tools such as the overlap gap property and free energy barrier are used to provide lower bounds for algorithms that are local, stable, or low-degree. In this talk, we review quantum algorithms for Gibbs sampling and show that they face analogous obstructions due to a general quantum bottleneck lemma. When applied to Metropolis-like algorithms and classical Hamiltonians, our result reproduces classical slow mixing arguments. Unlike previous techniques to bound mixing times of quantum Gibbs samplers, however, our bottleneck lemma provides bounds for non-commuting Hamiltonians. We apply it to systems such as random classical CSPs, quantum code Hamiltonians, and the transverse field Ising model. Key to our work are two notions of distance, which we use to measure the locality of quantum samplers and to construct the bottleneck.
organizzato da: Gabriele Sicuro
nell'ambito del Progetto P.R.I.N. PRIN2022_DE PALMA CUP J53D23003890006 del prof. Giacomo De Palma

indietro