Applications are closed
for this workshop

Arithmetic golden gates

April 24 to April 28, 2017

at the

American Institute of Mathematics, San Jose, California

organized by

Vadym Kliuchnikov, Michele Mosca, Ori Parzanchevski, and Peter Selinger

This workshop, sponsored by AIM and the NSF, will be devoted to understanding new developments in unitary approximation, which is a topic at the interface between quantum computing and number theory.

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:

  1. Construct an $\epsilon$-approximation to unitary $U$ by a gate sequence $g_1 g_2 \cdots g_k$, where $k=O(\log(1/\epsilon))$.
  2. Find such $\epsilon$-approximations in time polynomial in $\log(1/\epsilon)$.
All currently known constructions of fault-tolerant gate sets lead to countable subgroups of $SU(d)$ that are generated by elements with algebraic entries. For some of these gate sets there is a satisfactory answer to 1. and 2., most famously perhaps the so-called "Clifford+T" gate set, which consists of the image of the Clifford/Jacobi group under a faithful unitary representation together with a local operation $T=diag(1,\omega_8)$. Many other universal gate sets are possible, with an interesting family coming from so-called S-arithmetic groups, also called "Golden Gates" by Sarnak. Those groups are conjectured to yield the best possible approximations, however so far this has been established only for few groups in this family.

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 will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email

Plain text announcement or brief announcement.