Cost-optimal single-qubit gate synthesis in the
Clifford hierarchy
Gary J. Mooney
1
, Charles D. Hill
1,2
, and Lloyd C.L. Hollenberg
1
1
School of Physics, University of Melbourne, VIC, Parkville, 3010, Australia.
2
School of Mathematics and Statistics, University of Melbourne, VIC, Parkville, 3010, Australia.
For universal quantum computation, a major challenge to overcome for practical
implementation is the large amount of resources required for fault-tolerant quantum
information processing. An important aspect is implementing arbitrary unitary oper-
ators built from logical gates within the quantum error correction code. A synthesis
algorithm can be used to approximate any unitary gate up to arbitrary precision by
assembling sequences of logical gates chosen from a small set of universal gates that are
fault-tolerantly performable while encoded in a quantum error-correction code. How-
ever, current procedures do not yet support individual assignment of base gate costs and
many do not support extended sets of universal base gates. We analysed cost-optimal
sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the
canonical Clifford+T set of base gates and compared them to when additionally in-
cluding Z-rotations from higher orders of the Clifford hierarchy. Two approaches of
assigning base gate costs were used. First, costs were reduced to T-counts by recur-
sively applying a Z-rotation catalyst circuit. Second, costs were assigned as the average
numbers of raw (i.e. physical level) magic states required to directly distil and imple-
ment the gates fault-tolerantly. We found that the average sequence cost decreases by
up to 54±3% when using the Z-rotation catalyst circuit approach and by up to 33±2%
when using the magic state distillation approach. In addition, we investigated observed
limitations of certain assignments of base gate costs by developing an analytic model
to estimate the proportion of sets of Z-rotation gates from higher orders of the Clifford
hierarchy that are found within sequences approximating random target gates.
1 Introduction
Quantum computing has the potential to solve many real-world problems by using significantly
fewer physical resources and computation time than the best known classical algorithms. The
quantum algorithms for these problems are implemented using deep quantum circuits. Thus to
reliably implement these circuits, qubits within the devices require long coherence times and high
precision control. Current systems consist of physical qubits that are too noisy for large scale
computation. Error-correction schemes provide the ability to overcome this hurdle by entangling
clusters of physical qubits in such a way that they collectively encode the information into more
robust logical qubits. In principle, when physical qubits have error-rates below the error threshold
of the error-correction scheme, logical qubits within the code can be made arbitrarily robust using
increasing numbers of qubits. A particular error-correction scheme with relatively high physical
error threshold of approximately 1% is the surface code, which is implemented over a nearest-
neighbour two-dimensional physical layout, making it one of the most realistically implementable
schemes [14]. In this work, we analyse the resource costs for gate synthesis, which is used to
fault-tolerantly implement arbitrary unitary gates in error-correction codes.
Gary J. Mooney: mooneyg@unimelb.edu.au
Charles D. Hill: cdhill@unimelb.edu.au
Lloyd C.L. Hollenberg: lloydch@unimelb.edu.au
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 1
arXiv:2005.05581v3 [quant-ph] 1 Feb 2021
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
to implement two copies of its corresponding Z-rotation gate using a small number of T gates
while retaining the initial Z-rotation state [22, 23]. This circuit can enable the average resource
costs of implementing Z-rotation gates from the Clifford hierarchy to be expressed as T -counts.
Using this approach, costs could be calculated either by assuming that output gates are applied
directly to target qubits or by assuming that all output gates are first applied to |+i states to form
intermediate magic states, which can then be consumed to implement the corresponding gates onto
target qubits at any time. As an alternative to the Z-rotation catalyst circuit approach of gate
implementation, the second approach is to use the average number of raw magic states required
to directly distil and implement subsets of gates belonging to the Clifford hierarchy in surface
codes. The distillation costs have already been calculated by Campbell and O’Gorman [24] for
various levels of precision, the accumulated costs of distilling and then implementing the gates are
found within their supplementary materials. Although other factors relating to physical resources
are important to consider such as qubit count, circuit depth, magic state distillation methods, and
details of the error-correction implementation, the number of raw magic states can serve as a rough
approximation to the cost of implementing fault-tolerant logical gates on surface codes.
We introduce an algorithm, based on Dijkstra’s shortest path algorithm, that generates a
database of all cost-optimal sequences below a chosen maximum sequence cost where each sequence
produces distinct gates in PSU (2). The algorithm supports arbitrary universal sets of single-qubit
base gates with individually assigned cost values. The database can then be searched to find a
sequence approximating a specified target gate. We use this algorithm to compare the cost of cost-
optimal gate synthesis between the canonical Clifford+T base gate set and various sets of base gates
consisting of Clifford gates and Z-rotations from higher orders of the Clifford hierarchy. Each set of
logical base gates is compared by calculating how the average gate sequence cost for approximating
random target gates scales with respect to reaching target gate synthesis logical error rates. When
including Z-rotation base gates from higher orders of the Clifford hierarchy with T-counts assigned
using the Z-rotation catalyst approach, we find that the average cost-optimal sequence T -counts
can potentially be reduced by over 50% when output gates are directly applied to target qubits
and by over 30% when intermediate magic states are used. When using the alternative approach
of assigning costs from direct magic state distillation, we find that by including Z-rotation logical
base gates from the fourth order of the Clifford hierarchy, the average cost-optimal sequence costs
can be reduced by 30%. These cost reductions indicate that a significant amount of resources could
be saved by adapting current synthesis algorithms to include higher orders of the Clifford hierarchy
and to optimise sequences with respect to individual gate costs.
In the cases when costs are assigned using the Z-rotation catalyst method via intermediate
magic states or when assigned using direct magic state distillation, we observe that there is only a
small improvement to the average costs of synthesis when Z-rotations of orders higher than four
of the Clifford hierarchy are included as base gates. We investigate this behaviour by developing
a model to estimate the proportion of Z-rotation base gates from specified orders of the Clifford
hierarchy within sequences approximating random target gates, without needing to generate the
database of sequences. The proportions calculated in this manner closely fit results obtained using
the sequence generation algorithm to approximate uniformly distributed random target gates. The
parameters of the calculation include the maximum sequence cost and separate logical base gate
costs for each order of the Clifford hierarchy, which can be readily be extended to specify costs for
individual logical base gates.
Results
Base Gates From The Clifford Hierarchy
The Clifford hierarchy is an infinite discrete set of gates that are universal for the purposes of
quantum computation and can be fault-tolerantly performed on certain error-correcting codes.
Each order of the hierarchy is defined as
C
l
:= {U | UP U
C
l1
, P P}, (1)
noting that C
1
= P is the set of Pauli gates, C
2
is the set of Clifford gates and C
3
includes, among
others, the Pauli basis rotations by π/4 such as the T gate. Higher order gates typically correspond
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 3
Figure 1: A Z-rotation catalyst circuit [22, 23]. The rotations R
z
(2πk/2
n
) are elements of T
n
(as shown in
Eq. 2) where k is an odd integer and n is a natural number. The circuit utilises a |T
n
i state, a |T i state, three
T
3
gates and a T
n1
gate to perform two T
n
gates on two separate qubits while retaining the original |T
n
i state.
The output T
n
gates can either be applied directly to target qubits or |ψ
0
i and |ψ
1
i states can be first set to |+i
states, so that the application of the T
n
gates prepare two |T
n
i states which can then be used to implement T
n
gates at any time and on any target qubit using teleportation circuits. However, this consumes on average an
additional half a T
n1
gate for the implementation of each T
n
gate. The two sets of grouped gates (outlined by
dashed lines) correspond to logical-AND computation and uncomputation circuits, which only requires a total
T -count of four to implement [23]. The circuit can be recursively applied until the R
z
(2πk/2
n1
) gate position
reduces down to a T
3
gate which has a cost of 1. All costs are calculated by assuming that all target gates at
each recursive level of the circuit are used at some point (i.e. that no output gates are wasted).
to finer angle rotations.
In this work, we compare sets of single-qubit universal logical base gates consisting of Clifford
gates and Z-rotation gates from higher orders of the Clifford hierarchy. Although only higher order
Z-rotations are included, they can be readily converted to other gates in the same order of the
Clifford hierarchy by multiplying gates from lower orders. In particular, by multiplying Clifford
gates, other gates of the same order are generated for the same cost. For example Z.R
z
(π/4) =
R
z
(5π/4) and H.R
z
(π/4).H = R
x
(π/4) up to global phase, where H is the Hadamard gate and Z
is the Pauli-Z gate. These sets of logical base gates are compared with respect to the optimal
resource costs resulting from gate synthesis for random target gates. Each set of Z-rotation gates
from order 3 l 7 of the Clifford hierarchy, denoted T
l
, can be written as
T
3
:=
R
z
πk
4
C
3
| k {−1, 1}
,
T
4
:=
R
z
πk
8
C
4
| k {−3, 1, 1, 3}
,
T
5
:=
R
z
πk
16
C
5
| k {−7, 5, . . . , 5, 7}
,
T
6
:=
R
z
πk
32
C
6
| k {−15, 13, . . . , 13, 15}
, and
T
7
:=
R
z
πk
64
C
7
| k {−31, 29, . . . , 29, 31}
. (2)
The five sets of logical base gates used in our analysis are then constructed as
Set
1
:= C
1
C
2
T
3
,
Set
2
:= Set
1
T
4
,
Set
3
:= Set
2
T
5
,
Set
4
:= Set
3
T
6
, and
Set
5
:= Set
4
T
7
. (3)
Calculating precise resource costs of implementing each gate fault-tolerantly is an extensive
task that would need to consider a variety of factors such as qubit count, circuit depth, magic state
distillation methods and details of the error-correction implementation. As an approximation for
the cost of these logical gates we investigate two approaches of assigning costs to individual T
l
gates, where gates from C
1
and C
2
are assumed to be free since they can be implemented in a
relatively straightforward way. The first approach can associate the costs with the T -count, which
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 4
(a) Direct application of T
l
method
Average T -count per base gate
T
3
1
T
4
2.5
T
5
3.25
T
6
3.625
T
7
3.8125
(b) Application of T
l
via |T
l
i method
Average T -count per base gate
T
3
1
T
4
3
T
5
5
T
6
7
T
7
9
Table 1: The average number of T gates required to implement a single qubit Z-rotation gate from order l
of the Clifford hierarchy T
l
using the Z-rotation catalyst approach. (a) The average T -count required to
implement T
l
gates by directly applying them to target qubits. The T -counts are calculated using the expression
Cost[T
l
] = 4 3 × 2
3l
as shown in Equation 5. (b) The average T -count required to implement T
l
gates by
applying them via intermediate |T
l
i states at every level of recursion (since the Z-rotation catalyst circuit is
recursively applied). The T -counts are calculated using the expression Cost[T
l
] = 1 + 2 × (l 3) as shown in
Equation 7.
Average raw magic state count per base gate
Base gate error rate µ 10
5
10
10
10
15
10
20
T
3
5.1 36.2 70.4 120.1
T
4
16.7 103.1 186.5 358.7
T
5
34.8 172.7 333.2 635.8
T
6
49.0 255.8 486.1 962.2
T
7
64.7 344.8 671.5 1351.2
Table 2: The average raw magic state count required for distillation and implementation of corresponding logical
base gates, obtained from the supplementary materials of [24]. Each column contains the cost of distilling and
implementing a logical Z-rotation gate from order l of the Clifford hierarchy T
l
to below a gate error rate µ
calculated using the diamond norm. The raw magic state physical level error is assumed to be 0.1%.
is used as the standard metric for measuring the costs of gate sequences within the gate synthesis
literature. This can be done by using a Z-rotation catalyst circuit shown in Fig. 1, which was
introduced in [23] and presented in more detail in [22]. The circuit is similar to a synthillation
parity-check circuit described in [25]. It utilises a |T
l
i state and a small number of T gates to
perform two T
l
gates on two different qubits while retaining the original |T
l
i state. Costs can be
calculated by recursively applying this circuit, assuming that all output gates at each recursive
level are resourced (i.e. that no output gates are wasted). We calculate the costs using the Z-
rotation catalyst approach in two ways. The first assumes that output T
l
gates are directly applied
to target qubits. The recurrence relation for the T -counts using this method can be obtained as
Cost [T
l
] =
4 + Cost [T
l1
]
2
, (4)
where Cost[T
3
] = 1. Solving this results in the average number of T gates required to implement
a T
l
gate to be expressed as
Cost [T
l
] = 4 3 × 2
3l
, (5)
which is enumerated in Table 1a for 3 l 7. The second method of calculating the T-count
using the Z-rotation catalyst approach applies the T
l
gates to |+i states, creating corresponding
intermediate |T
l
i states, which are then consumed to implement the gates via teleportation circuits.
The recurrence relation for these costs can be obtained as
Cost [T
l
] = 2 + Cost [T
l1
] , (6)
where Cost[T
3
] = 1, resulting in the expression
Cost [T
l
] = 1 + 2 × (l 3) (7)
which is enumerated in Table 1b for 3 l 7. This second method is more expensive since the
teleportation circuit that consumes the |T
l
i state to implement the T
l
gate requires a T
l1
correction
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 5
gate to be applied 50% of the time. However, this method is more flexible in implementation since
the outputted |T
l
i states can be used at any time to implement T
l
gates onto any target qubits,
enabling more options when instruction scheduling. A realistic employment of the Z-rotation
catalyst approach would likely benefit from a combination of both direct application of T
l
gates
and application via their intermediate |T
l
i states. For the second approach of assigning resource
costs, we use the average number of raw magic states to implement fault-tolerant T
l
gates from
direct magic state distillation procedures. Resource costs have already been calculated for Y -
rotation gates R
y
(2π/2
l
) from the Clifford hierarchy by searching for optimal combinations of
various distillation protocols with respect to target gate synthesis error rates [24]. For integer
multiples R
y
(2πk/2
l
), the distillation protocols can be performed identically, hence they can be
assigned the same cost. To follow convention, the Y -rotation gates are converted to Z-rotation
gates with the same cost using the relation R
z
(θ) = HS
R
y
(θ)SH, since H and S := R
z
(π/2) have
zero cost due to being elements of C
2
. These resource costs vary between orders of the Clifford
hierarchy and are shown in Table 2.
Sequence Generation Algorithm
In this section, a sequence generation algorithm, based on Dijkstra’s algorithm, is developed that
generates a database of all cost-optimal single-qubit gate sequences below some maximum cost
using arbitrary sets of universal base gates which have individually assigned cost values. We use
this algorithm to help study the average cost of cost-optimal gate synthesis when including Z-
rotation gates from higher orders of the Clifford hierarchy as base gates. Due to the flexibility of
this algorithm, it could be used as a subroutine within other synthesis algorithms. For example, it
could be used as the base approximation step within the SK algorithm, enabling the SK algorithm
to consider individual base gate costs when synthesising target gates.
The sequence generation algorithm explores the space of sequence configurations using a tree
expansion as shown in Figure 2, where each node corresponds to a gate and each path from
the root node to any other node corresponds to a sequence of gates. Let B
n
be an element
of P SU(2) corresponding to the base gate of node n in the sequence tree. A combined gate S
n
of node n is calculated by multiplying all nodes within the branch from the root down to n,
i.e. S
n
:= B
n
0
· B
n
1
. . . B
n
k
, where n
i
is the i
th
node from the root node such that n
0
is the
root and n
k
is node n. The Lie algebra generator of S
n
in the Pauli basis is of the form of a
vector α
n
X + β
n
Y + γ
n
Z with real coefficients and can be written as (α
n
, β
n
, γ
n
). Each vector
represents a point in a ball of radius π/2 over the Pauli bases X, Y and Z. Thus each point within
the ball is a geometrical location corresponding to a single-qubit gate.
The pseudocode for the algorithm is shown in Algorithm 1. It works by expanding nodes in a
sequence tree (see Figure 2). All leaf (end) nodes of the sequence tree are stored in a minimum heap
data structure which sorts the leaf nodes based on their corresponding sequence cost in increasing
order. This determines the order of nodes to expand. The tree begins as a single identity gate at
the root node which is added as the first element to the leaf node heap. At each iteration, the
leaf node with the lowest sequence cost, i, is taken from the heap, which for the first iteration
would be the identity gate node. The vector (α
i
, β
i
, γ
i
) is calculated from the combined gate of the
corresponding node’s sequence. Before expanding a node in the sequence tree, we check whether
another node with the same combined gate vector has already been expanded, using a hashset data
structure. If the vector exists in the hashset, then the node is removed from the sequence tree and
the algorithm proceeds to the next iteration. This repeats until a unique vector is found. When
such a vector is found, it is added to the hashset for uniqueness checking in further iterations and
the corresponding node in the sequence tree is expanded by generating a child node for each base
gate. Each of these child nodes are added to the leaf node heap. To save computation time, adding
a child node to the sequence tree and the heap can be limited to when their corresponding vectors
are unique. Since vectors of sequences with lower costs are always added to the hashset before
those with higher costs, the hashset must only contain vectors corresponding to sequences with
the lowest cost among all sequences that produce equivalent combined gates. Thus, whenever a
vector is successfully added to the hashset, the corresponding sequence must be cost-optimal. The
cost-optimal vector and sequence pair can be stored in a data structure such as a k-d tree which
can be used to approximate target gates by geometrically searching for nearest neighbours in the
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 6
Figure 2: An example of a sequence tree used to relate logical base gates, gate sequences and combined gates
for the sequence generation algorithm. A node n corresponds to a single-qubit base gate B
n
and the root
node corresponds to the identity gate B
0
= I. A gate sequence corresponding to n is the sequence of logical
base gates along the path from B
0
to B
n
. A combined gate S
n
is calculated by multiplying all logical base
gates within the gate sequence in sequence order. In this example, B
1
, B
2
and B
3
are logical base gates where
B
1
= B
4
= B
7
= B
10
, B
2
= B
5
= B
8
= B
11
and B
3
= B
6
= B
9
= B
12
. In the sequence generation
algorithm, the leaf node with the lowest sequence cost is expanded by adding a child node as a new leaf node
for each gate in the set of logical base gates. All non-leaf nodes of the tree correspond to cost-optimal sequences
and they can be thought of as the cost-optimal sequence database generated by the algorithm. Although all
leaf nodes are depicted to be at the same depth in the tree, this is not always the case. At any point during
the sequence generation algorithm, a path of relatively expensive logical base gates may be much shorter than
a path of relatively cheap gates.
Algorithm 1 Cost-optimal sequence generation
1: procedure GenerateSequences(baseGates, maxCost)
2: sequenceDatabase new KdTreehNodei To store the cost-optimal sequences geometrically
3: sequenceTree new TreehNodei To relate nodes, sequences and combined gates
4: sequenceTree.SetRoot(Identity gate) Set the root node to the identity gate
5: sortedLeafNo des new MinHeaphNodei To order sequence tree leaf nodes based on sequence cost
6: uniqueVectors new HashsethVector3i To test whether sequences have the same combined gates
7: Add sequenceTree.root to sortedLeafNodes
8: while sortedLeafNodes not empty do
9: i sortedLeafNodes.Pop() Obtains and removes the leaf node with lowest sequence cost
10: if sequenceTree.SequenceCost(i) > maxCost then
11: return sequenceDatabase Complete! Ignore i and return cost-optimal sequences
12: end if
13: (α
i
, β
i
, γ
i
) sequenceTree.GetVector(i)
14: if (α
i
, β
i
, γ
i
) not in uniqueVectors then
15: Add i to sequenceDatabase The node i corresponds to a cost-optimal sequence
16: Add (α
i
, β
i
, γ
i
) to uniqueVectors
17: childNodes sequenceTree.GenerateChildren(i, baseGates)
Add base gates as child nodes of i
18: for all j in childNodes do
19: (α
j
, β
j
, γ
j
) sequenceTree.GetVector(j)
20: if (α
j
, β
j
, γ
j
) not in uniqueVectors then
21: Add j to sortedLeafNodes
22: else
23: Remove j from sequenceTree Vector corresponding to childNode j already found
24: end if
25: end for
26: end if
27: end while
28: end procedure
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 7
(a) Sequences using the Z-rotation catalyst approach
with directly applied output gates
1.2 1.4 1.6 1.8 2 2.2 2.4
-log
10
( )
0
2
4
6
8
10
12
14
16
Cost (T-count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
(b) Sequences using the Z-rotation catalyst approach
with output gates applied via intermediate magic
states
1.2 1.4 1.6 1.8 2 2.2 2.4
-log
10
( )
0
2
4
6
8
10
12
14
16
Cost (T-count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
Figure 3: Cost-optimal sequence T -counts calculated using the Z-rotation catalyst approach plotted against
synthesised target gate error rates of . Each point is the result of averaging the T -count for implementing 5000
random target gate. The synthesis logical errors are calculated using the trace distance (shown in Equation 8).
The logical base gates for each set of base gates are specified in Equation 3. The corresponding linear best fit
values for both plots are shown in Table 3. (a) A plot of sequence costs where base gates are assigned costs by
assuming that all output gates are directly applied to target qubits. Base gate costs are calculated using Eq. 5
and enumerated in Table 1a. The reductions in scaling factors relative to Set
1
are 34 ± 4%, 43 ± 2%, 49 ± 2%,
and 54 ± 3% for Set
2
, Set
3
, Set
4
, and Set
5
respectively, where uncertainties correspond to 95% confidence
intervals. These correspond to synthesis cost savings in the limit of small . (b) A plot of sequence costs where
base gates are assigned costs by assuming that output gates are applied to |+i states to form the corresponding
intermediate magic states, gates are then applied by consuming the magic states via teleportation circuits. Base
gate costs are calculated using Eq. 7 and enumerated in Table 1b. The reductions in scaling factors relative to
Set
1
are 29±3%, 31±3%, 31±4%, and 31±4% for Set
2
, Set
3
, Set
4
, and Set
5
respectively, where uncertainties
correspond to 95% confidence intervals. These correspond to synthesis cost savings in the limit of small .
space of vectors.
There is a notable further optimisation that could be implemented into Algorithm 1. During
the procedure, all non-leaf nodes within the sequence tree correspond to cost-optimal sequences
with unique combined gate vectors, that is, each path starting at the root node and ending at any
non-leaf node is a shortest path to the sequence’s unique combined gate. To see how this could be
helpful, first assume that an existing sequence tree needs to grow to a new maximum cost, such
that the leaf nodes need to expand multiple times along the same branch. Instead of searching
through every combination of base gates as children for a leaf node, the sequence tree itself can
be used as a sieve by iterating child nodes from the root that are known to be shortest paths.
The tree already contains optimal paths up to a certain depth, so this information could be used
to help avoid the tree branches expanding in directions that produce nonoptimal paths to unique
combined gates.
In Algorithm 1, cost-optimal sequences and their corresponding vectors are stored in a k-d
tree which uses the Euclidean distance on the vectors to organise the data. Due to the periodic
nature of the vectors, there is a small chance of failure in the k-d tree when searching for nearest
neighbours to points close to the boundary. With computational overhead, the k-d tree may be
modified to help overcome this [26], or a more appropriate data structure such as a vantage point
tree [27, 28] may be used instead. In general, further alternative data structures may be used such
as the geometric nearest-neighbour access tree [29].
Synthesis Results
Algorithm 1 was computed using the sets of logical base gates described in Eq. 3 with the assignment
of costs obtained from the two approaches of implementing base gates, where values are shown in
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 8
(a) Sequences with below µ = 10
5
logical base gate
error
1 1.2 1.4 1.6 1.8 2 2.2 2.4
-log
10
( )
0
10
20
30
40
50
60
70
80
Cost (Raw Magic State Count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
(b) Sequences with below µ = 10
10
logical base gate
error
1 1.5 2 2.5
-log
10
( )
0
100
200
300
400
500
600
Cost (Raw Magic State Count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
(c) Sequences with below µ = 10
15
logical base gate
error
1 1.5 2 2.5
-log
10
( )
0
200
400
600
800
1000
1200
Cost (Raw Magic State Count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
(d) Sequences with below µ = 10
20
logical base gate
error
1 1.2 1.4 1.6 1.8 2 2.2 2.4
-log
10
( )
0
200
400
600
800
1000
1200
1400
1600
1800
Cost (Raw Magic State Count)
Set 1
Set 1 Fit
Set 2
Set 2 Fit
Set 3
Set 3 Fit
Set 4
Set 4 Fit
Set 5
Set 5 Fit
Figure 4: Cost-optimal sequence costs averaged over 5000 random target gates with respect to target gate
synthesis logical error rates . The logical base gates used are specified in Eq. 3 with cost values (shown in
Table 2) assigned as the average number of raw magic states required to distil and implement them to below
a specified logical gate error. The synthesis logical errors are calculated using the trace distance (shown in
Equation 8). Corresponding linear best fit values are shown in Table 4. The pattern of the data about the
lines of best fit for each logical base gate set are similar between plots because for each of the logical base gate
errors, the ratios of the base gate cost values between orders of the Clifford hierarchy are similar, hence the cost
optimal sequences will be comparable. (a) Synthesis using logical base gate costs associated with µ = 10
5
logical gate error. (b) Synthesis using logical base gate costs associated with µ = 10
10
logical gate error. (c)
Synthesis using logical base gate costs associated with µ = 10
15
logical gate error. (d) Synthesis using logical
base gate costs associated with µ = 10
20
logical gate error.
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 9
Tables 1 and 2. A database was generated that is in the form of a k-d tree of cost-optimal sequences
up to some chosen maximum sequence cost. The sequences were organised in the k-d tree with
respect to the vectors corresponding to their combined gates. For a given target gate G, gate
synthesis was performed by searching for the lowest cost sequence among all nearest neighbours
of G up to a chosen synthesis error (distance), , between their combined gates and G. The errors
were computed using the trace distance defined as
dist(S, G) =
q
(2 |tr(S
G)|)/2, (8)
where S is a combined gate and G is the target gate. If such a sequence did not exist, then the
database was further generated to a higher cost and the process was repeated until a sequence was
found. Incrementally generating the cost-optimal sequence database in this manner helps avoid
over generation.
For each set of base gates with individual costs calculated for each approach of implementing
them, gate synthesis was performed on 5000 random target gates sampled from a uniform distri-
bution for a variety of synthesis error rates (calculated using Eq. 8 with respect to the sequences’
combined gates). Cost-optimal sequence T -counts calculated using the Z-rotation catalyst circuit
approach for the two methods of assigning base gate costs are plotted against synthesised target
gate error rates for each set of base gates in Figure 3. The corresponding linear best fit values for
each set of logical base gates and corresponding cost values are shown in Table 3. We can compare
the scaling factors of the fits between different sets of logical base gates to estimate changes in
average sequence costs as the synthesis error approaches zero. For the Z-rotation catalyst circuit
method that assumes all output gates are directly applied to target qubits (as opposed to using
intermediate magic states), we find cost savings relative to Set
1
of 34 ± 3%, 42 ± 2%, 49 ± 2%, and
54 ± 3% for Set
2
, Set
3
, Set
4
, and Set
5
respectively, where uncertainties correspond to 95% confi-
dence intervals. Data for a Set
6
that includes T
8
gates was also calculated, however no noticeable
improvement was found with sequence cost values being almost identical to Set
5
resulting in a cost
saving of 52 ± 3% relative to Set
1
. For the Z-rotation catalyst circuit method that assumes all
output gates are applied to |+i states forming intermediate magic states before consuming them
to perform the corresponding Z-rotation gate, we find cost savings relative to Set
1
of 29 ± 3%,
31±3%, 31 ±4%, and 31±4% for Set
2
, Set
3
, Set
4
, and Set
5
respectively. These results show that if
gate synthesis includes higher order Clifford hierarchy Z-rotation gates as base gates implemented
using the Z-rotation catalyst approach, then a T -count saving of over 50% could potentially be
achieved. Cost-optimal sequence raw magic state counts calculated using direct base gate distil-
lation and implementation procedures are plotted against synthesised target error rates for each
combination of base gates and cost values in Figure 4. Each of the four plots correspond to differ-
ent resource costs of distilling and implementing the logical base gates with corresponding logical
errors µ = 10
5
, 10
10
, 10
15
and 10
20
calculated using the diamond norm. The corresponding
linear best fit values for each set of logical base gates are shown in Table 4 and corresponding
cost values are shown in Table 2 (physical error rate assumed to be 0.1% in all calculations). The
pattern of the data about their lines of best fit for each base gate set are similar between plots.
This is because for each of the logical base gate errors, the ratios of the logical base gate cost
values between orders of the Clifford hierarchy are similar, hence the cost optimal sequences will
be comparable. For logical base gate errors µ = 10
5
, 10
10
, 10
15
and 10
20
, we find that Set
2
provides 23± 3%, 27 ± 2%, 30 ± 2% and 26 ± 3% reductions in scaling factor respectively compared
to Set
1
. For µ = 10
10
and 10
15
, we find that Set
3
provides 30 ± 3% and 33 ± 2% reductions in
scaling factor respectively compared to Set
1
, which are both approximately a further 3% savings
compared to Set
2
. No further improvements are noticeable in our data for these assignments of
cost values. These results show that for any error-correction scheme with distillation costs assigned
according to Table 2, using Set
2
(which includes T
4
as logical base gates) instead of the standard
Set
1
, reduces the average resource cost scaling factor with respect to the synthesis negative log-
error, log(
1
), by up to 30%. Additionally Set
3
can provide up to a further 3% reduction when
compared to Set
2
. Each method of assigning individual base gate costs that were used in this work
indicated that the resource requirements of synthesis algorithms may be considerably improved
by including higher orders of the Clifford hierarchy as logical base gates and by optimising with
respect to the individual costs of implementing them.
Accepted in Quantum 2021-01-20, click title to verify. Published under CC-BY 4.0. 10
(a) Linear fits using Z-rotation catalyst method
Base Gates Scaling Factor Constant
Set
1
10.46 ± 0.43 8.83 ± 0.73
Set
2
6.89 ± 0.22 4.96 ± 0.36
Set
3
6.05 ± 0.03 4.17 ± 0.06
Set
4
5.33 ± 0.06 3.18 ± 0.11
Set
5
4.84 ± 0.21 2.46 ± 0.34
(b) Linear fits using Z-rotation catalyst method via
magic states
Base Gates Scaling Factor Constant
Set
1
10.46 ± 0.43 8.83 ± 0.73
Set
2
7.47 ± 0.15 5.39 ± 0.26
Set
3
7.19 ± 0.12 5.13 ± 0.21
Set
4
7.21 ± 0.25 5.16 ± 0.38
Set
5
7.21 ± 0.25 5.15 ± 0.39
Table 3: Linear best fits with a confidence level of 95% for cost-optimal sequence costs averaged over random
target logical gates with respect to the negative log-error, log(
1
), for target gate synthesis calculated using
the trace distance (shown in Equation 8). The sequences are constructed using