Shorter quantum circuits via single-qubit gate approximation

Vadym Kliuchnikov1,2, Kristin Lauter3, Romy Minko4,5, Adam Paetznick1, and Christophe Petit6,7

1Microsoft Quantum, Redmond, WA, US
2Microsoft Quantum, Toronto, ON, CA
3Facebook AI Research, Seattle, WA, US
4University of Oxford, Oxford, UK
5Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, UK
6University of Birmingham, Birmingham, UK
7Université Libre de Bruxelles, Brussels, Belgium

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works [28] and [15], we show that taking probabilistic mixtures of channels to solve fallback [13] and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$\sqrt{\mathrm{T}}$ gate set we achieve an average non-Clifford gate count of $0.23\log_2(1/\varepsilon)+2.13$ and T-count $0.56\log_2(1/\varepsilon)+5.3$ with mixed fallback approximations for diamond norm accuracy $\varepsilon$.
This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$\sqrt{\mathrm{T}}$). We also provide detailed numerical results for Clifford+T and Clifford+$\sqrt{\mathrm{T}}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

► BibTeX data

► References

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis, ``Quantum supremacy using a programmable superconducting processor'' Nature 574, 505-510 (2019).

[2] Wojciech Banaszczyk ``Inequalities for convex bodies and polar reciprocal lattices in $R^n$'' Discrete & Computational Geometry 13, 217–231 (1995).

[3] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter, ``Elementary gates for quantum computation'' Physical Review A 52, 3457–3467 (1995).

[4] Andreas Blass, Alex Bocharov, and Yuri Gurevich, ``Optimal ancilla-free Pauli+V circuits for axial rotations'' Journal of Mathematical Physics 56, 122201 (2015).

[5] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, ``Lower bounds on the non-Clifford resources for quantum computations'' Quantum Science and Technology 5, 035009 (2020).

[6] Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo, ``Assessing requirements to scale to practical quantum advantage'' (2022).

[7] Jean Bourgainand Alex Gamburd ``A Spectral Gap Theorem in SU$(d)$'' Journal of the European Mathematical Society 14, 1455–1511 (2012).

[8] Alex Bocharov, Yuri Gurevich, and Krysta M. Svore, ``Efficient Decomposition of Single-Qubit Gates into V Basis Circuits'' Physical Review A 88, 1–13 (2013).

[9] Sergey Bravyiand Alexei Kitaev ``Universal quantum computation with ideal Clifford gates and noisy ancillas'' Phys. Rev. A 71, 022316 (2005).

[10] Sergey Bravyiand Robert König ``Classification of Topologically Protected Gates for Local Stabilizer Codes'' Phys. Rev. Lett. 110, 170503 (2013).

[11] Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore, ``Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes'' PRX Quantum 2, 020341 (2021).

[12] Alex Bocharov, Martin Roetteler, and Krysta M Svore, ``Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits'' Physical Review Letters 114, 080502 (2015).

[13] Alex Bocharov, Martin Roetteler, and Krysta M. Svore, ``Efficient synthesis of probabilistic quantum circuits with fallback'' Physical Review A 91, 052317 (2015).

[14] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, ``Quantum computing enhanced computational catalysis'' Phys. Rev. Research 3, 033055 (2021).

[15] Earl Campbell ``Shorter gate sequences for quantum computing by mixing unitaries'' Physical Review A 95 (2017).

[16] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, ``Theory of Trotter Error with Commutator Scaling'' Phys. Rev. X 11, 011020 (2021).

[17] Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren, ``Cryptographic Hash Functions from Expander Graphs'' Journal of Cryptology 22, 93–113 (2009).

[18] Henri Cohen ``Advanced Topics in Computional Number Theory'' Springer New York (2000).

[19] Henri Cohen ``A Course in Computational Algebraic Number Theory'' Springer Berlin Heidelberg (1993).

[20] Shorter Quantum Circuits Dataset (2023).

[21] Bryan Eastinand Emanuel Knill ``Restrictions on Transversal Encoded Quantum Gate Sets'' Phys. Rev. Lett. 102, 110502 (2009).

[22] 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, 082201 (2015).

[23] Daniel Gottesmanand Isaac L. Chuang ``Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations'' Nature 402, 390–393 (1999).

[24] Craig Gidneyand Austin G. Fowler ``Efficient magic state factories with a catalyzed $|CCZ⟩$ to $2|T⟩$ transformation'' Quantum 3, 135 (2019).

[25] Joachim von zur Gathenand Jürgen Gerhard ``Modern Computer Algebra'' Cambridge University Press (2013).

[26] Craig Gidney ``Halving the cost of quantum addition'' Quantum 2, 74 (2018).

[27] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo, ``An Algorithm for the T-Count'' Quantum Info. Comput. 14, 1261–1276 (2014).

[28] Matthew B. Hastings ``Turning gate synthesis errors into incoherent errors'' Quantum Information and Computation 17, 488–494 (2017).

[29] Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang, ``Efficient discrete approximations of quantum gates'' Journal of Mathematical Physics 43, 4445–4451 (2002).

[30] Kenneth Irelandand Michael Rosen ``A Classical Introduction to Modern Number Theory'' Springer New York (1990).

[31] Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl, ``Quantum circuits for isometries'' Phys. Rev. A 93, 032318 (2016).

[32] Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck, ``Introduction to UniversalQCompiler'' (2021).

[33] Nathaniel Johnston, David W. Kribs, and Vern I. Paulsen, ``Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps'' Quantum Info. Comput. 9, 16–35 (2009).

[34] Aleksandr Yakovlevich Khinchin ``A quantitative formulation of the approximation theory of Kronecker'' Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 12, 113–122 (1948).

