Improved Synthesis of Restricted Clifford+T Circuits
In quantum information theory, the decomposition of unitary operators into gates from some fixed universal set is of great research interest. Since 2013, researchers have discovered a correspondence between certain quantum circuits and matrices over rings of algebraic integers. For example, there is a correspondence between a family of restricted Clifford+T circuits and the group On(Z[1/2]). Therefore, in order to study quantum circuits, we can study the corresponding matrix groups and try to solve the constructive membership problem (CMP): given a set of generators and an element of the group, how to factor this element as a product of generators? Since a good solution to CMP yields a smaller decomposition of an arbitrary group element, it helps us implement quantum circuits using fewer resources.
Here, we consider CMP for the groups On(Z[1/2]), of n-dimensional orthogonal matrices with entries in Z[1/2]; and Ln, of n-dimensional orthogonal matrices of the form M/(\sqrt{2}^k), where M is an integer matrix and k is a natural number. Both groups arise in the study of quantum circuits and correspond to important classes of restricted Clifford+T circuits. In 2020, Amy et al. defined an exact synthesis algorithm that decomposes an element of On(Z[1/2]) or Ln into a product of O(2^nk) generators. In this talk, I will first describe an improved synthesis method that works in arbitrary dimensions and requires O(n^2k) generators. Then, I will introduce an alternative synthesis method, namely, a global synthesis algorithm. It works in dimensions 2, 4, and 8, and it requires O(k) generators.
Join the seminar on Teams or in QNC 1201!
Meeting link: IQC Student Seminar
Add event to calendar