Arithmetic golden gates

April 24 to April 28, 2017

at the

American Institute of Mathematics, San Jose, California

organized by

Vadym Kliuchnikov, Ori Parzanchevski, and Peter Selinger

Original Announcement

This workshop 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:

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)$.

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.

Material from the workshop

A list of participants.

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