Session: Quantum Methods for Optimization and Sampling
Chair: Jiaqi Leng
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)
Talk 1: Optimizing random local Hamiltonians by dissipation
Speaker: Alexander Dalzell
Abstract: Markov chain Monte Carlo (MCMC) is a versatile category of numerical methods that has been fruitfully applied to many instances of classical constraint optimization problems. Recent work has developed a quantum analogue of MCMC—quantum Gibbs sampling algorithms—which can be applied to quantum optimization problems, that is, the task of preparing a low-energy quantum state of a local Hamiltonian. However, since quantum computers do not yet exist, these quantum algorithms cannot yet be tested empirically. In this work, we provide analytical guarantees for a simplified version of the Gibbs sampling algorithm on a wide class of random quantum optimization problems. Specifically, we study the problem of preparing a quantum state that optimizes a local Hamiltonian on a system of either quantum spins or fermions consisting of random all-to-all, k-local interactions. We prove that the simplified Gibbs sampling algorithm achieves a Ω(1/k)-fraction approximation of the optimum energy, giving an exponential improvement on the k-dependence over the prior best (both classical and quantum) algorithmic guarantees. Combined with existing circuit lower bound for such states, our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial. This further indicates that quantum Gibbs sampling may be a suitable metaheuristic for optimization problems. This is based on joint work with Joao Basso and Chi-Fang Chen (https://arxiv.org/pdf/2411.02578)
Talk 2: Quantum Langevin Dynamics for Optimization
Speaker: Zherui Chen
Abstract: We initiate the study of utilizing Quantum Langevin Dynamics (QLD) to solve optimization problems, particularly those non-convex objective functions that present substantial obstacles for traditional gradient descent algorithms. Specifically, we examine the dynamics of a system coupled with an infinite heat bath. This interaction induces both random quantum noise and a deterministic damping effect to the system, which nudge the system towards a steady state that hovers near the global minimum of objective functions. We theoretically prove the convergence of QLD in convex landscapes, demonstrating that the average energy of the system can approach zero in the low temperature limit with an exponential decay rate correlated with the evolution time. Numerically, we first show the energy dissipation capability of QLD by retracing its origins to spontaneous emission. Furthermore, we conduct detailed discussion of the impact of each parameter. Finally, based on the observations when comparing QLD with classical Fokker-Plank-Smoluchowski equation, we propose a time-dependent QLD by making temperature and ℏ time-dependent parameters, which can be theoretically proven to converge better than the time-independent case and also outperforms a series of state-of-the-art quantum and classical optimization algorithms in many non-convex landscapes.
Talk 3: Quantum Acceleration of Gibbs Sampling for Continuous Potentials
Speaker: Jiaqi Leng
Abstract: Realizing a random variable corresponding to a Gibbs distribution σ ∝ e(−βV(x)) with a continuous potential V(x) is a prominent task in the computer science and engineering. However, sampling from a high-dimensional Gibbs distribution is in general intractable due to the exponential blowup of computational complexity, a challenge known as the curse of dimensionality. While quantum computers can efficiently process high-dimensional data, existing quantum algorithms for Gibbs sampling exhibit sub-optimal dimension dependence and potentially slow convergence rate, leaving substantial room for quantum advantage for the classical sampling task. In this paper, by reformulating the invariant measure of certain diffusion processes as ground state of quantum Hamiltonians, we propose a novel approach to accelerate Gibbs sampling on quantum computers. In this paper, by reformulating the invariant measure of certain diffusion processes as the ground state of quantum Hamiltonians, we propose a novel approach to accelerating Gibbs sampling on quantum computers using the standard quantum numerical linear algebra toolbox. We apply our framework to two commonly used diffusion processes in the literature: Langevin Diffusion (LD) and Replica Exchange Langevin Diffusion (RELD). By quantizing LD, we obtain a quantum algorithm that matches the best-known classical methods. While RELD has been widely used in practice, its rigorous analysis remains challenging in the classical literature. Our new method bypasses the technical difficulties in the classical convergence analysis of RELD, yielding a quantum algorithm that outperforms all known results in terms of dimension dependence and convergence rate.
