A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.
Quantum algorithms for simulated annealing
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper summarizes a quantum algorithm of [R.D. Somma, et.al., Phys. Rev. Lett. 101, 130504 (2008)] that simulates a classical annealing process for solving discrete optimization problems. The complexity of the quantum algorithm scales with the inverse square root of the spectral gap of an associated stochastic matrix. This represents a quadratic quantum speedup, in terms of the gap, with respect to classical simulated annealing.
fields
quant-ph 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Quantum algorithm for estimating volumes of convex bodies
A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.