[35] V Kliuchnikov, A Bocharov, M Roetteler, and J Yard, ``A Framework for Approximating Qubit Unitaries'' (2015).

[36] Phillip Kaye, Raymond Laflamme, and Michele Mosca, ``An Introduction to Quantum Computing'' Oxford University Press (2006).

[37] V Kliuchnikov, D Maslov, and M Mosca, ``Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits'' Physical Review Letters 110, 190502 (2013).

[38] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca, ``Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates'' Quantum Info. Comput. 13, 607–630 (2013).

[39] V Kliuchnikovand J Yard ``A framework for exact synthesis'' (2015).

[40] Guang Hao Lowand Isaac L. Chuang ``Optimal Hamiltonian Simulation by Quantum Signal Processing'' Phys. Rev. Lett. 118, 010501 (2017).

[41] Franz Lemmermeyer ``The Euclidean algorithm in algebraic number fields'' Expositiones Mathematicae 13, 385–416 (1995).

[42] H. W. Lenstra ``Integer Programming with a Fixed Number of Variables'' Mathematics of Operations Research 8, 538–548 (1983).

[43] Daniel Litinski ``A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery'' Quantum 3, 128 (2019).

[44] A. K. Lenstra, H. W. Lenstra, and L. Lovász, ``Factoring polynomials with rational coefficients'' Mathematische Annalen 261, 515–534 (1982).

[45] A. Lubotzky, R. Phillips, and P. Sarnak, ``Ramanujan graphs'' Combinatorica 8, 261–277 (1988).

[46] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson, ``Characterizing quantum gates via randomized benchmarking'' Phys. Rev. A 85, 042311 (2012).

[47] Emanuel Malvetti, Raban Iten, and Roger Colbeck, ``Quantum Circuits for Sparse Isometries'' Quantum 5, 412 (2021).

[48] Michael A. Nielsenand Isaac L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2012).

[49] Shorter Quantum Circuits Notebook (2023).

[50] Gabriele Nebe, Eric M. Rains, and Neil J.A. Sloane, ``Real and Complex Clifford Groups'' Springer Berlin Heidelberg (2006).

[51] Yunseong Nam, Yuan Su, and Dmitri Maslov, ``Approximate quantum Fourier transform with O(n log(n)) T gates'' npj Quantum Information 6, 26 (2020).

[52] Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater, ``Full Cryptanalysis of LPS and Morgenstern Hash Functions'' (2008).

[53] Eduardo Carvalho Pintoand Christophe Petit ``Better path-finding algorithms in LPS Ramanujan graphs'' Journal of Mathematical Cryptology 12, 191–202 (2018).

[54] Adam Paetznickand Krysta M. Svore ``Repeat-until-success: Non-deterministic decomposition of single-qubit unitaries'' Quantum Information and Computation 14, 1277–1301 (2014).

[55] Ori Parzanchevskiand Peter Sarnak ``Super-Golden-Gates for PU(2)'' Advances in Mathematics 327, 869–901 (2018) Special volume honoring David Kazhdan.

[56] Neil J. Ross ``Optimal Ancilla-Free Clifford+V Approximation of Z-Rotations'' Quantum Info. Comput. 15, 932–950 (2015).

[57] Neil J. Rossand Peter Selinger ``Optimal ancilla-free Clifford+T approximation of z-rotations'' Quantum Information & Computation 15, 932–950 (2015).

[58] Peter Sarnak ``Letter to Aaronson and Pollington on the Solvay-Kitaev Theorem and Golden Gates, 2015''.

[59] Naser T Sardari ``Complexity of Strong Approximation on the Sphere'' International Mathematics Research Notices 2021, 13839–13866 (2021).

[60] Peter Selinger ``Efficient Clifford+T approximation of single-qubit operators'' Quantum Information & Computation 15, 159–180 (2015).

[61] Zachary Stier private communication (2020).

[62] Jean-Pierre Tillichand Gilles Zémor ``Collisions for the LPS expander graph hash function'' Annual International Conference on the Theory and Applications of Cryptographic Techniques 254–269 (2008).

[63] John Voight ``Quaternion Algebras'' Springer International Publishing (2021).

[64] Lawrence C. Washington ``Introduction to Cyclotomic Fields'' Springer New York (1997).

[65] John Watrous ``The Theory of Quantum Information'' Cambridge University Press (2018).

[66] Paul Websterand Stephen D. Bartlett ``Fault-tolerant quantum gates with defects in topological stabilizer codes'' Phys. Rev. A 102, 022403 (2020).

Cited by

[1] Seiseki Akibue, Go Kato, and Seiichiro Tani, "Probabilistic state synthesis based on optimal convex approximation", npj Quantum Information 10 1, 3 (2024).

[2] Daniel Litinski and Naomi Nickerson, "Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections", arXiv:2211.15465, (2022).

[3] Pascal Baßler, Matthias Zipper, Christopher Cedzich, Markus Heinrich, Patrick H. Huber, Michael Johanning, and Martin Kliesch, "Synthesis of and compilation with time-optimal multi-qubit gates", Quantum 7, 984 (2023).

[4] Seiseki Akibue, Go Kato, and Seiichiro Tani, "Probabilistic unitary synthesis with optimal accuracy", arXiv:2301.06307, (2023).

[5] Thomas Lubinski, Cassandra Granade, Amos Anderson, Alan Geller, Martin Roetteler, Andrei Petrenko, and Bettina Heim, "Advancing hybrid quantum-classical computation with real-time execution", Frontiers in Physics 10, 940293 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-02-27 14:26:55) and SAO/NASA ADS (last updated successfully 2024-02-27 14:26:56). The list may be incomplete as not all publishers provide suitable and complete citation data.