Fast Navigation with Icosahedral Golden Gates

A quaternion algebra $\mathcal{A}$ over a field $\mathbb{F}$ is a central simple algebra of dimension four over $\mathbb{F}$ (cf. [15, §5.2] or [5, p.15]). It follows from Wedderburn’s structure theorem on simple algebras [3] that every quaternion algebra over any field $\mathbb{F}$ is either isomorphic to $\mathrm{M}_{2}(\mathbb{F})$ or a division algebra with center $\mathbb{F}$ [8]. If the characteristic of $\mathbb{F}$ is not 2 then it is always possible to find a basis $\{1,i,j,k\}$ for $\mathcal{A}$ over $\mathbb{F}$ such that

where $\alpha,\beta\in\mathbb{F}^{\times}$. We designate such an algebra by

Evidently $q\in\mathcal{A}$ is of the form

where $x_{\ell}\in\mathbb{F}$. In this notation, Hamilton’s quaternions arise as

The conjugate of $q$ as in (2.1), denoted by $\bar{q}$, is equal to $x_{0}-x_{1}i-x_{2}j-x_{3}k$. For each $q\in\mathcal{A}$ we define the (reduced) norm map $\operatorname{N}:\mathcal{A}\to\mathbb{F}$ by

and the (reduced) trace map $\operatorname{Tr}:\mathcal{A}\to\mathbb{F}$ by

We note that every element $q\in\mathcal{A}$ satisfies the quadratic equation

It is possible to make everything completely explicit by embedding $\mathcal{A}$ in $\mathrm{M}_{2}\left(F\left(\sqrt{\alpha}\right)\right)$ by, for example,

Evidently, if $\alpha$ is a square in $\mathbb{F}$, then $\mathcal{A}\cong\mathrm{M}_{2}(\mathbb{F})$. A necessary and sufficient condition for $\mathcal{A}\cong\mathrm{M}_{2}(\mathbb{F})$ is that $\alpha$ is the norm of an element in $\mathbb{F}(\sqrt{\beta})$ with respect to $\mathbb{F}$ [28]. Of course, one may interchange $\alpha$ and $\beta$ in this remark.

Specializing to quaternion algebras over the rational field $\mathbb{Q}$, or over one of the completions $\mathbb{Q}_{p}$ or $\mathbb{R}$ (the completion $\mathbb{Q}_{\infty}$), let $\mathcal{A}$ be a quaternion algebra over $\mathbb{Q}$ and let $p$ be a prime (or $\infty$). We define

Either $\mathcal{A}_{p}\cong\mathrm{M}_{2}(\mathbb{Q}_{p})$ or $\mathcal{A}_{p}$ is a division algebra over $\mathbb{Q}_{p}$. In this case we will have that $\mathcal{A}_{p}\cong\mathbb{H}_{p}$ and say that $\mathcal{A}$ is ramified at $p.$ When $\mathcal{A}_{p}\cong\mathrm{M}_{2}(\mathbb{Q}_{p})$ we will say that $\mathcal{A}$ is unramified or split at $p.$ If $\mathcal{A}$ is ramified at $\infty$ it is called a definite rational quaternion algebra—that is, if $\mathcal{A}$ is definite then

If $\mathcal{A}$ is split at $\infty$, it is called an indefinite rational quaternion algebra—that is, if $\mathcal{A}$ is indefinite then

Golden gates are special unit groups in quaternion algebras over totally real number fields derived from the $p$-arithmetic groups [24]. They give variants of optimal generators for $\operatorname{PU}(2)$ and connect the arithmetic of quaternion algebras to quantum computation on a single qubit. The “golden” characterization is to be understood by way of an interesting link between $p$-arithmetic unit groups coming from unit quaternion groups and the Ramanujan graphs $X^{p,q}$, which we explicate below.

Recall once more that in classical computation, one decomposes any function into basic logical gates such as XOR, AND, and NOR, and that in quantum computation, the classical bits are replaced by qubits, which are vectors in projective Hilbert space $\mathbb{C}P^{n}$, and that the logical gates are all the elements of the projective unitary group $\operatorname{PU}(2).$ Let $S$ be a subgroup of $\operatorname{PU}(2)$ and denote by $S^{(\ell)}$ the set of $\ell$-fold products of elements in $S$. If $\left\langle S\right\rangle=\bigcup\limits_{\ell\geq 0}S^{(\ell)}$ is dense in $\operatorname{PU}(2)$ (with respect to the standard bi-invariant metric $d^{2}(A,B):=1-\frac{|\operatorname{Tr}(A^{*}B)|}{2}$) then $S$ is universal. That is, any gate can be approximated with arbitrary precision as a product of elements of $S$.

