Quantum Circuit Overhead

Oskar Słowik, Piotr Dulian, Adam Sawicki · 2025

Read Quantum Circuit Overhead by Oskar Słowik, Piotr Dulian, Adam Sawicki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00683.txt.

Introduction

Oskar Słowik, Piotr Dulian, and Adam Sawicki proposed a way to grade how efficient a quantum gate set is, in a paper published in 2025. Any set that can build all quantum operations still pays a price, because some sets need longer chains of gates for the same operation. Their grade compares a set's chain length with the best length any set of the same size could reach. A companion grade counts only the expensive gates.

Extensive calculations set upper bounds for the grades across many kinds of sets. Sets chosen at random and sets drawn from famous groups all received marks. One famous result stood out. The T gate, the standard partner for a core gate set, scored poorly for its slot, even among gates of its own order. The team names the best partners for both group types. The work gives gate design a shared yardstick.

Catalog record

CREATOROskar Słowik, Piotr Dulian, Adam Sawicki
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00683

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Circuit Overhead Oskar Słowik, Piotr Dulian, Adam Sawicki Abstract We introduce a measure for evaluating the efficiency of finite universal quantum gate sets 𝒮 \mathcal{S} , called the Quantum Circuit Overhead (QCO), and the related notion of T T -Quantum Circuit Overhead ( T T -QCO). The overhead is based on the comparison between the efficiency of 𝒮 \mathcal{S} versus the optimal efficiency among all gate sets with the same number of gates. We demonstrate the usefulness of the ( T T -)QCO by extensive numerical calculations of its upper bounds, providing insight into the efficiency of various choices of single-qubit 𝒮 \mathcal{S} , including Haar-random gate sets and the gate sets derived from finite subgroups, such as Clifford and Hurwitz groups. In particular, our results suggest that, in terms of the upper bounds on the T T -QCO, the famous T gate is a highly non-optimal choice for the completion of the Clifford gate set, even among the gates of order 8. We identify the optimal choices of such completions for both finite subgroups. I Introduction Quantum circuit Nielsen and Chuang 2010 ; Kitaev et al. 2002 is a universal model for quantum computation in which quantum information is processed via the application of a series of unitary operations called quantum logic gates. Similarly to a classical computer, whose computation can be described using the classical circuit model, every global quantum operation on a qubit register can be realized using a universal finite set of elementary operations. A set of such quantum logic gates is referred to as the universal gate set or, in the context of quantum hardware, the native gate set. Contrary to the classical case, the finite length quantum circuits built out of a finite discrete set \mathcal{S} of quantum gates can be used to implement arbitrary multi-qubit (global) unitary operations only approximately, up to some error \epsilon (in a suitable metric). The number of elementary gates needed to implement a target unitary operation U with precision \epsilon using gates from \mathcal{S} is a measure of the complexity of U with respect to \mathcal{S} Nielsen and Chuang 2010 ; Kitaev et al. 2002 ; Aaronson 2016 . For a universal gate set \mathcal{S} and any finite \epsilon , the complexity of any U is finite and thus can be upper bounded by the shortest circuit length, \ell(\mathcal{S},\epsilon) , so that any U can be \epsilon -approximated by a quantum circuit built out of \mathcal{S} of length at most \ell(\mathcal{S},\epsilon) . This number can be understood as an absolute measure of the efficiency of \mathcal{S} at the scale of \epsilon -approximations. Since the implementation of quantum gates is always flawed, for reasonably small nonzero \epsilon , this number fully characterizes the efficiency of \mathcal{S} . Quantum compilation Ge et al. 2024 ; Häner et al. 2018 ; Nielsen and Chuang 2010 is a process whose main objective is to approximate the target quantum circuit from the high-level hardware-agnostic representation used by quantum programmers to the form expressible by the native gate set executable on a specific quantum computer. Another task handled by the compiler is circuit optimization, which, loosely speaking, involves reducing the resources of quantum circuits, such as the depth of the circuit or the number of specific gates used. In the case of the current noisy intermediate-scale quantum (NISQ) machines, which do not enjoy quantum error correction, the reduction of the circuit depth and the number of costly gates (such as the noisy entangling gates) is of utmost practical importance Gheorghiu et al. 2023 ; Preskill 2018 ; Noh et al. 2020 . On the other hand, in the fault-tolerant regime, due to the Eastin-Knill theorem Eastin and Knill 2009a ; Woods and Alhambra 2020 ; Faist et al. 2020 , the bottleneck is typically determined by the number of resource-costly non-traversal gates used Gottesman 2005 ; Luo et al. 2021 ; Eastin and Knill 2009b . For example, in the case of Clifford+T gate sets, the focus is usually on the reduction of the T-count i.e. the number of non-transversal T gates (also known as the P(\pi/4) or \pi/8 gates 1 1 1 To avoid confusion with the T symbol occurring in T -QCO, we refer to the T gate as P(\pi/4) gate. ), leading to an improvement in error rates, runtime and the number of qubits needed to perform the computations Beverland et al. 2021 ; Gheorghiu et al. 2022 ; Ruiz et al. 2025 ; Gosset et al. 2014 ; Vandaele 2024 ; Zhou et al. 2024 ; Heyfron and Campbell 2018 . However, the compilation process is fundamentally limited by the efficiency of the used gate set \mathcal{S} . Aside from the applications in the description of information processing occurring in quantum computers, quantum circuits can be used to describe the discrete unitary dynamics of general discrete quantum systems Tokusumi et al. 2018 ; Fisher et al. 2023 ; Claeys et al. 2022 . Such an approach has been recently proposed to gain insight into the physics of black hole interiors, and interesting results regarding the saturation and recurrence of the complexity of such systems have been obtained Hayden and Preskill 2007 ; Oszmaniec et al. 2024 . Such behaviour also depends on the efficiency of gate sets \mathcal{S} used to model the system. Although it is conjectured that the generic universal gate sets \mathcal{S} have, so called spectral gap, which implies the optimal asymptotic efficiency \ell(\mathcal{S},\epsilon)=\Theta\left(\mathrm{log}(1/\epsilon)\right) , the quantitative methods to bound and compare the efficiency of various gate sets \mathcal{S} are not well-developed. In this work, we introduce and study the relative measure of the efficiency of finite discrete universal gate sets \mathcal{S} that we call the quantum circuit overhead (QCO) and the related notion of T -Quantum Circuit Overhead ( T -QCO). The notion of overhead is based on the comparison of the efficiency \ell(\mathcal{S},\epsilon) among the gate sets \mathcal{S} having the same number of elements, where the optimal efficiency is denoted \ell_{\mathrm{opt}}(|\mathcal{S}|,\epsilon) . Crucially, both overheads can be upper-bounded by essentially calculable quantities, namely Q and Q_{T} , respectively, which can be obtained from numerical simulations. To demonstrate the feasibility of our method and its applications, we perform extensive numerical experiments in which we calculate Q/Q_{T} , focusing on the comparison between the two scenarios for single-qubit gate sets: 1. A Haar-random set \mathcal{S} with a fixed number of elements (of infinite or fixed finite order), 2. A set \mathcal{S} composed of a finite group (such as Clifford or Hurwitz group) completed with a single Haar-random gate (of infinite or fixed finite order), making the set universal. In the second scenario, we compare such random ensembles with some “special” choices, e.g. the P(\pi/4) gate in the case of the Clifford group, gaining insight into their efficiency. The inclusion of the finite order cases is motivated by the fault-tolerance considerations and the analysis of the so-called Super-Golden Gates Sarnak 2015 . Surprisingly, our results suggest that the P(\pi/4) gate is a highly non-optimal choice among all gates of order 8 in terms of Q_{T} . We also identified the best possible gates of orders 8 and 2 in the Clifford and Hurwitz group cases, respectively. In order

Read the complete text