Talks
Spring 2017

Discrete Log Problem with Respect to the LPS generators on PGL_2

Tuesday, January 31st, 2017 11:40 am12:25 pm

Add to Calendar

We discuss our p-adic version of the best known quantum compiling algorithm on a single qubit that is developed by Ross and Selinger. Two main applications of our algorithm are computing optimally the discrete log of diagonal matrices of $PGL_2(\mathbb{Z}/q\mathbb{Z})$ with respect to Lubotzky, Phillips and Sarnak generators and navigation problem for diagonal vertices of LPS Ramanujan graphs \cite{LPS}. My algorithm and Ross and Selinger's algorithm are conditional on assuming one can factor quickly, and a natural conjecture on the distribution of integers representable as a sum of two squares.