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:2101.02993 · Applied Sciences

Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers

Anna M. Krol, Aritra Sarkar, Imran Ashraf, Zaid Al-Ars, Koen Bertels

Published Jan 12, 2022• 69 citations
arXivHTMLPDF

Abstract

Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.

DOI
10.3390/app12020759

Related papers

Compiling Quantum Circuits using the Palindrome Transform

Alfred V. Aho, Krysta M. Svore

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2^n x 2^n unitary matrices into efficient circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of self-inverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an numerative algorithm for minimal (n-1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates.

arXiv:quant-ph/0311008•Nov 3, 2003•29 citations

Efficient decomposition of single-qubit gates into V basis circuits

Alex Bocharov, Yuri G. Gurevich, Krysta M. Svore

We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal $V$ basis. The $V$ basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and $\ensuremath{\pi}/8$ gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time [in precision $\mathrm{log}(1/\ensuremath{\epsilon})$] and produces an $\ensuremath{\epsilon}$ approximation to a single-qubit unitary with a circuit depth $\ensuremath{\le}12\phantom{\rule{0.16em}{0ex}}{\mathrm{log}}_{5}(2/\ensuremath{\epsilon})$. The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in $\mathrm{log}(1/\ensuremath{\epsilon})$; however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the $V$ basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.

arXiv:1303.1411•Physical Review A•Jul 12, 2013•77 citations

Beyond quantum Shannon decomposition: Circuit construction for n -qubit gates based on block- Z X Z decomposition

Anna M. Krol, Zaid Al-Ars

This paper proposes an optimized quantum block-$ZXZ$ decomposition method that results in more optimal quantum circuits than the quantum Shannon decomposition, which was presented in 2005 by M. M\"ott\"onen, and J. J. Vartiainen [in Trends in quantum computing research, edited by S. Shannon (Nova Science Publishers, 2006) Chap. 7, p. 149, arXiv:quant-ph/0504100]. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only single-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general three-qubit gate can be decomposed using 19 cnot gates (rather than 20). For general $n$-qubit gates, the proposed decomposition generates circuits that have $\frac{22}{48}{4}^{n}\ensuremath{-}\frac{3}{2}{2}^{n}+\frac{5}{3}$ cnot gates, which is less than the best-known exact decomposition algorithm by $({4}^{n\ensuremath{-}2}\ensuremath{-}1)/3$ cnot gates.

arXiv:2403.13692•Physical Review Applied•Sep 9, 2024•25 citations

The Design and Optimization of Quantum Circuits using the Palindrome Transform

Krysta M. Svore, Alfred V. Aho

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n unitary matrices into efficient circuits of (n−1)-controlled single-qubit and (n−1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative algorithm for minimal (n−1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n − 1)-controlled single-qubit and (n − 1)-controlled-NOT gates.

•Sep 1, 2003•6 citations

Exact Unitary Synthesis: Simultaneously Optimal in Size and Depth-Ancilla Tradeoff

Pei Yuan, Wei Zi, Shengyu Zhang

Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget $m\geq 0$ of ancilla, every $n$-qubit unitary can be exactly implemented using a quantum circuit consisting of $O(4^n)$ CNOT and single-qubit gates in $O(n+4^n/(n+m))$ layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.

quant-pharXiv:2610.07010•Oct 6, 2026•1 citation

Efficient compilation of quantum circuits using multi-qubit gates

Jonathan Nemirovsky, Maya Chuchem, Yotam Shapira

Abstract As quantum processors grow in scale and reliability, the need for efficient quantum gate decomposition of circuits to a set of specific available gates, becomes ever more critical. The decomposition of a particular algorithm into a sequence of these available gates is not unique. Thus, the fidelity of an algorithm’s implementation can be increased by choosing an optimized decomposition. This is true both for noisy intermediate-scale quantum platforms as well as for implementation of quantum error correction schemes. Here we present a compilation scheme which implements a general-circuit decomposition to a sequence of Ising-type, long-range, multi-qubit (MQ) entangling gates, that are separated by layers of single qubit rotations. We use trapped ions as an example in which MQ gates naturally arise, yet any system that has connectivity beyond nearest-neighbors may gain from our approach. We evaluate our methods using the quantum volume (QV) test over N qubits. In this context, our method replaces 3 N 2 / 2 two-qubit gates with 2 N + 1 MQ gates. Furthermore, our method minimizes the magnitude of the entanglement phases, which typically enables an improved implementation fidelity, by using weaker driving fields or faster realizations. We numerically test our compilation and show that, compared to conventional realizations with sequential two-qubit gates, our compilations improves the logarithm of QV by 20% to 25%.

arXiv:2501.17246•Quantum Science and Technology•Jan 12, 2026•15 citations
Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2^n x 2^n unitary matrices into efficient circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of self-inverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an numerative algorithm for minimal (n-1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates.
We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal VVV basis. The VVV basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and $\ensuremath{\pi}/8$ gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time [in precision $\mathrm{log}(1/\ensuremath{\epsilon})$] and produces an $\ensuremath{\epsilon}$ approximation to a single-qubit unitary with a circuit depth $\ensuremath{\le}12\phantom{\rule{0.16em}{0ex}}{\mathrm{log}}_{5}(2/\ensuremath{\epsilon})$. The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in $\mathrm{log}(1/\ensuremath{\epsilon})$; however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the VVV basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.
This paper proposes an optimized quantum block-ZXZZXZZXZ decomposition method that results in more optimal quantum circuits than the quantum Shannon decomposition, which was presented in 2005 by M. M\"ott\"onen, and J. J. Vartiainen [in Trends in quantum computing research, edited by S. Shannon (Nova Science Publishers, 2006) Chap. 7, p. 149, arXiv:quant-ph/0504100]. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only single-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general three-qubit gate can be decomposed using 19 cnot gates (rather than 20). For general nnn-qubit gates, the proposed decomposition generates circuits that have $\frac{22}{48}{4}^{n}\ensuremath{-}\frac{3}{2}{2}^{n}+\frac{5}{3}$ cnot gates, which is less than the best-known exact decomposition algorithm by $({4}^{n\ensuremath{-}2}\ensuremath{-}1)/3$ cnot gates.
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n unitary matrices into efficient circuits of (n−1)-controlled single-qubit and (n−1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative algorithm for minimal (n−1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n − 1)-controlled single-qubit and (n − 1)-controlled-NOT gates.
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget m≥0m\geq 0m≥0 of ancilla, every nnn-qubit unitary can be exactly implemented using a quantum circuit consisting of O(4n)O(4^n)O(4n) CNOT and single-qubit gates in O(n+4n/(n+m))O(n+4^n/(n+m))O(n+4n/(n+m)) layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.
Abstract As quantum processors grow in scale and reliability, the need for efficient quantum gate decomposition of circuits to a set of specific available gates, becomes ever more critical. The decomposition of a particular algorithm into a sequence of these available gates is not unique. Thus, the fidelity of an algorithm’s implementation can be increased by choosing an optimized decomposition. This is true both for noisy intermediate-scale quantum platforms as well as for implementation of quantum error correction schemes. Here we present a compilation scheme which implements a general-circuit decomposition to a sequence of Ising-type, long-range, multi-qubit (MQ) entangling gates, that are separated by layers of single qubit rotations. We use trapped ions as an example in which MQ gates naturally arise, yet any system that has connectivity beyond nearest-neighbors may gain from our approach. We evaluate our methods using the quantum volume (QV) test over N qubits. In this context, our method replaces 3 N 2 / 2 two-qubit gates with 2 N + 1 MQ gates. Furthermore, our method minimizes the magnitude of the entanglement phases, which typically enables an improved implementation fidelity, by using weaker driving fields or faster realizations. We numerically test our compilation and show that, compared to conventional realizations with sequential two-qubit gates, our compilations improves the logarithm of QV by 20% to 25%.