Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39092

Quantum circuit compilation with constant overhead

Chenyi Zhang, Xinyu Tan, Robin Kothari, David Gosset, Craig Gidney

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 1 citation
arXivHTMLPDF

Abstract

Compiling a continuous gate set to a discrete universal gate set generally incurs an overhead. A circuit composed of $G$ arbitrary one- and two-qubit gates can be $ε$-approximated by a sequence of gates from $\{H,T,\mathrm{CNOT}\}$ by replacing each original gate by a sequence of $O(\log(G/ε))$ elementary gates. We show that this overhead can be avoided using adaptivity for polynomial-sized circuits with inverse-polynomial target error, which is optimal.

AI Summary

Standard gate-by-gate compilation of a circuit with $G$ arbitrary one- and two-qubit gates into $\{H,T,\mathrm{CNOT}\}$ costs $O(G\log(G/\epsilon))$ gates. This paper asks whether compiling the circuit collectively can remove that multiplicative overhead. The main result is an adaptive implementation using $O(G)$ elementary gates in the worst case, with diamond-distance error $G^{-c}$ for any fixed $c$; the hidden constant depends on $c$. For circuits over the discrete set augmented by dyadic rotations $R(\pi/2^j)$, the bound improves to $O(G+\log(1/\epsilon))$ for arbitrary target error. A supporting result prepares an $n$-qubit phase-gradient state unitarily with error $2^{-n}$ using $O(n)$ gates. With Clifford gates free, a circuit containing $G$ arbitrary $Z$-rotations can achieve error $1/\sqrt G$ with at most $8G+o(G)$ $T$ gates. The compilation strategy combines state injection with catalytic phase-halving gadgets and an adaptive bank of rotation-resource states. Tail bounds allow a fixed runtime cutoff while controlling failure error. General rotations are discretized and decomposed using a large-base expansion; the simpler $1/\sqrt G$-error construction uses randomized rounding. Linear-cost phase-gradient preparation uses LCU, amplitude amplification, tailored encodings, and classical multiselection circuits. A counting argument rules out linear-cost compilation at superpolynomially small error for arbitrary gates. Full adaptivity remains necessary for the presented protocols; whether it can be avoided is open. The optimal phase-gradient construction requires complex coherent reversible circuits and is not presented as near-term practical.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm

Adam Bouland, Tudor Giurgică-Tiron

The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both $\text{SU}(d)$ and $\text{SL}(d, \mathbb{C})$. The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.

arXiv:2112.02040•Dec 3, 2021•33 citations

Quantum Compiler Optimizations

Booth, Jeffrey

A quantum computer consists of a set of quantum bits upon which operations called gates are applied to perform computations. In order to perform quantum algorithms, physicists would like to design arbitrary gates to apply to quantum bits. However, the physical limitations of the quantum computing device restrict the set of gates that physicists are able to apply. Thus, they must compose a sequence of gates from the permitted gate set, which approximates the gate they wish to apply - a process called quantum compiling. Austin Fowler proposes a method that finds optimal gate sequences in exponential time, but which is tractable for common problems. In this paper, I present several optimizations to this algorithm. While my optimizations do not improve its overall exponential behavior, they improve its empirical performance by one to two orders of magnitude.

arXiv:1206.3348•Jun 14, 2012•19 citations

Qutrit-Based Orthogonal Approximations with Inverse-Free Quantum Gate Sets

Anuradha Mahasinghe, Dulmi Fernando, Kaushika De Silva

The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.

International Online Conference on Mathematics and Applications (IOCMA)•Jun 13, 2023•0 citations

Constructing quantum circuits with global gates

John van de Wetering

Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.

arXiv:2012.09061•New Journal of Physics•Mar 24, 2021•44 citations

Universal quantum computing with a single arbitrary gate

Zhongyi Ni, Yusheng Zhao, Jin-Guo Liu

This study presents a roadmap towards utilizing a single arbitrary gate for universal quantum computing. Since two decades ago, it has been widely accepted that almost any single arbitrary gate with qubit number $>2$ is universal. Utilizing a single arbitrary gate for compiling is beneficial for systems with limited degrees of freedom, e.g. the scattering based quantum computing schemes. However, how to efficiently compile the wanted gate with a single arbitrary gate, and finally achieve fault-tolerant quantum computing is unknown. In this work, we show almost any target gate can be compiled to precision $ε$ with a circuit depth of approximately $\log(ε^{-1})$ with an improved brute-force compiling method. Under the assumption of reasonable classical resource, we show the gate imperfection can be lowered to $10^{-3}$. By treating the imperfection as coherent error, we show that the error can be further reduced by roughly two orders of magnitude with a measurement-free quantum error correction method.

