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:2403.13692

Beyond Quantum Shannon: Circuit Construction for General n-Qubit Gates Based on Block ZXZ-Decomposition

Anna M. Krol, Zaid Al-Ars

Published Mar 20, 2024• 1 citation
arXivHTMLPDF

Abstract

This paper proposes a new optimized quantum block-ZXZ decomposition method [7,8,10] that results in more optimal quantum circuits than the quantum Shannon decomposition (QSD)[27], which was introduced in 2006 by Shende et al. 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 one-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 3-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 - \frac{3}{2}2^n +\frac{5}{3}$ CNOT gates, which is less that the best known exact decomposition algorithm by $(4^{n-2} -1)/3$ CNOT gates.

DOI
10.48550/arxiv.2403.13692

Related papers

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.

Physical Review Applied•Sep 9, 2024•4 citations

Optimal synthesis of general multi-qutrit quantum computation

Gui‐Long Jiang, Wen‐Qiang Liu, Hai‐Rui Wei

Quantum circuits of a general quantum gate acting on multiple $d$-level quantum systems play a prominent role in multi-valued quantum computation. We first propose a new recursive Cartan decomposition of semi-simple unitary Lie group $U(3^n)$ (arbitrary $n$-qutrit gate). Note that the decomposition completely decomposes an n-qutrit gate into local and non-local operations. We design an explicit quantum circuit for implementing arbitrary two-qutrit gates, and the cost of our construction is 21 generalized controlled X (GCX) and controlled increment (CINC) gates less than the earlier best result of 26 GGXs. Moreover, we extend the program to the $n$-qutrit system, and the quantum circuit of generic $n$-qutrit gates contained $\frac{41}{96}\cdot3^{2n}-4\cdot3^{n-1}-(\frac{n^2}{2}+\frac{n}{4}-\frac{29}{32})$ GGXs and CINCs is presented. Such asymptotically optimal structure is the best known result so far.

arXiv:2310.11996•Oct 18, 2023•0 citations

Decomposition of Multi-controlled Special Unitary Single-Qubit Gates

Rafaella F. Vale, Thiago Melo D. Azevedo, Ismael C. S. Araújo +2 more

Multi-controlled unitary gates have been a subject of interest in quantum computing since its inception, and are widely used in quantum algorithms. The current state-of-the-art approach to implementing n-qubit multi-controlled gates involves the use of a quadratic number of single-qubit and CNOT gates. However, linear solutions are possible for the case where the controlled gate is a special unitary SU(2). The most widely-used decomposition of an n-qubit multi-controlled SU(2) gate requires a circuit with a number of CNOT gates proportional to 28n. In this work, we present a new decomposition of n-qubit multi-controlled SU(2) gates that requires a circuit with a number of CNOT gates proportional to 20n, and proportional to 16n if the SU(2) gate has at least one real-valued diagonal. This new approach significantly improves the existing algorithm by reducing the number of CNOT gates and the overall circuit depth. As an application, we show the use of this decomposition for sparse quantum state preparation. Our results are further validated by demonstrating a proof of principle on a quantum device accessed through quantum cloud services.

arXiv:2302.06377•Feb 13, 2023•4 citations

Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers

Anna M. Krol, Aritra Sarkar, Imran Ashraf +2 more

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.

arXiv:2101.02993•Applied Sciences•Jan 12, 2022•54 citations

Decomposition of Multi-Qubit Gates for Circuit Cutting

Ryota Tamura, Tomoya Kashimata, Yohei Hamakawa +2 more

A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.

quant-pharXiv:2603.26278•Mar 30, 2026•0 citations

Quantum-gate decomposer

Ken M. Nakanishi, Takahiko Satoh, Synge Todo

Efficient decompositions of multi-qubit gates are essential in NISQ applications, where the number of gates or the circuit depth is limited. This paper presents efficient decompositions of CCZ and CCCZ gates, typical multi-qubit gates, under several qubit connectivities. We can construct the CCZ gate with only four CZ-depth when the qubit is square-shaped, including one auxiliary qubit. In T-shaped qubit connectivity, which has no closed loop, we can decompose the CCCZ gate with 17 CZ gates. While previous studies have shown a CCCZ gate decomposition with 14 CZ gates for the fully connected case, we found only four connections are sufficient for 14 CZ gates' implementation. The search for constraint-sufficient decompositions is aided by an optimization method we devised to bring the parameterized quantum circuit closer to the target quantum gate. We can apply this scheme to decompose any quantum gates, not only CCZ and CCCZ. Such decompositions of multi-qubit gates, together with the newly found CCZ and CCCZ decompositions, shorten the execution time of quantum circuits and improve the accuracy of complex quantum algorithms on near future QPUs.

