UCSB CS Theory Colloquium Series

Spring 2022

Friday, March 11th, 2pm, Phelps 2510

Speaker: Qipeng Liu (Simons)

Title: Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering
Abstract:
In this talk, I will show possible speed-ups for solving lattice-related problems using quantum computers, including the following:

(*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. One interesting parameter regime is to find a binary solution x for an over-determined linear equation system Ax = 0 in field F_3, in polynomial time.

(*) Learning with errors (LWE) problem given LWE-like *quantum* samples with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.

No classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider.