Icosahedral golden gates

This page contains information about and code for the paper "Fast Navigation with Icosahedral Golden Gates" by T. Blackman and Z. Stier.

In "Short paths in PU(2)," an algorithm is described and implemented for producing factorizations using the Clifford+T gate set to within specified precision of length at most 7/3 times the theoreical upper bound. In this paper we describe and implement an analogous algorithm for the icosahedral golden gate set. The advantages of this set are: the logarithm's base is 59, as opposed to 2, leading to an improvement by a factor of log₂59; and the icosahedral gates act on the corresponding 60-regular graph edge-transitively (as opposed to merely vertex-transitively).

Click here to download all files zipped. Below is also a link to each file and with short description of the important methods within. Please write to zstier (at) berkeley (dot) edu if any method in the code is not adequately explained here. UPDATE (Summer 2024): code is now Python 3 (was previously only compatible with Python 2).

• approx.py: the key method in this file is approx, a function which takes the top row of a not-necessarily-normalized (but nonzero) unitary matrix and a precision ε and returns a factored approximation to the corresponding determinant-1 matrix, to within a small constant times ε in d.
• convex.py:
  • Interval: a class for handling intervals on the real line. intersect intersects two intervals and intersectZ intersects the given interval with the integers.
  • HyperplaneSolid: a class for convex sets in real n-space, provided as a list of inequalities. The class' operating assumptions are that it is only ever given bounded convex sets of posiitve volume, and that n+1 hyperplane boundaries never meet at a point. Hyperplanes are provided one-by-one using enter. check will query if a given point lies in the set. findCorners gives a list of all corners of the set. Znpoints runs Lenstra's algorithm on the convex set (as of summer 2021 only n=2 is supported).
• diagonal.py: the key method in this file is diag, a function which takes an angle and a precision ε and returns a factored approximation to the corresponding rotation matrix, to within ε in d.
• quaternions.py:
  • HZphi: a class for handling the Hamilton quaternion algebra H(Z[φ]). Elements can be manipulated mostly like other numbers in Python.
  • C: a list explicitly containing all sixty elements of the alternating group A₅, generated by ρ and σ in PU(2).
  • TeX: a dictionary where TeX[i] gives a LaTeX representation of an element giving rise to C[i].
  • factorGamma: a function for factoring elements of <ρ,σ,τ>.
  • TeXGamma: a function for returning a LaTeX-friently form of the output of factorGamma.
• rings.py:
  • Zphi: a class for handling the ring Z[φ]. Elements can be manipulated mostly like other numbers in Python. Special methods include gcd and factor.
  • Ziphi: a class for handling the ring Z[i,φ]. Elements can be manipulated mostly like other numbers in Python. Special methods include gcd.
  • twoSquares: a function that takes in an instance of Zphi and always outputs a pair of Zphi instances, which either have squared-sum the input, or are both None.
• vectors.py:
  • nearestInLattice: a function for finding the lattice element nearest a given point (written with respect to the lattice's basis) with respect to the 2-norm.
  • GramSchmidt: a function for computing the Gram–Schmidt process.
  • LLL: a function for computing the Lovasz–Lovasz–Lenstra lattice reduction.
• Ziphi_dict.py: contains a single object, the quadruply-nested list of 4-tuples D, which represents the displacements necessary to make the proof of Z[i,φ]'s norm-Euclideanness go through. D was computed with code nearly identical to the block provided in the paper.