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:0806.4015 · Journal of Physics A Mathematical and Theoretical

Constructive quantum Shannon decomposition from Cartan involutions

Byron C. Drury, Peter J. Love

Published Sep 4, 2008• 43 citations
arXivHTMLPDF

Abstract

The work presented here extends upon the best known universal quantum circuit, the Quantum Shannon Decomposition proposed in [Vivek V. Shende, Stephen S. Bullock and Igor Markov, Synthesis of Quantum Logic Circuits, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25 (6): 1000-1010 (2006)]. We obtain the basis of the circuit's design in a pair of Cartan decompositions. This insight gives a simple constructive algorithm for obtaining the Quantum Shannon Decomposition of a given unitary matrix in terms of the corresponding Cartan involutions.

DOI
10.1088/1751-8113/41/39/395305

Related papers

A new algorithm for producing quantum circuits using KAK decompositions

M.Y. Nakajima, Y. Kawano, Hiroshi Sekigawa

We provide a new algorithm that translates a unitary matrix into a quantum circuit according to the G=KAK theorem in Lie group theory. With our algorithm, any matrix decomposition corresponding to type-AIII KAK decompositions can be derived according to the given Cartan involution. Our algorithm contains, as its special cases, Cosine-Sine decomposition (CSD) and Khaneja-Glaser decomposition (KGD) in the sense that it derives the same quantum circuits as the ones obtained by them if we select suitable Cartan involutions and square root matrices. The selections of Cartan involutions for computing CSD and KGD will be shown explicitly. As an example, we show explicitly that our method can automatically reproduce the well-known efficient quantum circuit for the $n$-qubit quantum Fourier transform.

arXiv:quant-ph/0509196•Quantum Information and Computation•Jan 1, 2006•59 citations

Synthesis of quantum logic circuits

Vivek Shende, Stephen S. Bullock, Igor L. Markov

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits to the attention of the EDA community (Iwama et al., 2002; Shende et al., 2003; Bullock and Markov, 2003; Shende et al., 2004; Hung et al., 2004). We discuss efficient circuits to initialize quantum registers and implement generic quantum computations. Our techniques yield circuits that are twice as small as the best previously published technique. Moreover, a theoretical lower bound shows that our new circuits can be improved by at most a factor of two. Further, the circuits grow by at most a factor of nine under severe architectural restrictions.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jul 19, 2005•53 citations

Synthesis of quantum-logic circuits

Vivek Shende, Stephen S. Bullock, Igor L. Markov

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.

arXiv:quant-ph/0406176•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 12, 2006•794 citations

Cartan-Khaneja-Glaser decomposition of $SU(2^n)$ via involutive automorphisms

John A. Mora Rodríguez, Arthur C. R. Dutra, Henrique N. Sá Earp +1 more

We present a novel algorithm for performing the Cartan-Khaneja-Glaser decomposition of unitary matrices in $\mathrm{SU}\left(2^n\right)$, a critical task for efficient quantum circuit design. Building upon the approach introduced by Sá Earp and Pachos (2005), we overcome key limitations of their method, such as reliance on ill-defined matrix logarithms and the convergence issues of truncated Baker-Campbell-Hausdorff (BCH) series. Our reformulation leverages the algebraic structure of involutive automorphisms and symmetric Lie algebra decompositions to yield a stable and recursive factorization process. We provide a full Python implementation of the algorithm, available in an open-source repository, and validate its performance on matrices in $\mathrm{SU}(8)$ and $\mathrm{SU}(16)$ using random unitary benchmarks. The algorithm produces decompositions that are directly suited to practical quantum hardware, with factors that can be implemented near-optimally using standard gate sets.

arXiv:2509.05468•Pure and Applied Mathematics Quarterly•Jan 1, 2026•1 citation

Near-optimal quantum circuit construction via Cartan decomposition

Maximilian Balthasar Mansky, Santiago Londoño Castillo, Victor Ramos Puigvert +1 more

We show the applicability of the Cartan decomposition of Lie algebras to quantum circuits. This approach can be used to synthesize circuits that can efficiently implement any desired unitary operation. Our method finds explicit quantum circuit representations of the algebraic generators of the relevant Lie algebras allowing the direct implementation of a Cartan decomposition on a quantum computer. The construction is recursive and allows us to expand any circuit down to generators and rotation matrices on individual qubits, where through our recursive algorithm we find that the generators themselves can be expressed with controlled-not (cnot) and swap gates explicitly. Our approach is independent of the standard cnot implementation and can be easily adapted to other cross-qubit circuit elements. In addition to its versatility, we also achieve near-optimal counts when working with cnot gates, achieving an asymptotic cnot cost of $\frac{21}{16}{4}^{n}$ for $n$ qubits.

