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:1609.05780 · Annales Henri Poincaré

Universality of Single-Qudit Gates

Adam Sawicki, Katarzyna Karnas

Published Aug 10, 2017• 35 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s00023-017-0604-z

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

On a Problem of Construction of Efficient Universal Sets of Quantum Gates: A preliminary report

Qingzhong Liang, Steven B. Damelin

A 1-qubit gate is defined as an element of the unitary group $U(2)$, the group of complex valued matrices whose conjugate transposes equal their inverses. In quantum computing, it is important to be able to find good approximations of 1-qubit gates by using a dense group generated by a universal subset of the projective special unitary group $G=PSU(2)$. Here, $PSU(2)$ is the group formed by taking all elements of $U(2)$ with determinant 1 and taking the quotient of this subgroup by the group $\{I,-I\}$ where $I$ is the identity matrix. In this http URL [1], Sarnak recently studied this problem motivated by developing a continued fraction type algorithm for this problem. The continued fraction algorithm is the fastest known algorithm to approximate real numbers by the dense subset of rational numbers. In this report, we study the efficiency of the approximation of $G$ by using a dense group generated by a universal subset of $G$. The measure of the efficiency $K(g)$ of an arbitrary universal subset $g$ is defined in [1] and satisfies $K(g)\geqslant 1$. $g$ is more efficient when $K(g)$ is closer to $1$. We address some open problems posed by Sarnak in [1]. This report forms the basis of the shorter preprint [LD].

•Jun 18, 2015•0 citations

Criteria for exact qudit universality

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

We describe criteria for implementation of quantum computation in qudits. A qudit is a -dimensional system whose Hilbert space is spanned by states \ensuremath{\mid}0⟩, \ensuremath{\mid}1⟩, \dots{}, . An important earlier work [] describes how to exactly simulate an arbitrary unitary on multiple qudits using a parameter family of single qudit and two qudit gates. That technique is based on the spectral decomposition of unitaries. Here we generalize this argument to show that exact universality follows given a discrete set of single qudit Hamiltonians and one two-qudit Hamiltonian. The technique is related to the -matrix decomposition of numerical linear algebra. We consider a generic physical system in which the single qudit Hamiltonians are a small collection of and . A coupling graph results taking nodes 0, \dots{}, and edges are allowed Hamiltonians. One qudit exact universality follows iff this graph is connected, and complete universality results if the two-qudit Hamiltonian is also allowed. We discuss implementation in the eight dimensional ground electronic states of and construct an optimal gate sequence using Raman laser pulses.

arXiv:quant-ph/0407223•Physical Review A•May 16, 2005•86 citations

Universality of swap for qudits: a representation theory approach

James R. van Meter

An open problem of quantum information theory has been to determine under what conditions universal exchange-only computation is possible for qudits encoded on $d$-state systems for $d>2$. This problem can be posed in terms of representation theory by recognizing that each quantum mechanical swap, generated by exchange-interaction, can be identified with a transposition in a symmetric group, each $d$-state system can be identified with the fundamental representation of $SU(d)$, and each encoded qudit can be identified with an irreducible representation of a Lie algebra generated by transpositions. Towards this end we first give a mathematical definition of exchange-only universality in terms of a map from the special unitary algebra on the product of qudits into a representation of a Lie algebra generated by transpositions. We show that this definition is consistent with quantum computing requirements. We then proceed with the task of characterizing universal families of qudits, that is families of encoded qudits admitting exchange-only universality. This endeavor is aided by the fact that the irreducible representations corresponding to qudits are canonically labeled by partitions. In particular we derive necessary and sufficient conditions for universality on one or two such qudits, in terms of simple arithmetic conditions on the associated partitions. We also derive necessary and sufficient conditions for universality on arbitrarily many such qudits, in terms of Littlewood--Richardson coefficients. Among other results, we prove that universal families of multiple qudits are upward closed, that universality is guaranteed for sufficiently many qudits, and that any family that is not universal can be made so by simply adding at most five ancillae. We also obtain results for 2-state systems as a special case.

arXiv:2103.12303•Mar 23, 2021•2 citations

A Note on a Quantitative Form of the Solovay-Kitaev Theorem

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

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 $SU(2)$ to approximate an arbitrary element of $SU(2)$. The Solovay-Kitaev Theorem is a well-known theorem that guarantees the existence of a finite sequence of 1-qubit quantum gates approximating an arbitrary unitary matrix in $SU(2)$ within specified accuracy $\varepsilon > 0$. In this note we study a quantitative description of this theorem in the following sense. 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 $\varepsilon > 0$ small enough, 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$. For a measure of efficiency on T, which we denote $K(T)$, we prove the following theorem: Fix a $δ$ in $[0, \frac{2}{3}]$. Choose $f: (0, \infty) \rightarrow (1, \infty)$ satisfying $\lim_{\varepsilon\to 0+}\dfrac{\log(f(t_{\varepsilon}))}{t_{\varepsilon}}$ exists with value $0$. Assume that the inequality $\varepsilon \leqslant f(t_{\varepsilon})\cdot 5^{\frac{-t_{\varepsilon}}{6-3δ}}$ holds. Then $K(T) \leqslant 2-δ$. Our conjecture implies the following: Let $ν(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}=ν(5^{t_{\varepsilon}})\cupν(5^{t_{\varepsilon}-1})$ on the sphere $S^{3}$ in $\mathbb{R}^{4}$. Then $M \sim f(\log N)N^{\frac{-1}{6-3δ}}$. Here $N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2$.

