Speaker
Description
Demonstrating a quantum advantage over classical computational capabilities is a central objective of quantum algorithms research. While there are numerous quantum algorithms that outperform the best known classical methods, quantum-classical separation results are comparatively rare, especially for sampling problems over continuous domain. The best known quantum–classical separation results, such as Grover's search for the unstructured search problem and Simon's problem, primarily concern discrete computational problems and do not address problems involving continuous variables. However, analogous separation results for Gibbs sampling, which is a fundamental computational task in statistical physics, computational science, and machine learning, have never been established before to the best of our knowledge. In this work, we establish a quantum-classical separation for Gibbs sampling on the torus $\mathbb {T}^{d}$ whose densities belong to a Gevrey regularity class. We prove an information-theoretic lower bound on the query complexity of every classical sampling algorithm interacting with any local oracle for the target. We then develop a Gibbs sampling algorithm based Quantum Singular Value Transformation (QSVT) with annealing which has an upper bound that is lower than the classical lower bound for the same class of problem. This is the first separation result for continuous Gibbs sampling to the best of our knowledge.
| Topic | Quantum algorithms for machine learning applications |
|---|