license.txt

Abstract

In broad terms, this thesis concerns efficient generators of unitary groups with respect to natural optimality heuristics. The first part considers finding optimal topological generators for \(U(1)\), viewed as the rotations of the plane. Sarnak's golden mean conjecture states that \((m+1)d_\varphi(m)\le1+\frac{2}{\sqrt{5}}\) for all integers \(m\ge1\), where \(\varphi\) is the golden mean and \(d_\theta(m)\) is the discrepancy function for \(m+1\) multiples of \(\theta\) modulo 1. In the first part of this thesis, we characterize the set \(\mathcal{S}\) of values \(\theta\) that share this property, as well as the set \(\mathcal{T}\) of those with the property for some lower bound \(m\ge M\). Remarkably, \(\mathcal{S}\mod1\) has only 16 elements, whereas \(\mathcal{T}\) is the set of \(GL_2(\mathbb{Z})\)-transformations of \(\varphi\).

The purpose of the second part of this thesis is in settings where good generators are known, and one wishes to navigate to a particular element. Chapter 2 gives a unified treatment of recent work by Carvalho Pinto--Petit and Sardari on finding short paths in the Lubotzky--Phillips--Sarnak Ramanujan graphs \(X^{p,q}\); both works make similar, fundamental improvements on the subcase of factoring diagonal matrices and use this technique to give polynomial-time algorithms for factoring almost all matrices in the group. Then, we consider an extension of this technique to \(\text{SU}_2(\mathbb{C})\), the setting of one-qubit gates and a focus of recent work by Ross--Selinger and Parzanchevski--Sarnak. We culminate with an extension of Carvalho Pinto--Petit's factorization and an implementation of the novel methods in the algorithm.