Quantum Colloquium — An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor

We give a polynomial-time quantum algorithm for solving the Bounded Distance Decoding problem with a subexponential approximation factor on a class of integer lattices.  The quantum algorithm achieves an exponential speedup compared to the best known classical algorithm, and is the first example of an exponential speedup on a general lattice problem not connected to number theory.

Joint work with Lior Eldar.

Panel discussion: Vinod Vaikuntanathan, Daniel Apon, Umesh Vazirani