The notion of of a golden gate set is much stronger, requiring [10]:

1. (1)

   Optimal covering of $\operatorname{PU}(2)$ by $\left\langle S\right\rangle$: for every $\ell$ the set $S^{(\ell)}$ distributes in $\operatorname{PU}(2)$ as a perfect sphere packing (or randomly placed points) would, up to a negligible factor.

2. (2)

   Approximation: given $A\in\operatorname{PU}(2)$ and $\varepsilon>0$, there is an efficient algorithm to find some $A^{\prime}\in B_{\varepsilon}(A)$ (the $\varepsilon$-ball around $A$) such that $A^{\prime}\in S^{(\ell)}$ with $\ell$ (almost) minimal.

3. (3)

   Compiling: given $A\in\left\langle S\right\rangle$ as a matrix, there is an efficient algorithm to write $A$ as a word in $S$ of the smallest possible length.

These requirements ensure that any gate can be approximated and compiled as an efficient circuit using the gates in $S$.

Each super golden gate set is composed of a finite group $C$ and an involution $\tau$, which lie in a $\mathfrak{p}$-arithmetic group for $\mathfrak{p}$ a prime ideal of the integers $O_{\mathbb{F}}$ of a totally definite quaternion algebra $\mathcal{A}$, over a totally real number field $\mathbb{F}$. We require that:

1. (1)

   $C$ acts simply transitively on the neighbors of any given vertex in $X^{p}$, the ($p+1$)-regular tree, for $p$ the norm of $\mathfrak{p}$.

2. (2)

   $\tau$ is an involution which takes a vertex to one of its neighbors.

$\mathfrak{p}$-arithmetic unit quaternion group act transitively on the vertices of the corresponding $X^{p}$. The $\mathfrak{p}$-arithmetic groups which act transitively on the vertices of $X^{p}$ are called the golden gates and the $\mathfrak{p}$-arithmetic groups which act transitively on both the vertices and edges of $X^{p}$ are called the super golden gates.

We proceed by, for given diagonal element $\delta=u(\theta)$ and $\varepsilon$, seeking $\gamma\in\Gamma$ with $d(\delta,\gamma)<\varepsilon$. Knowing that $\gamma$ is projectively equal to an element

for $x_{0},x_{1},x_{2},x_{3}\in\mathbb{Z}[\varphi]$ satisfying

for some $m\in\mathbb{N}$, we also have that it is sufficient to satisfy

(note that this is precisely [21, (13) and Problem 7.4] (see there for the derivation)), following the readily computable observation that $\left\|\delta-\gamma\right\|\geq\sqrt{2}d(\delta,\gamma)$ and setting the goal $\left\|\delta-\gamma\right\|\leq\sqrt{2}\varepsilon$, since [21] operates with respect to the operator norm. Observe, unfortunately, that (5.1) is a quadratic constraint and (5.2) is a linear constraint. We now explain how to transform them into a practicable sequence of integer programs.¹¹1Fundamentally, this is the same idea as in [21], as their study of upright ellipses accomplishes the same task as Lenstra’s algorithm.

Fix $m$. We seek $x_{\ell}\in\mathbb{Z}[\varphi]$ satisfying (5.1) and (5.2). Define $y_{\ell}=\nicefrac{{x_{\ell}}}{{\eta^{\nicefrac{{m}}{{2}}}}}$. Artificially add the constraint

Observe from (5.1) that $y_{0}^{2}\leq 1-y_{1}^{2}$. Then, we have the sequence of implications (mainly by algebraic manipulation)

and so we have reduced our consideration to just one of the four variables. As $[\mathbb{Q}(\varphi):\mathbb{Q}]=2$, we explicitly work with the Galois group elements

where $\varphi^{\bullet}$ is $\varphi$’s Galois conjugate $\frac{1-\sqrt{5}}{2}=1-\varphi$, both of which are real embeddings, yielding the additional constraints

Now, putting $x_{1}=c+d\varphi$ for some $c,d\in\mathbb{Z}$, (5.3), (5.4), and (5.5) transform into

The existence of such a pair is determinable in $O(\operatorname{poly}m)$ time, by Lenstra’s algorithm [7, 20].

Putting $x_{0}=a+b\varphi$ for some $a,b\in\mathbb{Z}$, for a particular solution to Problem 1, (5.1) and (5.2) transform into

