Guneykan Ozgul

We introduce new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, broadening the scope of quantum advantage beyond traditional tunneling-based explanations. By establishing a rigorous correspondence between the spectral properties of Schrödinger operators and classical Langevin diffusion, we identify regimes where a real-space adiabatic algorithm (RsAA) can significantly outperform classical stochastic gradient-based methods. Leveraging this connection and novel non-asymptotic versions of well-known semi-classical results, we provide polynomial (in the dimension $d$) runtime bounds for RsAA on rotated block-separable functions, and offer theoretical evidence that black-box classical algorithms require exponential time for optimization in these settings, thereby generalizing and formalizing prior work by Leng et al (arXiv:2311.00811). While we can design certain specialized, structure-aware classical algorithms that can efficiently optimize these functions, we further show that the quantum ground state exhibits remarkable robustness to nontrivial perturbations. Leveraging recent advances in the study of the hypercontractivity of Schr\"{o}dinger operators, we construct new families of nonconvex functions for which RsAA achieves polynomial-time optimization, whereas both off-the-shelf and structure-aware classical algorithms incur exponential computational costs. These results provide new insight into quantum-classical separations in nonconvex optimization and highlight tractable and general pathways to advantage in this setting.

We present quantum speedups for sampling from probability distributions of the form $\pi \propto e^{-f}$, where $f:\mathbb{R}^d\mapsto \mathbb{R}$. We consider two oracle models: (i) a stochastic gradient oracle, where $f$ is in finite sum form, i.e., \(f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)\) and individual component gradients are accessible, (ii) a stochastic zeroth-order oracle, where only noisy evaluations of \(f\) are available. Our main contribution is a general framework for quantumly accelerating classical stochastic sampling algorithms, such as Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC), by replacing stochastic gradient computations with variance-controlled quantum mean and gradient estimation subroutines. In contrast to prior quantum sampling approaches based on quantum walks, our methods do not require reversibility or exact gradient access, and preserve the structure of the underlying (possibly nonreversible) Markov chain. In the stochastic gradient oracle model, we integrate unbiased quantum mean estimation with classical variance-reduction techniques, including stochastic variance-reduced gradients (SVRG) and control variates (CV). By jointly optimizing the target variance of quantum estimators and the frequency of full-gradient recomputation, we obtain provable improvements in gradient query complexity over the best known classical samplers. These results apply both to strongly log-concave and to non-logconcave distributions satisfying a log-Sobolev inequality, with convergence guarantees in Wasserstein distance and Kullback--Leibler divergence. In the stochastic zeroth-order model, we develop new quantum gradient estimation procedures that are robust to noisy and potentially unbounded function evaluations. These estimators lead to improved evaluation complexity for quantum-accelerated LMC and HMC under standard smoothness assumptions. Finally, we show that faster quantum sampling yields quantum speedups for optimization, including nonsmooth and approximately convex objectives. This recovers known quantum advantages for finite-sum optimization and establishes new improvements in the zeroth-order stochastic setting.

Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} in general but of great practical importance, and it is valuable to identify algorithmic speedups to expand the domain of problems that can be solved in practice. It has proven challenging to identify super-quadratic quantum speedups for ILPs. A primary difficulty is that most classical algorithms that handle ILPs with many constraints are global and exhaustive, whereas quantum frameworks that offer the potential for super-quadratic speedups leverage the local properties of the objective function and feasible set. We address this difficulty by considering quantum algorithms for Gomory's group relaxation, a relaxation of an ILP that is obtained by removing the nonnegativity constraints from variables that are positive in the optimal solution of the linear programming relaxation, while keeping integrality of the decision variables. We present a classical algorithm that is competitive with known alternatives that solves the group relaxation via a local search, and a corresponding quantum algorithm that under reasonable technical conditions offers a super-quadratic speedup. When the group relaxation satisfies a non-degeneracy condition analogous to (albeit stronger than) that found in linear programming, our approach yields an optimal solution to the original integer program. In other cases, the group relaxation can improve downstream branch-and-cut solvers by reducing the integrality gap, a behavior that we numerically show to be typical for some practically interesting ILPs.