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

On a Problem of Sarnak Related to Constructing Efficient Universal Sets of Quantum Gates

Qingzhong Liang, Steven B. Damelin

Published Jun 18, 2015• 0 citations
OpenAlex

Abstract

Constructing an efficient universal subset of quantum gates can be done by finding an efficient universal subset of $G=PSU(2)$ (or $SU(2)$). Following [Letter], we define the efficiency $K$ of a universal subset of $G$. We focus on two different universal subsets $S$ and $T$, and estimate their efficiencies. We show that the efficiency of the first set is bounded by $\frac{4}{3}\leqslant K(S)\leqslant 2$. Also, based on a conjecture about covering radius on $3$-sphere, we show the efficiency of the second set is $K(T)=\frac{4}{3}$, based on a question of Sarnak.

Related papers

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

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

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

Elementary Quantum Gates from Lie Group Embeddings in $U(2^n)$: Geometry, Universality, and Discretization

Antonio Falco, Daniela Falco-Pomares, Hermann G. Matthies

In the standard circuit model, elementary gates are defined relative to a chosen tensor factorization and are therefore extrinsic to the ambient group $U(2^n)$. Writing $N=2^n$, we introduce an \emph{intrinsic descriptor layer} in $U(N)$ by declaring as primitive the motions inside faithful embedded copies of $SU(2)$ (phase-free), together with a phase-inclusive $U(2)$ variant. We describe the embedding landscape $\Emb(SU(2),U(N))$ as a finite union of $U(N)$-homogeneous strata indexed by isotypic multiplicities, with stabilizers given by centralizers, and we isolate a canonical \emph{two-level sector} parameterized by $\Gr_2(\C^N)$ up to a $PSU(2)$ gauge. Equipping $U(N)$ with the Hilbert--Schmidt bi-invariant metric, each embedded subgroup is totally geodesic, yielding a variational characterization of elementary motions via minimal-norm logarithms. On the constructive side, we prove phase-free universality in $SU(N)$ from two-level primitives using QR/Givens factorizations together with explicit diagonal generation, and we obtain full universality in $U(N)$ by explicit abelian phase bookkeeping (equivalently, via the $U(2)$ two-level dictionary). Finally, we formalize a modular finite-alphabet compilation interface: any approximation routine in $SU(2)$ (e.g.\ Solovay--Kitaev) can be lifted through two-level embeddings to yield $U(N)$-level synthesis with global operator-norm error control.

quant-pharXiv:2601.17936•Jan 27, 2026•0 citations

Efficient quantum approximation : examining the efficiency of select universal gate sets in approximating 1-qubit quantum gates.

Brent A Mode

Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.

•Jan 1, 2018•0 citations

Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm

Adam Bouland, Tudor Giurgică-Tiron

The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both $\text{SU}(d)$ and $\text{SL}(d, \mathbb{C})$. The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.

arXiv:2112.02040•Dec 3, 2021•7 citations
Constructing an efficient universal subset of quantum gates can be done by finding an efficient universal subset of G=PSU(2)G=PSU(2)G=PSU(2) (or SU(2)SU(2)SU(2)). Following [Letter], we define the efficiency KKK of a universal subset of GGG. We focus on two different universal subsets SSS and TTT, and estimate their efficiencies. We show that the efficiency of the first set is bounded by 43⩽K(S)⩽2\frac{4}{3}\leqslant K(S)\leqslant 234​⩽K(S)⩽2. Also, based on a conjecture about covering radius on 333-sphere, we show the efficiency of the second set is K(T)=43K(T)=\frac{4}{3}K(T)=34​, based on a question of Sarnak.
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].
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].
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.
Elementary Quantum Gates from Lie Group Embeddings in U(2n)U(2^n)U(2n): Geometry, Universality, and Discretization
In the standard circuit model, elementary gates are defined relative to a chosen tensor factorization and are therefore extrinsic to the ambient group U(2n)U(2^n)U(2n). Writing N=2nN=2^nN=2n, we introduce an \emph{intrinsic descriptor layer} in U(N)U(N)U(N) by declaring as primitive the motions inside faithful embedded copies of SU(2)SU(2)SU(2) (phase-free), together with a phase-inclusive U(2)U(2)U(2) variant. We describe the embedding landscape $\Emb(SU(2),U(N))$ as a finite union of U(N)U(N)U(N)-homogeneous strata indexed by isotypic multiplicities, with stabilizers given by centralizers, and we isolate a canonical \emph{two-level sector} parameterized by $\Gr_2(\C^N)$ up to a PSU(2)PSU(2)PSU(2) gauge. Equipping U(N)U(N)U(N) with the Hilbert--Schmidt bi-invariant metric, each embedded subgroup is totally geodesic, yielding a variational characterization of elementary motions via minimal-norm logarithms. On the constructive side, we prove phase-free universality in SU(N)SU(N)SU(N) from two-level primitives using QR/Givens factorizations together with explicit diagonal generation, and we obtain full universality in U(N)U(N)U(N) by explicit abelian phase bookkeeping (equivalently, via the U(2)U(2)U(2) two-level dictionary). Finally, we formalize a modular finite-alphabet compilation interface: any approximation routine in SU(2)SU(2)SU(2) (e.g.\ Solovay--Kitaev) can be lifted through two-level embeddings to yield U(N)U(N)U(N)-level synthesis with global operator-norm error control.
Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both SU(d)\text{SU}(d)SU(d) and SL(d,C)\text{SL}(d, \mathbb{C})SL(d,C). The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.