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:quant-ph/0111133

Uniform Finite Generation of Compact Lie Groups and universal quantum gates

Domenico D’Alessandro

Published Nov 24, 2001• 8 citations
arXivHTMLPDF

Abstract

Consider a compact connected Lie group $G$ and the corresponding Lie algebra $\cal L$. Let $\{X_1,...,X_m\}$ be a set of generators for the Lie algebra $\cal L$. We prove that $G$ is uniformly finitely generated by $\{X_1,...,X_m\}$. This means that every element $K \in G$ can be expressed as $K=e^{Xt_1}e^{Xt_2} \cdot \cdot \cdot e^{Xt_l}$, where the indeterminates $X$ are in the set $\{X_1,...,X_m \}$, $t_i \in \RR$, $i=1,...,l$, and the number $l$ is uniformly bounded. This extends a previous result by F. Lowenthal in that we do not require the connected one dimensional Lie subgroups corresponding to the $X_i$, $i=1,...,m$, to be compact. We discuss the consequence of this result to the question of universality of quantum gates in quantum computing.

DOI
10.48550/arxiv.quant-ph/0111133

Related papers

On the universality and membership problems for quantum gates

Lorenzo Mattioli, Adam Sawicki

We study the universality and membership problems for gate sets consisting of a finite number of quantum gates. Our approach relies on the techniques from compact Lie group theory. We also introduce an auxiliary problem called the subgroup universality problem, which helps in solving some instances of the membership problem and can be of interest on its own. The resulting theorems are mainly formulated in terms of centralizers and the adjoint representations of a given set of quantum gates.

arXiv:2110.04210•Journal of Mathematical Physics•Apr 1, 2023•5 citations

Universal computation with magic Hamiltonians

Marius Junge, Jason Pollack, Luke Visser

In the conventional theory of quantum computation, universality is discussed in terms of properties of unitary gate sets. In many experimental setups, however, we instead have access to a parametrized set of Hamiltonians, which can be exponentiated for any desired time. Accordingly, we formulate a continuous analogue of universality, where adding one expensive Hamiltonian control to a cheap set of local control operators allows for universal computation. We find several concrete sets of 1- or 2-local Pauli generators $S$ and $n$-qubit ``magic" Hamiltonians $H$ that together generate the full Lie algebra $\mathfrak{su}(2^n)$, with a special focus on the Ising Hamiltonian $J$. We propose a method to directly implement any unitary by exponentiating these generator sets, and give bounds on the needed time of application of the magic Hamiltonian $H$. We find that the number of applications of $H$ needed to approximate any unitary up to accuracy $ε$ scales exponentially in the number of qubits as expected from the standard application of the Solovay-Kitaev theorem. We also find phase transitions in the size of the generated Lie algebras as the parameters of the Ising Hamiltonian are varied. We find an algorithmic application of the Chow/Rashevskii technique to implement unitaries corresponding to iterated commutators.

quant-pharXiv:2609.14757•Sep 15, 2026•0 citations

Universality of Single-Qudit Gates

Adam Sawicki, Katarzyna Karnas