arXiv:2212.12934•Physical Review A•Nov 15, 2023•13 citations

Efficient circuits for exact-universal computation with qudits

Gavin K. Brennen, Stephen S. Bullock, Dianne Prost O’Leary

This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, $\CINC$, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d^n) two-qudit gates for state synthesis and O(d^{2n}) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the (n-2)/(d-2) ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.

arXiv:quant-ph/0509161•Quantum Information and Computation•Jul 1, 2006•39 citations
The work presented here extends upon the best known universal quantum circuit, the Quantum Shannon Decomposition proposed in [Vivek V. Shende, Stephen S. Bullock and Igor Markov, Synthesis of Quantum Logic Circuits, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25 (6): 1000-1010 (2006)]. We obtain the basis of the circuit's design in a pair of Cartan decompositions. This insight gives a simple constructive algorithm for obtaining the Quantum Shannon Decomposition of a given unitary matrix in terms of the corresponding Cartan involutions.
We provide a new algorithm that translates a unitary matrix into a quantum circuit according to the G=KAK theorem in Lie group theory. With our algorithm, any matrix decomposition corresponding to type-AIII KAK decompositions can be derived according to the given Cartan involution. Our algorithm contains, as its special cases, Cosine-Sine decomposition (CSD) and Khaneja-Glaser decomposition (KGD) in the sense that it derives the same quantum circuits as the ones obtained by them if we select suitable Cartan involutions and square root matrices. The selections of Cartan involutions for computing CSD and KGD will be shown explicitly. As an example, we show explicitly that our method can automatically reproduce the well-known efficient quantum circuit for the nnn-qubit quantum Fourier transform.
The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits to the attention of the EDA community (Iwama et al., 2002; Shende et al., 2003; Bullock and Markov, 2003; Shende et al., 2004; Hung et al., 2004). We discuss efficient circuits to initialize quantum registers and implement generic quantum computations. Our techniques yield circuits that are twice as small as the best previously published technique. Moreover, a theoretical lower bound shows that our new circuits can be improved by at most a factor of two. Further, the circuits grow by at most a factor of nine under severe architectural restrictions.
The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.
Cartan-Khaneja-Glaser decomposition of SU(2n)SU(2^n)SU(2n) via involutive automorphisms
We present a novel algorithm for performing the Cartan-Khaneja-Glaser decomposition of unitary matrices in SU(2n)\mathrm{SU}\left(2^n\right)SU(2n), a critical task for efficient quantum circuit design. Building upon the approach introduced by Sá Earp and Pachos (2005), we overcome key limitations of their method, such as reliance on ill-defined matrix logarithms and the convergence issues of truncated Baker-Campbell-Hausdorff (BCH) series. Our reformulation leverages the algebraic structure of involutive automorphisms and symmetric Lie algebra decompositions to yield a stable and recursive factorization process. We provide a full Python implementation of the algorithm, available in an open-source repository, and validate its performance on matrices in SU(8)\mathrm{SU}(8)SU(8) and SU(16)\mathrm{SU}(16)SU(16) using random unitary benchmarks. The algorithm produces decompositions that are directly suited to practical quantum hardware, with factors that can be implemented near-optimally using standard gate sets.
We show the applicability of the Cartan decomposition of Lie algebras to quantum circuits. This approach can be used to synthesize circuits that can efficiently implement any desired unitary operation. Our method finds explicit quantum circuit representations of the algebraic generators of the relevant Lie algebras allowing the direct implementation of a Cartan decomposition on a quantum computer. The construction is recursive and allows us to expand any circuit down to generators and rotation matrices on individual qubits, where through our recursive algorithm we find that the generators themselves can be expressed with controlled-not (cnot) and swap gates explicitly. Our approach is independent of the standard cnot implementation and can be easily adapted to other cross-qubit circuit elements. In addition to its versatility, we also achieve near-optimal counts when working with cnot gates, achieving an asymptotic cnot cost of 21164n\frac{21}{16}{4}^{n}1621​4n for nnn qubits.
This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, $\CINC$, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d^n) two-qudit gates for state synthesis and O(d^{2n}) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the (n-2)/(d-2) ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.