arXiv:2409.20025•Sep 30, 2024•0 citations

QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis

Xin-Chuan Wu, Davis, Marc Grau, Frederic T. Chong +1 more

The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.

arXiv:2012.09835•Dec 17, 2020•52 citations
Compiling a continuous gate set to a discrete universal gate set generally incurs an overhead. A circuit composed of GGG arbitrary one- and two-qubit gates can be εεε-approximated by a sequence of gates from {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT} by replacing each original gate by a sequence of O(log⁡(G/ε))O(\log(G/ε))O(log(G/ε)) elementary gates. We show that this overhead can be avoided using adaptivity for polynomial-sized circuits with inverse-polynomial target error, which is optimal.
Standard gate-by-gate compilation of a circuit with GGG arbitrary one- and two-qubit gates into {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT} costs O(Glog⁡(G/ϵ))O(G\log(G/\epsilon))O(Glog(G/ϵ)) gates. This paper asks whether compiling the circuit collectively can remove that multiplicative overhead.
The main result is an adaptive implementation using O(G)O(G)O(G) elementary gates in the worst case, with diamond-distance error G−cG^{-c}G−c for any fixed ccc; the hidden constant depends on ccc. For circuits over the discrete set augmented by dyadic rotations R(π/2j)R(\pi/2^j)R(π/2j), the bound improves to O(G+log⁡(1/ϵ))O(G+\log(1/\epsilon))O(G+log(1/ϵ)) for arbitrary target error. A supporting result prepares an nnn-qubit phase-gradient state unitarily with error 2−n2^{-n}2−n using O(n)O(n)O(n) gates. With Clifford gates free, a circuit containing GGG arbitrary ZZZ-rotations can achieve error 1/G1/\sqrt G1/G​ with at most 8G+o(G)8G+o(G)8G+o(G) TTT gates.
The compilation strategy combines state injection with catalytic phase-halving gadgets and an adaptive bank of rotation-resource states. Tail bounds allow a fixed runtime cutoff while controlling failure error. General rotations are discretized and decomposed using a large-base expansion; the simpler 1/G1/\sqrt G1/G​-error construction uses randomized rounding. Linear-cost phase-gradient preparation uses LCU, amplitude amplification, tailored encodings, and classical multiselection circuits.
A counting argument rules out linear-cost compilation at superpolynomially small error for arbitrary gates. Full adaptivity remains necessary for the presented protocols; whether it can be avoided is open. The optimal phase-gradient construction requires complex coherent reversible circuits and is not presented as near-term practical.
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both SU(d)\text{SU}(d)SU(d) and SL(d,C)\text{SL}(d, \mathbb{C})SL(d,C). The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.
A quantum computer consists of a set of quantum bits upon which operations called gates are applied to perform computations. In order to perform quantum algorithms, physicists would like to design arbitrary gates to apply to quantum bits. However, the physical limitations of the quantum computing device restrict the set of gates that physicists are able to apply. Thus, they must compose a sequence of gates from the permitted gate set, which approximates the gate they wish to apply - a process called quantum compiling. Austin Fowler proposes a method that finds optimal gate sequences in exponential time, but which is tractable for common problems. In this paper, I present several optimizations to this algorithm. While my optimizations do not improve its overall exponential behavior, they improve its empirical performance by one to two orders of magnitude.
The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.
Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.
This study presents a roadmap towards utilizing a single arbitrary gate for universal quantum computing. Since two decades ago, it has been widely accepted that almost any single arbitrary gate with qubit number >2>2>2 is universal. Utilizing a single arbitrary gate for compiling is beneficial for systems with limited degrees of freedom, e.g. the scattering based quantum computing schemes. However, how to efficiently compile the wanted gate with a single arbitrary gate, and finally achieve fault-tolerant quantum computing is unknown. In this work, we show almost any target gate can be compiled to precision εεε with a circuit depth of approximately log⁡(ε−1)\log(ε^{-1})log(ε−1) with an improved brute-force compiling method. Under the assumption of reasonable classical resource, we show the gate imperfection can be lowered to 10−310^{-3}10−3. By treating the imperfection as coherent error, we show that the error can be further reduced by roughly two orders of magnitude with a measurement-free quantum error correction method.
The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.