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 operators 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. However, 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 including $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 recursively 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 implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to $54\pm 3\%$ when using the $Z$-rotation catalyst circuit approach and by up to $33\pm 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.
Although single-qubit synthesis algorithms have been well studied within the quantum compilation literature, they typically do not yet support the variety of available base gates and do not optimise with respect to individual gate costs of implementation. In this work we use an exhaustive search algorithm, based on Dijkstra’s pathfinding algorithm, to find cost-optimal sequences for random target single-qubit gates. It is compatible with arbitrary sets of universal base gates with individually assigned costs, enabling us to explore potential cost benefits from including higher order Clifford hierarchy base gates. We calculate the synthesis cost against error scaling relations and compare between the canonical Clifford+T set of base gates and the sets resulting from accumulatively including Z-rotation gates from increasing orders of the Clifford hierarchy. Two gate implementation approaches were used to assign resource costs to gates from each order of the hierarchy. The first approach reduces the gate costs to T-counts by using a Z-rotation catalyst circuit to implement the gates. This resulted in the scaling factor decreasing by up to 54±3%. The second approach assigns the costs as the average number of raw magic states required to directly distil and implement the gates fault-tolerantly. This approach decreased the scaling factor by up to 33±2%.
The results of our paper demonstrate that the resource requirements of synthesis algorithms could be considerably improved by including higher orders of the Clifford hierarchy as base gates and optimising with respect to individually assigned gate costs.
 Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. 10.1063/1.1499754.
 Robert Raussendorf, Jim Harrington, and Kovid Goyal. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9 (6): 199, 2007. 10.1088/1367-2630/9/6/199.
 David S Wang, Austin G Fowler, and Lloyd CL Hollenberg. Surface code quantum computing with error rates over 1%. Physical Review A, 83 (2): 020302, 2011. 10.1103/PhysRevA.83.020302.
 Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Physical Review Letters, 102 (11): 110502, 2009. 10.1103/PhysRevLett.102.110502.
 Xinlan Zhou, Debbie W Leung, and Isaac L Chuang. Methodology for quantum logic gate construction. Physical Review A, 62 (5): 052316, 2000. 10.1103/PhysRevA.62.052316.
 A Yu Kitaev, AH Shen, and MN Vyalyi. Classical and Quantum Computation (Graduate Studies in Mathematics vol 47)(Providence, RI: American Mathematical Society). 2002. 10.1090/GSM/047.
 Austin G Fowler. Constructing arbitrary Steane code single logical qubit fault-tolerant gates. Quantum Information & Computation, 11 (9-10): 867–873, 2011.
 Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information & Computation, 6 (1): 81–95, 2006. ISSN 1533-7146.
 Alex Bocharov and Krysta M Svore. Resource-optimal single-qubit quantum circuits. Physical Review Letters, 109 (19): 190501, 2012. 10.1103/PhysRevLett.109.190501.
 Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and $T$ gates. Quantum Information & Computation, 13 (7–8): 607–630, 2013a. ISSN 1533-7146.
 Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and $T$ circuits. IEEE Transactions on Computers, 65 (1): 161–172, 2016. 10.1109/TC.2015.2409842.
 Neil J Ross and Peter Selinger. Optimal ancilla-free clifford+$t$ approximation of z-rotations. Quantum Information & Computation, 16 (11-12): 901–953, 2016.
 Simon Forest, David Gosset, Vadym Kliuchnikov, and David McKinnon. Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets. Journal of Mathematical Physics, 56 (8): 082201, 2015. 10.1063/1.4927100.
 Peter Selinger. Efficient Clifford+$T$ approximation of single-qubit operators. Quantum Information & Computation, 15 (1–2): 159–180, 2015. ISSN 1533-7146.
 Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Asymptotically optimal approximation of single qubit unitaries by Clifford and $T$ circuits using a constant number of ancillary qubits. Physical Review Letters, 110 (19): 190502, 2013b. 10.1103/PhysRevLett.110.190502.
 Alex Bocharov, Martin Roetteler, and Krysta M Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A, 91 (5): 052317, 2015. 10.1103/PhysRevA.91.052317.
 Daniel Gottesman and Isaac L Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390, 1999. 10.1038/46503.
 Craig Gidney and Austin G Fowler. Efficient magic state factories with a catalyzed $| CCZ\rangle $ to $2| T\rangle $ transformation. Quantum, 3: 135, 2019. 10.22331/Q-2019-04-30-135.
 Earl T Campbell and Joe O’Gorman. An efficient magic state approach to small angle rotations. Quantum Science and Technology, 1 (1): 015007, 2016. 10.1088/2058-9565/1/1/015007.
 Joshua M Brown, Terry Bossomaier, and Lionel Barnett. Review of data structures for computationally efficient nearest-neighbour entropy estimators for large systems with periodic boundary conditions. Journal of Computational Science, 23: 109–117, 2017. 10.1016/J.JOCS.2017.10.019.
 Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40 (4): 175–179, 1991. 10.1016/0020-0190(91)90074-r.
 Peter N Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda, volume 93, pages 311–21, 1993.
 Tien Trung Pham, Rodney Van Meter, and Clare Horsman. Optimization of the Solovay-Kitaev algorithm. Physical Review A, 87 (5): 052332, 2013. 10.1103/PhysRevA.87.052332.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.