Arithmetic golden gates
April 24 to April 28, 2017
American Institute of Mathematics,
San Jose, California
and Peter Selinger
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:
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.
- 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
- 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
- Synthesis algorithms for general gate sets: Generalize
earlier work on synthesis via quaternion algebras in various
directions, including indefinite quaternion algebras and central
- 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
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: