Reminder - these are today!
On Wed, Nov 6, 2019, 22:46 Aram Harrow <aram(a)mit.edu> wrote:
Dear quanta,
In our Friday group meeting we will have a talk from Kyungjoo Noh (Yale)
on bosonic codes.
That afternoon (1:30pm, 6c-402) we will have a talk by Tongyang Li
(Maryland); information below.
Title: Quantum algorithm for estimating volumes of convex bodies
https://arxiv.org/abs/1908.03903
Abstract: Estimating the volume of a convex body is a central problem in
convex geometry and can be viewed as a continuous version of counting. We
present a quantum algorithm that estimates the volume of an $n$-dimensional
convex body within multiplicative error $\epsilon$ using
$\tilde{O}(n^{3}+n^{2.5}/\epsilon)$ queries to a membership oracle and
$\tilde{O}(n^{5}+n^{4.5}/\epsilon)$ additional arithmetic operations. For
comparison, the best known classical algorithm uses
$\tilde{O}(n^{4}+n^{3}/\epsilon^{2})$ queries and
$\tilde{O}(n^{6}+n^{5}/\epsilon^{2})$ additional arithmetic operations. To
the best of our knowledge, this is the first quantum speedup for volume
estimation. Our algorithm is based on a refined framework for speeding up
simulated annealing algorithms that might be of independent interest. This
framework applies in the setting of "Chebyshev cooling", where the solution
is expressed as a telescoping product of ratios, each having bounded
variance. We develop several novel techniques when implementing our
framework, including a theory of continuous-space quantum walks with
rigorous bounds on discretization error.
_______________________________________________
qip mailing list
qip(a)mit.edu