The surface code, among other high-threshold codes, is limited to a small set of Clifford gates
over logical qubits that can be performed with relative ease. A procedure called magic state
distillation can be used to perform a wider range of non-Clifford gates fault-tolerantly, such as the
T := R
z
(π/4) gate (up to global phase), which cannot be produced using only Clifford gates [5, 6].
Initially, raw magic states are surgically injected into the code and with the aid of state distillation
procedures, a number of raw magic states are consumed to produce a smaller number of more
robust magic states. In principle, the procedures can be recursively applied to obtain states
with arbitrarily low noise, although requiring large amounts of physical resources. These purified
magic states can then be consumed to fault-tolerantly perform corresponding gates using quantum
teleportation circuits. Distillation procedures only exist for a subset of gates, in order to implement
arbitrary unitary gates, the Solovay-Kitaev (SK) theorem can be used. The SK theorem states
that a universal set of n-qubit gates generate a group dense in SU(2
n
) (Special Unitary), and the
set fills SU(2
n
) relatively quickly. Hence single-qubit base gates that form a universal set can be
multiplied in sequence to approximate any single-qubit gate to arbitrary precision [7, 8].
A frequently used set of single-qubit universal base gates for fault-tolerant quantum compu-
tation are the Clifford+T gates, where the Clifford gates are relatively cheap to apply while the
T gate requires a considerable amount of resources due to the magic state distillation proce-
dure. This set of gates and how they can be used to synthesise arbitrary single-qubit gates is a
well studied topic within the quantum compilation literature. Gate synthesis algorithms, besides
brute-force [9], began with the Solovay-Kitaev algorithm [8, 10]. It initially searches for a base
sequence that roughly approximates a target gate and then uses a recursive strategy to append
other base sequences in such a way that the new sequence approximates a gate that is closer to the
target gate with distance reducing efficiently with the number of iterations. It is compatible with
arbitrary single-qubit universal gate sets, provided that they include each gate’s adjoint. The SK
algorithm has room for optimisation with respect to lengths of resulting gate sequences since the
recursive process generates strings of disjoint subsequences which are only individually optimised,
rather than optimising over the entire sequence. In 2008, Matsumoto and Amano [11] developed
a normal form for sequences of Clifford+T gates that produces unique elements in SU (2). Shortly
after, Bocharov and Svore [12] introduced their canonical form which extends the normal form by
instead producing unique elements in P SU(2) (Projective Special Unitary) which more concisely
describes the space of all physical single-qubit gates by ignoring global phase. This normal form
can be used to enumerate length optimal sequences of Clifford+T base gates which produce dis-
tinct gates, considerably reducing the size of the sequence configuration space for search algorithms
(although still growing exponentially with respect to sequence length).
More recently, there has been significant progress on developing direct synthesis methods which
are not based on search. For target single-qubit unitary gates that can be exactly produced by
Clifford+T base gate sequences, a method was developed that optimally and efficiently finds these
exact sequences directly [13]. This was later used as a subroutine in algorithms for optimal synthesis
of arbitrary single-qubit Z-rotations [14, 15]. Direct Clifford+T base gate synthesis methods for
Z-rotations have since been generalised to Clifford+cyclotomic (Z-rotation by π/n) sets of base
gates [16] and sets derived from totally definite quaternion algebras [17]. For arbitrary single-qubit
rotations (not necessarily Z-rotations) there has been a number of other approaches developed,
such as a randomised algorithm that uses the distribution of primes [18], asymptotically optimal
synthesis using ancilla qubits [19], and probabilistic quantum circuits with fallback [20].
It is common within the quantum compilation literature for synthesis algorithms to optimise
sequences based on minimising the total number of gates that require magic state injection. This
measure is well-suited to the Clifford+T set of base gates which are standard for gate synthesis
algorithms, since the T gate and its adjoint are the only gates with a significantly higher cost
than the Clifford gates. However, procedures exist for performing alternative gates to the T
gate that vary in implementation cost. Examples of such gates are found within the Clifford
hierarchy, which is an infinite discrete set of gates that are universal and can be performed on
certain error-correcting codes fault-tolerantly [21]. The resource cost of implementation typically
varies between orders of the hierarchy. Thus to accurately cost optimise sequences from such sets
of gates, the cost of each individual base gate should be considered. We investigate two different
approaches for implementing Z-rotation gates from the Clifford hierarchy and calculating their
resource costs. The first approach is based on a circuit that uses a catalyst Z-rotation state
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 2