Paper 2022/372

Shorter quantum circuits

Vadym Kliuchnikov, Kristin Lauter, Romy Minko, Christophe Petit, and Adam Paetznick


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 arXiv:1612.01011 and arXiv:1612.02689, we show that taking probabilistic mixtures of channels to solve fallback (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$\sqrt{T}$ gate set we achieve an average non-Clifford gate count of 0.23log2(1/$\varepsilon$)+2.13 and T-count 0.56log2(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{T}$). We also provide detailed numerical results for Clifford+T and Clifford+$\sqrt{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.

Available format(s)
Publication info
Preprint. MINOR revision.
quantum informationapplicationspath finding
Contact author(s)
romy minko @ bristol ac uk
2022-03-24: revised
2022-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vadym Kliuchnikov and Kristin Lauter and Romy Minko and Christophe Petit and Adam Paetznick},
      title = {Shorter quantum circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2022/372},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.