# Cost-optimal single-qubit gate synthesis in the Clifford hierarchy

1School of Physics, University of Melbourne, VIC, Parkville, 3010, Australia
2School of Mathematics and Statistics, University of Melbourne, VIC, Parkville, 3010, Australia

### Abstract

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.

Performing large scale complex quantum algorithms will require the use of robust error-correction protocols over encoded qubits. However, these protocols present unique challenges that need to be overcome in order to achieve universal quantum computation. In general, many logic gate operations used in quantum algorithms cannot be directly applied to encoded quantum states. Logic gate operations that can be directly applied transversally over the encoded qubits are considered to be easy to implement because they are inherently fault tolerant and hence require relatively small numbers of physical gates. In addition, there are gates that can be fault-tolerantly implemented, but require resource intensive magic state distillation procedures. These gates, together with the transversal gates, form universal sets of base gates that can be used to approximate any unitary gate up to arbitrary precision by using gate synthesis algorithms to generate corresponding sequences of base gates. Within the quantum compilation literature, gate synthesis primarily focuses on the Clifford+T set of universal base gates where the T gate is implemented through magic state distillation. However, other universal sets of base gates exist that can be implemented fault-tolerantly in error correction codes. For instance, by including gates from higher orders of the Clifford hierarchy, where the resource cost of gate implementation increases for increasing orders of the hierarchy.

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.

### ► References

[1] Sergey B Bravyi and A Yu Kitaev. Quantum codes on a lattice with boundary. arXiv preprint quant-ph/​9811052, 1998.
arXiv:quant-ph/9811052

[2] 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.
https:/​/​doi.org/​10.1063/​1.1499754

[3] 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.
https:/​/​doi.org/​10.1088/​1367-2630/​9/​6/​199

[4] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.83.020302

[5] Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Physical Review Letters, 102 (11): 110502, 2009. 10.1103/​PhysRevLett.102.110502.
https:/​/​doi.org/​10.1103/​PhysRevLett.102.110502

[6] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.62.052316

[7] Michael A. Nielsen and Isaac L. Chuang. The Solovay–Kitaev theorem, page 617–624. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.019.
https:/​/​doi.org/​10.1017/​CBO9780511976667.019

[8] 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.
https:/​/​doi.org/​10.1090/​GSM/​047

[9] Austin G Fowler. Constructing arbitrary Steane code single logical qubit fault-tolerant gates. Quantum Information & Computation, 11 (9-10): 867–873, 2011.

[10] Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information & Computation, 6 (1): 81–95, 2006. ISSN 1533-7146.

[11] Ken Matsumoto and Kazuyuki Amano. Representation of quantum circuits with Clifford and $\pi/​8$ gates. arXiv preprint arXiv:0806.3834, 2008.
arXiv:0806.3834

[12] Alex Bocharov and Krysta M Svore. Resource-optimal single-qubit quantum circuits. Physical Review Letters, 109 (19): 190501, 2012. 10.1103/​PhysRevLett.109.190501.
https:/​/​doi.org/​10.1103/​PhysRevLett.109.190501

[13] 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.

[14] 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.
https:/​/​doi.org/​10.1109/​TC.2015.2409842

[15] Neil J Ross and Peter Selinger. Optimal ancilla-free clifford+$t$ approximation of z-rotations. Quantum Information & Computation, 16 (11-12): 901–953, 2016.

[16] 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.
https:/​/​doi.org/​10.1063/​1.4927100

[17] Vadym Kliuchnikov, Alex Bocharov, Martin Roetteler, and Jon Yard. A framework for approximating qubit unitaries. arXiv preprint arXiv:1510.03888, 2015.
arXiv:1510.03888

[18] Peter Selinger. Efficient Clifford+$T$ approximation of single-qubit operators. Quantum Information & Computation, 15 (1–2): 159–180, 2015. ISSN 1533-7146.

[19] 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.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.190502

[20] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.91.052317

[21] 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.
https:/​/​doi.org/​10.1038/​46503

[22] 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.
https:/​/​doi.org/​10.22331/​Q-2019-04-30-135

[23] Craig Gidney. Halving the cost of quantum addition. Quantum, 2: 74, 2018. 10.22331/​Q-2018-06-18-74.
https:/​/​doi.org/​10.22331/​Q-2018-06-18-74

[24] 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.
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007

[25] Earl T Campbell and Mark Howard. Magic state parity-checker with pre-distilled components. Quantum, 2: 56, 2018. 10.22331/​Q-2018-03-14-56.
https:/​/​doi.org/​10.22331/​Q-2018-03-14-56

[26] 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.
https:/​/​doi.org/​10.1016/​J.JOCS.2017.10.019

[27] 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.
https:/​/​doi.org/​10.1016/​0020-0190(91)90074-r

[28] Peter N Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda, volume 93, pages 311–21, 1993.

[29] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.87.052332

### Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-17 13:59:19). On SAO/NASA ADS no data on citing works was found (last attempt 2022-05-17 13:59:20).