Again, the existence of such a pair is determinable in $O(\operatorname{poly}m)$ time, by Lenstra’s algorithm.

Finally, if we have solutions to Problem ‣ 5.1 and Problem 1, we seek to solve

Here we change techniques. The objective is to write $\eta^{m}-x_{0}^{2}-x_{1}^{2}$ as a sum of squares in $\mathbb{Z}[\varphi]$. Assuming efficient factorization in $\mathbb{Z}$ (or $\mathbb{Z}[\varphi]$, also a PID), Problem 23 is efficiently solvable via Theorem 3 (the general approach being basically identical to the classical algorithms for $\mathbb{Z}[i]$ or $\mathbb{Z}[e^{\nicefrac{{i\pi}}{{8}}}]$, cf. [21, §C] for the latter).

We have succeeded in the core of the algorithm. To handle given $\delta$, begin by fixing $m=0$. For given $m$, attempt to solve Problem 1; for each solution, attempt to solve Problem ‣ 5.1; for each solution, attempt to solve Problem 23. If this results in a tuple $(x_{0},x_{1},x_{2},x_{3})$ satisfying all three problems, halt and return

Otherwise, if all possibilities have been exhausted, increment $m$.

We refer the reader to [19, §2.3]’s analysis of timing and correctness for Ross and Selinger’s algorithm generalized to any golden gate set, where the conclusion is that for desired precision $\varepsilon$, the factorization length becomes $(1+o(1))\log_{59}(\nicefrac{{1}}{{\epsilon^{3}}})$ with required computational time remaining $O(\operatorname{poly}\log(\nicefrac{{1}}{{\epsilon}}))$.

Select absolute constants $\tilde{\varepsilon},\varepsilon_{0}>0$. Take any $g=u(\alpha,\beta)\in\operatorname{PU}(2)$ where $\left\lvert\alpha\right\rvert<\sqrt{1-\varepsilon_{0}^{2}}$, and pick $\varepsilon<\tilde{\varepsilon}$. We wish to approximate $g$ in $d$ using $\gamma\in\Gamma$ of the form

having $k$, the factorization length, minimized, and so we begin with $k=0$. (We also have $x_{0},x_{1},x_{2},x_{3}\in\mathbb{Z}[\varphi]$.) In particular, the objective is to approximate $g$ as $\gamma_{1}\gamma\gamma_{2}$ where $\gamma_{1},\gamma_{2}\in\Gamma$ approximate well-chosen diagonals computable using §5, and $\gamma\in\Gamma$ has factorization computable using Algorithm 1. We will see that $\gamma$ is designed to have factorization typically shorter than that of $\gamma_{1}$ and $\gamma_{2}$, giving rise to the desired improvement.

In order to apply Lemma 1 we need to have $\left\lvert\frac{x_{0}+x_{1}i}{\eta^{\nicefrac{{k}}{{2}}}}\right\rvert=\sqrt{\frac{x_{0}^{2}+x_{1}^{2}}{\eta^{k}}}$ near $\left\lvert\alpha\right\rvert$ (that is, within $\varepsilon$). Because $\left\lvert\frac{x_{0}+x_{1}i}{\eta^{\nicefrac{{k}}{{2}}}}\right\rvert+\left\lvert\alpha\right\rvert\geq\left\lvert\alpha\right\rvert$ which is fixed, it suffices to find candidate values for $x_{0},x_{1}\in\mathbb{Z}[\varphi]$ with $\left\lvert\left\lvert\frac{x_{0}+x_{1}i}{\eta^{\nicefrac{{k}}{{2}}}}\right\rvert^{2}-\left\lvert\alpha\right\rvert^{2}\right\rvert<\varepsilon\left\lvert\alpha\right\rvert$, rewritten to

Viewing $\gamma$ as an element of $\operatorname{SU}(2)$, we also have $\det\gamma=1$, i.e. $x_{0}^{2}+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}=\eta^{k}$. As $x_{\ell}\in\mathbb{Z}[\varphi]\subset\mathbb{Q}(\varphi)\subset\mathbb{R}$, it follows that $\sigma_{\pm}(x_{0}^{2}+x_{1}^{2})+\sigma_{\pm}(x_{2}^{2}+x_{3}^{2})=\sigma_{\pm}(\eta^{k})$, and so

Now, let $m=x_{0}^{2}+x_{1}^{2}\in\mathbb{Z}[\varphi]$. Considering $\mathbb{Z}[\varphi]$ as an integer lattice, we adapt (6.2) and (6.3) and seek to solve