We consider the problem of deciding if a set of quantum one-qudit gates $$\mathcal {S}=\{g_1,\ldots ,g_n\}\subset G$$ is universal, i.e. if $${<}\mathcal {S}{>}$$ is dense in G, where G is either the special unitary or the special orthogonal group. To every gate g in $$\mathcal {S}$$ we assign the orthogonal matrix $$\mathrm {Ad}_g$$ that is image of g under the adjoint representation $$\mathrm {Ad}:G\rightarrow SO(\mathfrak {g})$$ and $$\mathfrak {g}$$ is the Lie algebra of G. The necessary condition for the universality of $$\mathcal {S}$$ is that the only matrices that commute with all $$\mathrm {Ad}_{g_i}$$ ’s are proportional to the identity. If in addition there is an element in $${<}\mathcal {S}{>}$$ whose Hilbert–Schmidt distance from the centre of G belongs to $$]0,\frac{1}{\sqrt{2}}[$$ , then $$\mathcal {S}$$ is universal. Using these we provide a simple algorithm that allows deciding the universality of any set of d-dimensional gates in a finite number of steps and formulate a general classification theorem.

arXiv:1609.05780•Annales Henri Poincaré•Aug 10, 2017•36 citations

On Golden Gates and Discrepancy

Steven B. Damelin, Qiwei Liang, B. A. W. Mode

A 1-qubit gate is defined as an element of the unitary group $U(2)$. The problem of finding good approximations of arbitrary 1-qubit gates is identical to that of finding a dense group generated by a universal subset of $PSU(2)$ to approximate an arbitrary element of $U(2)$. Notably, this problem has been recently studied by Sarnak in [8]. We will work with a universal gate set $T$, a subset of $SU(2)$ such that the group generated by the elements of $T$ is dense in $SU(2)$. For an arbitrary $\varepsilon > 0$, we define $t_{\varepsilon}$ as the minimum reduced word length such that every point of $SU(2)$ lies within a ball of radius $\varepsilon$ centered at the points in the dense subgroup generated by $T$. We define a measure of efficiency on $T$, denoted $K(T)$, construct a $t_{\varepsilon}'$ such that most points in $PSU(2)$ have optimally efficient approximation and we conjecture that $\varepsilon \leq f(t_{\varepsilon})5^{-t_{\varepsilon}/4}$ for a function $f:(0,\infty)\to (1,\infty)$ satisfying: \begin{equation*} \lim_{ t_{\varepsilon} \to \infty} log(f(t_{\varepsilon}))/t_{\varepsilon} \end{equation*} exists with value $0$. Our conjecture can be formulated to mean the following: Let $\nu(5^{t_{\varepsilon}})$ denote the set of integer solutions of the quadratic form: $x_1^2+x_2^2+x_3^2+x_4^2=5^{t_{\varepsilon}}$. Let $M\equiv M_{S^3}(\mathcal{N})$ denote the covering radius of the points $\mathcal{N}=\nu(5^{t_{\varepsilon}})\cup\nu(5^{t_{\varepsilon}-1})$ on the sphere $S^{3}$ in $\mathbb{R}^{4}$. Then $M \sim f(\log N)N^{-1/4}$. Here $N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2$. This is a weaker conjecture than that proposed in [2], namely: $M\geq N^{{-1/4}+o(1)}$. We prove that this conjecture implies that $K(T)=\dfrac{4}{3}$. This answers a question of Sarnak in [8].

•Jun 18, 2015•0 citations

A Lie-algebraic Criterion for the Universality of Exponentiated Quantum Gates

Yinuo Xue, Qian Chen, Jing-Song Huang

We present a criterion that serves as the basis for a polynomial-time algorithm to decide whether a finite set of qudit gates exponentiated by some Hamiltonians is universal. Our approach formulates universality in Lie algebraic terms and applies Borel--de Siebenthal theory with a diagonal generator having incommensurate spectrum. In this framework, nonuniversality is detected by invariant subspaces, equivalently by a graph-connectivity obstruction, while universality is repaired by adding generators that couple disconnected components. We further prove that two generators are sufficient for universal control. Our work reveals a profound link between qudit universality and irreducibility of Lie algebra representations.

quant-pharXiv:2604.25971•Apr 29, 2026•0 citations

Full classification of Pauli Lie algebras

Aguilar, Gerard, Simon Cichy, Jens Eisert +1 more

Lie groups, and therefore Lie algebras, are fundamental structures in quantum physics that determine the space of possible trajectories of evolving systems. However, classification and characterization methods for these structures are often impractical for larger systems. In this work, we provide a comprehensive classification of Lie algebras generated by an arbitrary set of Pauli operators, from which an efficient method to characterize them follows. By mapping the problem to a graph setting, we identify a reduced set of equivalence classes: the free-fermionic Lie algebra, the set of all anti-symmetric Paulis on n qubits, the Lie algebra of symplectic Paulis on n qubits, and the space of all Pauli operators on n qubits, as well as controlled versions thereof. Moreover, out of these, we distinguish 6 Clifford inequivalent cases and find a simple set of canonical operators for each, which allow us to give a physical interpretation of the dynamics of each class. Our findings reveal a no-go result for the existence of small Lie algebras beyond the free-fermionic case in the Pauli setting and offer efficiently computable criteria for universality and extendibility of gate sets. These results bear significant impact in ideas in a number of fields like quantum control, quantum machine learning, or classical simulation of quantum circuits.

arXiv:2408.00081•Jul 31, 2024•50 citations
Consider a compact connected Lie group GGG and the corresponding Lie algebra L\cal LL. Let {X1,...,Xm}\{X_1,...,X_m\}{X1​,...,Xm​} be a set of generators for the Lie algebra L\cal LL. We prove that GGG is uniformly finitely generated by {X1,...,Xm}\{X_1,...,X_m\}{X1​,...,Xm​}. This means that every element K∈GK \in GK∈G can be expressed as K=eXt1eXt2⋅⋅⋅eXtlK=e^{Xt_1}e^{Xt_2} \cdot \cdot \cdot e^{Xt_l}K=eXt1​eXt2​⋅⋅⋅eXtl​, where the indeterminates XXX are in the set {X1,...,Xm}\{X_1,...,X_m \}{X1​,...,Xm​}, ti∈\RRt_i \in \RRti​∈\RR, i=1,...,li=1,...,li=1,...,l, and the number lll is uniformly bounded. This extends a previous result by F. Lowenthal in that we do not require the connected one dimensional Lie subgroups corresponding to the XiX_iXi​, i=1,...,mi=1,...,mi=1,...,m, to be compact. We discuss the consequence of this result to the question of universality of quantum gates in quantum computing.
In the conventional theory of quantum computation, universality is discussed in terms of properties of unitary gate sets. In many experimental setups, however, we instead have access to a parametrized set of Hamiltonians, which can be exponentiated for any desired time. Accordingly, we formulate a continuous analogue of universality, where adding one expensive Hamiltonian control to a cheap set of local control operators allows for universal computation. We find several concrete sets of 1- or 2-local Pauli generators SSS and nnn-qubit ``magic" Hamiltonians HHH that together generate the full Lie algebra su(2n)\mathfrak{su}(2^n)su(2n), with a special focus on the Ising Hamiltonian JJJ. We propose a method to directly implement any unitary by exponentiating these generator sets, and give bounds on the needed time of application of the magic Hamiltonian HHH. We find that the number of applications of HHH needed to approximate any unitary up to accuracy εεε scales exponentially in the number of qubits as expected from the standard application of the Solovay-Kitaev theorem. We also find phase transitions in the size of the generated Lie algebras as the parameters of the Ising Hamiltonian are varied. We find an algorithmic application of the Chow/Rashevskii technique to implement unitaries corresponding to iterated commutators.
We consider the problem of deciding if a set of quantum one-qudit gates S={g1,…,gn}⊂G\mathcal {S}=\{g_1,\ldots ,g_n\}\subset GS={g1​,…,gn​}⊂G is universal, i.e. if <S>{<}\mathcal {S}{>}<S> is dense in G, where G is either the special unitary or the special orthogonal group. To every gate g in S\mathcal {S}S we assign the orthogonal matrix Adg\mathrm {Ad}_gAdg​ that is image of g under the adjoint representation Ad:G→SO(g)\mathrm {Ad}:G\rightarrow SO(\mathfrak {g})Ad:G→SO(g) and g\mathfrak {g}g is the Lie algebra of G. The necessary condition for the universality of S\mathcal {S}S is that the only matrices that commute with all Adgi\mathrm {Ad}_{g_i}Adgi​​ ’s are proportional to the identity. If in addition there is an element in <S>{<}\mathcal {S}{>}<S> whose Hilbert–Schmidt distance from the centre of G belongs to ]0,12[]0,\frac{1}{\sqrt{2}}[]0,2​1​[ , then S\mathcal {S}S is universal. Using these we provide a simple algorithm that allows deciding the universality of any set of d-dimensional gates in a finite number of steps and formulate a general classification theorem.
A 1-qubit gate is defined as an element of the unitary group U(2)U(2)U(2). The problem of finding good approximations of arbitrary 1-qubit gates is identical to that of finding a dense group generated by a universal subset of PSU(2)PSU(2)PSU(2) to approximate an arbitrary element of U(2)U(2)U(2). Notably, this problem has been recently studied by Sarnak in [8]. We will work with a universal gate set TTT, a subset of SU(2)SU(2)SU(2) such that the group generated by the elements of TTT is dense in SU(2)SU(2)SU(2). For an arbitrary ε>0\varepsilon > 0ε>0, we define tεt_{\varepsilon}tε​ as the minimum reduced word length such that every point of SU(2)SU(2)SU(2) lies within a ball of radius ε\varepsilonε centered at the points in the dense subgroup generated by TTT. We define a measure of efficiency on TTT, denoted K(T)K(T)K(T), construct a tε′t_{\varepsilon}'tε′​ such that most points in PSU(2)PSU(2)PSU(2) have optimally efficient approximation and we conjecture that ε≤f(tε)5−tε/4\varepsilon \leq f(t_{\varepsilon})5^{-t_{\varepsilon}/4}ε≤f(tε​)5−tε​/4 for a function f:(0,∞)→(1,∞)f:(0,\infty)\to (1,\infty)f:(0,∞)→(1,∞) satisfying: \begin{equation*} \lim_{ t_{\varepsilon} \to \infty} log(f(t_{\varepsilon}))/t_{\varepsilon} \end{equation*} exists with value 000. Our conjecture can be formulated to mean the following: Let ν(5tε)\nu(5^{t_{\varepsilon}})ν(5tε​) denote the set of integer solutions of the quadratic form: x12+x22+x32+x42=5tεx_1^2+x_2^2+x_3^2+x_4^2=5^{t_{\varepsilon}}x12​+x22​+x32​+x42​=5tε​. Let M≡MS3(N)M\equiv M_{S^3}(\mathcal{N})M≡MS3​(N) denote the covering radius of the points N=ν(5tε)∪ν(5tε−1)\mathcal{N}=\nu(5^{t_{\varepsilon}})\cup\nu(5^{t_{\varepsilon}-1})N=ν(5tε​)∪ν(5tε​−1) on the sphere S3S^{3}S3 in R4\mathbb{R}^{4}R4. Then M∼f(log⁡N)N−1/4M \sim f(\log N)N^{-1/4}M∼f(logN)N−1/4. Here N≡N(ε)=6⋅5tε−2N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2N≡N(ε)=6⋅5tε​−2. This is a weaker conjecture than that proposed in [2], namely: M≥N−1/4+o(1)M\geq N^{{-1/4}+o(1)}M≥N−1/4+o(1). We prove that this conjecture implies that K(T)=43K(T)=\dfrac{4}{3}K(T)=34​. This answers a question of Sarnak in [8].
We present a criterion that serves as the basis for a polynomial-time algorithm to decide whether a finite set of qudit gates exponentiated by some Hamiltonians is universal. Our approach formulates universality in Lie algebraic terms and applies Borel--de Siebenthal theory with a diagonal generator having incommensurate spectrum. In this framework, nonuniversality is detected by invariant subspaces, equivalently by a graph-connectivity obstruction, while universality is repaired by adding generators that couple disconnected components. We further prove that two generators are sufficient for universal control. Our work reveals a profound link between qudit universality and irreducibility of Lie algebra representations.
Lie groups, and therefore Lie algebras, are fundamental structures in quantum physics that determine the space of possible trajectories of evolving systems. However, classification and characterization methods for these structures are often impractical for larger systems. In this work, we provide a comprehensive classification of Lie algebras generated by an arbitrary set of Pauli operators, from which an efficient method to characterize them follows. By mapping the problem to a graph setting, we identify a reduced set of equivalence classes: the free-fermionic Lie algebra, the set of all anti-symmetric Paulis on n qubits, the Lie algebra of symplectic Paulis on n qubits, and the space of all Pauli operators on n qubits, as well as controlled versions thereof. Moreover, out of these, we distinguish 6 Clifford inequivalent cases and find a simple set of canonical operators for each, which allow us to give a physical interpretation of the dynamics of each class. Our findings reveal a no-go result for the existence of small Lie algebras beyond the free-fermionic case in the Pauli setting and offer efficiently computable criteria for universality and extendibility of gate sets. These results bear significant impact in ideas in a number of fields like quantum control, quantum machine learning, or classical simulation of quantum circuits.