The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error

ε

using merely

\mathrm{polylog}(1/ε)

gates from any finite universal quantum gate set

\mathcal{G}

. One drawback to the theorem is that it requires the gate set

\mathcal{G}

to be closed under inversion. Here we show that this restriction can be traded for the assumption that

\mathcal{G}

contains an irreducible representation of any finite group

G

. This extends recent work of Sardharwalla et al. [arXiv:1602.07963], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [arXiv:quant-ph/0505030, arXiv:0908.0512].

DOI: 10.4230/lipics.tqc.2018.6

Related papers

Trading Inverses for an Irrep in the Solovay-Kitaev Theorem

Adam Bouland, Māris Ozols

The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error epsilon using merely polylog(1/epsilon) gates from any finite universal quantum gate set G. One drawback to the theorem is that it requires the gate set G to be closed under inversion. Here we show that this restriction can be traded for the assumption that G contains an irreducible representation of any finite group G. This extends recent work of Sardharwalla et al. [Sardharwalla et al., 2016], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [Dawson and Nielsen, 2006; Kuperberg, 2015].The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error epsilon using merely polylog(1/epsilon) gates from any finite universal quantum gate set G. One drawback to the theorem is that it requires the gate set G to be closed under inversion. Here we show that this restriction can be traded for the assumption that G contains an irreducible representation of any finite group G. This extends recent work of Sardharwalla et al. [Sardharwalla et al., 2016], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [Dawson and Nielsen, 2006; Kuperberg, 2015].

Conference on Theory of Quantum Computation, Communication and CryptographyJul 1, 20181 citation

Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm

Adam Bouland, Victor Shyaka, Chenyi Zhang

The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy $ε$ in $\text{polylog}(1/ε)$ time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over $8.62$ , while information theoretically it is known that an inverse-free exponent of $3$ is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most $\approx 2.138$ . Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient ``Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$ . This result uses a novel form of approximate ``aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy $ε$ in $\text{polylog}(1/ε)$ time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over $8.62$, while information theoretically it is known that an inverse-free exponent of $3$ is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most $\approx 2.138$. Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient ``Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$. This result uses a novel form of approximate ``aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.

quant-pharXiv:2610.03655Oct 5, 20260 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.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.02040Dec 3, 20217 citations

Qutrit-Based Orthogonal Approximations with Inverse-Free Quantum Gate Sets

Anuradha Mahasinghe, Dulmi Fernando, Kaushika De Silva

The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.

International Online Conference on Mathematics and Applications (IOCMA)Jun 13, 20230 citations

Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem

H. F. Chau

Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of $ε> 0$ requires $\text{O}(\log^c[1/ε])$ quantum gates with $c > 1.44042$ . Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using $Ω(\log[1/ε])$ gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using $\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)$ FT gates chosen from a finite set depending on the value of $ε$ . The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy $ε> 0$ . This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of $ε> 0$ requires $\text{O}(\log^c[1/ε])$ quantum gates with $c > 1.44042$. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using $Ω(\log[1/ε])$ gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using $\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)$ FT gates chosen from a finite set depending on the value of $ε$. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy $ε> 0$. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.

arXiv:2406.04846Jun 7, 20240 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$ .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.03007Sep 9, 20171 citation

The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error

ε

using merely

\mathrm{polylog}(1/ε)

gates from any finite universal quantum gate set

\mathcal{G}

. One drawback to the theorem is that it requires the gate set

\mathcal{G}

to be closed under inversion. Here we show that this restriction can be traded for the assumption that

\mathcal{G}

contains an irreducible representation of any finite group

G

The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy

ε

\text{polylog}(1/ε)

time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over

8.62

, while information theoretically it is known that an inverse-free exponent of

3

is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most

\approx 2.138

. Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient ``Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most

2.988

. This result uses a novel form of approximate ``aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.

\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.

ε> 0

requires

\text{O}(\log^c[1/ε])

quantum gates with

c > 1.44042

. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using

Ω(\log[1/ε])

gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using

\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)

FT gates chosen from a finite set depending on the value of

ε

. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy

ε> 0

. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.

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

δ

[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}

\mathbb{R}^{4}

. Then

M \sim f(\log N)N^{\frac{-1}{6-3δ}}

. Here

N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2