arXiv:2109.13223•Sep 27, 2021•3 citations
This paper proposes a new optimized quantum block-ZXZ decomposition method [7,8,10] that results in more optimal quantum circuits than the quantum Shannon decomposition (QSD)[27], which was introduced in 2006 by Shende et al. 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 one-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 3-qubit gate can be decomposed using 19 CNOT gates (rather than 20). For general nnn-qubit gates, the proposed decomposition generates circuits that have 22484n−322n+53\frac{22}{48}4^n - \frac{3}{2}2^n +\frac{5}{3}4822​4n−23​2n+35​ CNOT gates, which is less that the best known exact decomposition algorithm by (4n−2−1)/3(4^{n-2} -1)/3(4n−2−1)/3 CNOT gates.
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.
Quantum circuits of a general quantum gate acting on multiple ddd-level quantum systems play a prominent role in multi-valued quantum computation. We first propose a new recursive Cartan decomposition of semi-simple unitary Lie group U(3n)U(3^n)U(3n) (arbitrary nnn-qutrit gate). Note that the decomposition completely decomposes an n-qutrit gate into local and non-local operations. We design an explicit quantum circuit for implementing arbitrary two-qutrit gates, and the cost of our construction is 21 generalized controlled X (GCX) and controlled increment (CINC) gates less than the earlier best result of 26 GGXs. Moreover, we extend the program to the nnn-qutrit system, and the quantum circuit of generic nnn-qutrit gates contained 4196⋅32n−4⋅3n−1−(n22+n4−2932)\frac{41}{96}\cdot3^{2n}-4\cdot3^{n-1}-(\frac{n^2}{2}+\frac{n}{4}-\frac{29}{32})9641​⋅32n−4⋅3n−1−(2n2​+4n​−3229​) GGXs and CINCs is presented. Such asymptotically optimal structure is the best known result so far.
Multi-controlled unitary gates have been a subject of interest in quantum computing since its inception, and are widely used in quantum algorithms. The current state-of-the-art approach to implementing n-qubit multi-controlled gates involves the use of a quadratic number of single-qubit and CNOT gates. However, linear solutions are possible for the case where the controlled gate is a special unitary SU(2). The most widely-used decomposition of an n-qubit multi-controlled SU(2) gate requires a circuit with a number of CNOT gates proportional to 28n. In this work, we present a new decomposition of n-qubit multi-controlled SU(2) gates that requires a circuit with a number of CNOT gates proportional to 20n, and proportional to 16n if the SU(2) gate has at least one real-valued diagonal. This new approach significantly improves the existing algorithm by reducing the number of CNOT gates and the overall circuit depth. As an application, we show the use of this decomposition for sparse quantum state preparation. Our results are further validated by demonstrating a proof of principle on a quantum device accessed through quantum cloud services.
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.
A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.
Efficient decompositions of multi-qubit gates are essential in NISQ applications, where the number of gates or the circuit depth is limited. This paper presents efficient decompositions of CCZ and CCCZ gates, typical multi-qubit gates, under several qubit connectivities. We can construct the CCZ gate with only four CZ-depth when the qubit is square-shaped, including one auxiliary qubit. In T-shaped qubit connectivity, which has no closed loop, we can decompose the CCCZ gate with 17 CZ gates. While previous studies have shown a CCCZ gate decomposition with 14 CZ gates for the fully connected case, we found only four connections are sufficient for 14 CZ gates' implementation. The search for constraint-sufficient decompositions is aided by an optimization method we devised to bring the parameterized quantum circuit closer to the target quantum gate. We can apply this scheme to decompose any quantum gates, not only CCZ and CCCZ. Such decompositions of multi-qubit gates, together with the newly found CCZ and CCCZ decompositions, shorten the execution time of quantum circuits and improve the accuracy of complex quantum algorithms on near future QPUs.