Chunhao Wang

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.

The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(n\log n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problem’s quantum {time} complexity. Specifically, we give an $\tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $\text{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the \emph{Quantum Strong Exponential Time Hypothesis (QSETH)}, which is based on the assumption that Grover’s algorithm is optimal for \textsf{CNF-SAT} when the clause width is large. We show that the na\”{i}ve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

The motivating question for this work is how to efficiently estimate the expected value of an observable when the system undergoes a small and time-dependent perturbation. When the underlying system is a Markovian open quantum system, well-established quantum regression theorem (QRT) and linear response theory (LRT) are powerful tools for this task; however, QRT and LRT failed to work beyond the Markovian regime. In this paper, we first develop a novel formulation of linear response functions for open quantum systems that extends the standard QRT beyond the Markov limit. In addition, we present efficient quantum algorithms for estimating such response functions whose cost scales poly-logarithmically in the system dimension and $1/\epsilon^{1+o(1)}$ in the target accuracy $\epsilon$. The framework removes the separability (Born-Markov) assumption and offers a pathway to efficient computation of nonequilibrium properties from open quantum systems.

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap $\mathrm{Max}$-$\mathrm{Cut}$, problem) to $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = \mathrm{O}(1)$ and finite $p \geq 1$, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from $k$-$\mathrm{SAT}$ to $\mathrm{CVP}_2$. This implies three headline results: (i) Faster algorithms for $\gamma\text{-}\mathrm{CVP}_p$ are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a $2^{0.78n}$-time or $2^{0.3n}$-time algorithm would improve upon the state-of-the-art algorithm such as Williams' 2004 algorithm [\textit{Theoretical Computer Science} 2005] or Arora, Barak, and Steurer's 2010 algorithm [$\textit{Journal of the ACM}$ 2015]. This provides evidence that $\gamma\text{-}\mathrm{CVP}_p$ for $\gamma = o(\sqrt{\log n}^\frac{1}{p})$ requires $2^{\delta n}$-time for some specific constant $\delta > 0$, improving upon the previous exponential lower-bound for $\gamma\text{-}\mathrm{CVP}_2$ with $\gamma < 3$ by Bennett, Golovnev, and Stephens-Davidowitz [$\textit{FOCS}$ 2017]. (ii) A new almost $2^{(1/2 + \varepsilon/4\varsigma + o(1)) n}$-time classical algorithm and a new almost $2^{(1/3 + \varepsilon/6\varsigma + o(1)) n}$-time quantum algorithm for $(1-\varepsilon, 1-\varsigma)$-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steuer [$\textit{Journal of the ACM}$ 2015], as well as the algorithm of Williams [$\textit{Theoretical Computer Science}$ 2004], % and others and the algorithm of Manurangsi and Trevisan [\textit{APPROX/RANDOM} 2018] when $c_0 \varepsilon < \varsigma < c_1 \varepsilon$ for some constants $c_0, c_1$. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a $2^{\delta n}$-time lower-bound for $\mathrm{Max}$-$\mathrm{Cut}$, Max-2-Lin(2), or $\mathrm{CVP}_2$ for any constant $\delta > 0$, it must be via an adaptive quantum reduction unless $\mathrm{NP} \subseteq \mathrm{pr}\text{-}\mathrm{QSZK}$. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result builds off of and strengthens the no-go results of Aggarwal and Kumar [$\textit{FOCS}$ 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).