which are convex constraints on $m$’s lattice components. Since this is an integer programming problem in two dimensions, we apply Lenstra’s algorithm [7, 20] to efficiently list all such lattice points $m$. For each $m$, using Theorem 3, we attempt to write $m$ as a sum of two squares; if possible, say $m=x_{0}^{2}+x_{1}^{2}$, we then attempt to write $\tilde{m}=\eta^{k}-m$ as a sum of two squares. If possible, say $\tilde{m}=x_{2}^{2}+x_{3}^{2}$, so we simply halt and return $\gamma$ corresponding to (6.1). However, if $\tilde{m}$ may not be represented as a sum of two squares, we simply move on to the next value of $m$ and try this process again. If this fails for all $m$ arising from $k$, we increment $k$ and run Lenstra’s algorithm for the new inequalities.

Supposing we have halted and constructed $\gamma$, we compute $\delta_{1}$ and $\delta_{2}$ guaranteed by Lemma 1. These are efficiently approximable by §5 to $\gamma_{1}$ and $\gamma_{2}$, respectively. Chaining together the three approximations as $\gamma_{1}\gamma\gamma_{2}$ gives the final desired approximation to $g$.

We begin the analysis by establishing the $\tau$-count and tightness of the approximation. In particular, $d(\gamma_{1},\delta_{1})<\varepsilon$ and $d(\gamma_{2},\delta_{2})<\varepsilon$ with factorization lengths of $\gamma_{\ell}$ each up to $(1+o(1))\log_{59}(\nicefrac{{1}}{{\varepsilon^{3}}})$. By Lemma 1, $d(\gamma,\delta_{1}\gamma\delta_{2})<C\varepsilon$. Therefore, $d(g,\gamma_{1}\gamma\gamma_{2})<(C+2)\varepsilon$ (by the triangle inequality) and since $\gamma$ has a factorization of $\tau$-count up to $\left(\frac{1}{3}+o(1)\right)\log_{59}(\nicefrac{{1}}{{\varepsilon^{3}}})$, this constitutes a factorization of an element in $g$’s neighborhood of $\tau$-count up to $\left(\frac{7}{3}+o(1)\right)\log_{59}(\nicefrac{{1}}{{\varepsilon^{3}}})$.

The efficiency of this algorithm—that is, that it runs in time $O(\operatorname{poly}\log(\nicefrac{{1}}{{\varepsilon}}))$—is because we expect to halt when $59^{k}\varepsilon\in O(1)$ (so only $k\approx\frac{1}{3}\log_{59}(\nicefrac{{1}}{{\varepsilon^{3}}})$ calls are expected), and only call polynomially-many polynomial-time subroutines. The dominant subroutines are calls to Lenstra’s algorithm which as shown in [7] runs in time polynomial in the size of the constraints for any fixed dimension $n$. Indeed, here we have only $n=2$ dimensions, $m=6$ linear constraints (two per absolute value), and the largest value $a$ in the constraints is $\eta^{k}$, so the runtime is polynomial in $nm\log a\in\Theta(k)$.

The reason we expect to halt when $59^{k}\varepsilon\in O(1)$ is that heuristically, we expect to halt when the area enclosed by (6.4)–(6.7) is $O(\operatorname{poly}\log(\nicefrac{{1}}{{\epsilon}}))$. Conveniently, the region is a rectangle since the vectors $\langle 1,\varphi\rangle$ and $\langle 1,\varphi^{\bullet}\rangle$ are orthogonal, so assuming in the limit that $\varepsilon\ll\min\left\{\left\lvert\alpha\right\rvert,\frac{1-\left\lvert\alpha\right\rvert^{2}}{\left\lvert\alpha\right\rvert}\right\}$ (so that (6.5) and the “bottom” inequality of (6.4) are redundant), we compute length-times-width of

whence we find $k\in(1+o(1))\log_{59}(\nicefrac{{1}}{{\varepsilon}})$ as expected.

When attempting to write elements of $\mathcal{O}$ as a sum of two squares, we primarily rest on a belief, in the style of Cramér’s conjecture and a conjecture of Sardari [23, ($*$)] that sums of squares are dense in $\mathbb{N}$. Seeking to analogize [23, ($*$)] in particular, we note that the operative aspect is that a dense cluster of lattice points will represent at least one sum of two squares, and that such a point thus will be found quickly through Lenstra’s algorithm.

The significance of this result is to accomplish a factorization in $\operatorname{PU}(2)$ in analogue to [25], but using a gate set with additional desirable properties beyond those enjoyed by the Clifford+$T$ gates.