Computer Science/Discrete Mathematics Seminar I

Solving the following problem is crucial when compiling for a quantum computer: given a finite set $G$ of elements of $SU(2)$, target element $U$ from $SU(2)$ and real number $\epsilon$ find $g_1,\dotsc, g_N$ from $G$ such that $\| g_1 \dotsm g_N - U \| < \epsilon$. It is known that if Hecke operator corresponding to $G$ has spectral gap, then $N$ can always be chosen to be less than $C_1 \log(1/ \epsilon) + C_2$ for constants $C_1$ and $C_2$ depending only on $G$. For example, this is the case when entries of elements of $G$ are algebraic numbers [J. Bourgain, A. Gamburd, On the spectral gap for finitely-generated subgroups of $SU(2)$]. When building a compiler for quantum computer one needs an efficient algorithm for finding the sequence $g_1, ..., g_N$ given $U$ and epsilon such that $N < C_1 \log(1/ \epsilon) + C_2$. In my talk I will review the recent progress towards such an algorithm for finite sets $G$ related to maximal orders of quaternion algebras over number fields and state many open questions. The talk is partially based on my joint work with Jon Yard http://arxiv.org/abs/1504.04350.