at the

American Institute of Mathematics, San Jose, California

organized by

Vadym Kliuchnikov, Ori Parzanchevski, and Peter Selinger

Quantum computers are capable of solving important problems more efficiently than is possible using conventional computers. Several laboratories around the world are now moving towards implementing large-scale fault-tolerant quantum computers. The requirement for a quantum computer to execute only such operations that can be implemented fault-tolerantly, i.e., without a proliferation of errors, gives rise to problems in unitary approximation, in particular the following:

- Construct an $\epsilon$-approximation to unitary $U$ by a gate sequence $g_1 g_2 \cdots g_k$, where $k=O(\log(1/\epsilon))$.
- Find such $\epsilon$-approximations in time polynomial in $\log(1/\epsilon)$.

In the case of a single qubit, a quaternionic framework for the approximation and synthesis problems (i) and (ii) was recently developed. This framework recovers many of the seminal earlier results on synthesis for the Clifford+T gate set but also some classic results on S-arithmetic groups and the associated LPS graphs. The study of Golden Gates gives rise to a plethora of questions. The answers to these questions will be fruitful for both communities, i.e., the quantum computing and quantum circuit compilation community on the one hand and the arithmetic group theory and Diophantine approximation community on the other.

The purpose of this interdisciplinary workshop is to bring the two communities together and to work on a number of open problems:

**Optimality of Golden Gates:**Here we seek to characterize the exact expansion properties of particular arithmetic gate sets, such as the Golden Gates, by developing a theory of strong approximation.**Finding the best gate sets:**Given that there is a large variety of potential gate sets, the goal is to find the best ones and to develop algorithms to find the shortest factorization for a given gate set.**Synthesis algorithms for general gate sets:**Generalize earlier work on synthesis via quaternion algebras in various directions, including indefinite quaternion algebras and central simple algebras.**Prove conjectures about samplers:**All known approaches to finding epsilon-approximations rely on solving norm equations. We aim at proving the existence of a polynomial fraction of good samples.

The workshop schedule.

A report on the workshop activities.

A list of open problems.

Resources from the workshop:

The slides from Peter Selinger's talk

Paths in the hash function based on Pizer/LPS graphs. Pizer/LPS graphs are good expanders; graph image for Pizer graph for $p=2521$ and $\ell=2$ created by Denis Charles: image 1 image 2 image 3