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

Tuesday, September 21st, 2021, 11:00 am12:30 pm

Add to Calendar

Parent Program: 

Sean Hallgren (Penn State University & Senior Visitor at Simons Institute 2021-22)

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.