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• 7 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•3 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•35 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

Quantum gate generation for systems with drift in U(n) using Lyapunov–LaSalle techniques

Hector Bessa Silveira, Paulo Sérgio Pereira da Silva, Pierre Rouchon

This paper considers right-invariant and controllable quantum systems with m inputs u = (u1,… , um) and state X(t) evolving on the unitary Lie group U(n). The ε-steering problem is introduced and solved for systems with drift: given any initial condition X0 at the initial time instant t0 ≥ 0, any goal state Xgoal∈ U(n) and ε > 0, find a control law such that dist(X(t0+t‾),Xgoal)≤ϵ, where t‾>0 is big enough and dist(X1, X2) is a convenient right-invariant notion of distance between two elements X1, X2 ∈ U(n). The purpose is to approximately generate arbitrary quantum gates corresponding to Xgoal. This is achieved by solving a tracking problem for a special kind of reference trajectories W‾: [t0, ∞) → U(n), which are here called c-universal reference trajectories. It is shown that, for this special kind of trajectories, the tracking problem can be solved up to an error ε for any reference trajectory X‾(t)=W‾(t)R which is a right-translation of W‾(t), at least when dist(X(t0),X‾(t0)) is finite. Furthermore, it is shown that dist(X(t),X‾(t)) converges uniformly exponentially to zero in the sense that the rate of convergence is independent of t0, R and X0. The approach considered here for showing such convergence is a generalisation of the results of a previous paper of the authors, which is mainly based on the central ideas of Jurdjevic and Quinn and Coron's return method. Taking a right-translation R such that X‾(t0+t‾)=Xgoal, one may solve the ε-steering problem by solving the tracking problem for the reference trajectory X‾(t), at least when dist(X(t0),X‾(t0))≤c. When dist(X(t0),X‾(t0))≥c, it is shown that the ε-steering problem can be globally solved in a two-iteration procedure. The underlying algorithmic complexity to get the steering control is essentially equivalent to the numerical integration of the Cauchy problem governing X(t). A numerical example considering a Toffoli quantum gate on U(8) for a chain of three coupled qubits that are controlled only locally is presented.

International Journal of Control•Mar 8, 2016•7 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.
This paper considers right-invariant and controllable quantum systems with m inputs u = (u1,… , um) and state X(t) evolving on the unitary Lie group U(n). The ε-steering problem is introduced and solved for systems with drift: given any initial condition X0 at the initial time instant t0 ≥ 0, any goal state Xgoal∈ U(n) and ε > 0, find a control law such that dist(X(t0+t‾),Xgoal)≤ϵ, where t‾>0 is big enough and dist(X1, X2) is a convenient right-invariant notion of distance between two elements X1, X2 ∈ U(n). The purpose is to approximately generate arbitrary quantum gates corresponding to Xgoal. This is achieved by solving a tracking problem for a special kind of reference trajectories W‾: [t0, ∞) → U(n), which are here called c-universal reference trajectories. It is shown that, for this special kind of trajectories, the tracking problem can be solved up to an error ε for any reference trajectory X‾(t)=W‾(t)R which is a right-translation of W‾(t), at least when dist(X(t0),X‾(t0)) is finite. Furthermore, it is shown that dist(X(t),X‾(t)) converges uniformly exponentially to zero in the sense that the rate of convergence is independent of t0, R and X0. The approach considered here for showing such convergence is a generalisation of the results of a previous paper of the authors, which is mainly based on the central ideas of Jurdjevic and Quinn and Coron's return method. Taking a right-translation R such that X‾(t0+t‾)=Xgoal, one may solve the ε-steering problem by solving the tracking problem for the reference trajectory X‾(t), at least when dist(X(t0),X‾(t0))≤c. When dist(X(t0),X‾(t0))≥c, it is shown that the ε-steering problem can be globally solved in a two-iteration procedure. The underlying algorithmic complexity to get the steering control is essentially equivalent to the numerical integration of the Cauchy problem governing X(t). A numerical example considering a Toffoli quantum gate on U(8) for a chain of three coupled qubits that are controlled only locally is presented.