Dániel Szilágyi

Simon Apers, Sander Gribling, Dániel Szilágyi

Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density $e^{-f(x)}$, given access to the gradient of $f$. A particular case of interest is that of a $d$-dimensional Gaussian distribution with covariance matrix $Σ$, in which case $f(x) = x^\top Σ^{-1} x$. We show that HMC can sample from a distribution that is $\varepsilon$-close in total variation distance using $\widetilde{O}(\sqrtκ d^{1/4} \log(1/\varepsilon))$ gradient queries, where $κ$ is the condition number of $Σ$. Our algorithm uses long and random integration times for the Hamiltonian dynamics. This contrasts with (and was motivated by) recent results that give an $\widetildeΩ(κd^{1/2})$ query lower bound for HMC with fixed integration times, even for the Gaussian case.

Iordanis Kerenidis, Anupam Prakash, Dániel Szilágyi

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time $\widetilde{O} \left( n\sqrt{r} \frac{ζκ}{δ^2} \log \left(1/ε\right) \right)$ where $r$ is the rank and $n$ the dimension of the SOCP, $δ$ bounds the distance of intermediate solutions from the cone boundary, $ζ$ is a parameter upper bounded by $\sqrt{n}$, and $κ$ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a $δ$-approximate $ε$-optimal solution of the given problem. Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision $ε$. We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time $O(n^{ω+0.5})$ (here, $ω$ is the matrix multiplication exponent, with a value of roughly $2.37$ in theory, and up to $3$ in practice). For the case of random SVM (support vector machine) instances of size $O(n)$, the quantum algorithm scales as $O(n^k)$, where the exponent $k$ is estimated to be $2.59$ using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$.