for this workshop
Arithmetic golden gates
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:
- 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 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 workshops@aimath.org