arXiv:1709.03007•Sep 9, 2017•1 citation

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
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 group of complex valued matrices whose conjugate transposes equal their inverses. In quantum computing, it is important to be able to find good approximations of 1-qubit gates by using a dense group generated by a universal subset of the projective special unitary group G=PSU(2)G=PSU(2)G=PSU(2). Here, PSU(2)PSU(2)PSU(2) is the group formed by taking all elements of U(2)U(2)U(2) with determinant 1 and taking the quotient of this subgroup by the group {I,−I}\{I,-I\}{I,−I} where III is the identity matrix. In this http URL [1], Sarnak recently studied this problem motivated by developing a continued fraction type algorithm for this problem. The continued fraction algorithm is the fastest known algorithm to approximate real numbers by the dense subset of rational numbers. In this report, we study the efficiency of the approximation of GGG by using a dense group generated by a universal subset of GGG. The measure of the efficiency K(g)K(g)K(g) of an arbitrary universal subset ggg is defined in [1] and satisfies K(g)⩾1K(g)\geqslant 1K(g)⩾1. ggg is more efficient when K(g)K(g)K(g) is closer to 111. We address some open problems posed by Sarnak in [1]. This report forms the basis of the shorter preprint [LD].
We describe criteria for implementation of quantum computation in qudits. A qudit is a -dimensional system whose Hilbert space is spanned by states \ensuremath{\mid}0⟩, \ensuremath{\mid}1⟩, \dots{}, . An important earlier work [] describes how to exactly simulate an arbitrary unitary on multiple qudits using a parameter family of single qudit and two qudit gates. That technique is based on the spectral decomposition of unitaries. Here we generalize this argument to show that exact universality follows given a discrete set of single qudit Hamiltonians and one two-qudit Hamiltonian. The technique is related to the -matrix decomposition of numerical linear algebra. We consider a generic physical system in which the single qudit Hamiltonians are a small collection of and . A coupling graph results taking nodes 0, \dots{}, and edges are allowed Hamiltonians. One qudit exact universality follows iff this graph is connected, and complete universality results if the two-qudit Hamiltonian is also allowed. We discuss implementation in the eight dimensional ground electronic states of and construct an optimal gate sequence using Raman laser pulses.
An open problem of quantum information theory has been to determine under what conditions universal exchange-only computation is possible for qudits encoded on ddd-state systems for d>2d>2d>2. This problem can be posed in terms of representation theory by recognizing that each quantum mechanical swap, generated by exchange-interaction, can be identified with a transposition in a symmetric group, each ddd-state system can be identified with the fundamental representation of SU(d)SU(d)SU(d), and each encoded qudit can be identified with an irreducible representation of a Lie algebra generated by transpositions. Towards this end we first give a mathematical definition of exchange-only universality in terms of a map from the special unitary algebra on the product of qudits into a representation of a Lie algebra generated by transpositions. We show that this definition is consistent with quantum computing requirements. We then proceed with the task of characterizing universal families of qudits, that is families of encoded qudits admitting exchange-only universality. This endeavor is aided by the fact that the irreducible representations corresponding to qudits are canonically labeled by partitions. In particular we derive necessary and sufficient conditions for universality on one or two such qudits, in terms of simple arithmetic conditions on the associated partitions. We also derive necessary and sufficient conditions for universality on arbitrarily many such qudits, in terms of Littlewood--Richardson coefficients. Among other results, we prove that universal families of multiple qudits are upward closed, that universality is guaranteed for sufficiently many qudits, and that any family that is not universal can be made so by simply adding at most five ancillae. We also obtain results for 2-state systems as a special case.
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 SU(2)SU(2)SU(2) to approximate an arbitrary element of SU(2)SU(2)SU(2). The Solovay-Kitaev Theorem is a well-known theorem that guarantees the existence of a finite sequence of 1-qubit quantum gates approximating an arbitrary unitary matrix in SU(2)SU(2)SU(2) within specified accuracy ε>0\varepsilon > 0ε>0. In this note we study a quantitative description of this theorem in the following sense. 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 ε>0\varepsilon > 0ε>0 small enough, 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. For a measure of efficiency on T, which we denote K(T)K(T)K(T), we prove the following theorem: Fix a δδδ in [0,23][0, \frac{2}{3}][0,32​]. Choose f:(0,∞)→(1,∞)f: (0, \infty) \rightarrow (1, \infty)f:(0,∞)→(1,∞) satisfying lim⁡ε→0+log⁡(f(tε))tε\lim_{\varepsilon\to 0+}\dfrac{\log(f(t_{\varepsilon}))}{t_{\varepsilon}}limε→0+​tε​log(f(tε​))​ exists with value 000. Assume that the inequality ε⩽f(tε)⋅5−tε6−3δ\varepsilon \leqslant f(t_{\varepsilon})\cdot 5^{\frac{-t_{\varepsilon}}{6-3δ}}ε⩽f(tε​)⋅56−3δ−tε​​ holds. Then K(T)⩽2−δK(T) \leqslant 2-δK(T)⩽2−δ. Our conjecture implies the following: Let ν(5tε)ν(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}=ν(5^{t_{\varepsilon}})\cupν(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−16−3δM \sim f(\log N)N^{\frac{-1}{6-3δ}}M∼f(logN)N6−3δ−1​. Here N≡N(ε)=6⋅5tε−2N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2N≡N(ε)=6⋅5tε​−2.
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.