arXiv:2306.13158

Breaking the cubic barrier in the Solovay-Kitaev algorithm

Greg Kuperberg

Published Jun 22, 2023• 4 citations

Abstract

We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length $O(n^{3+δ})$ to approximate an arbitrary target gate to $n$ bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is $O(n^{1.44042\ldots+δ})$. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity.

DOI: 10.48550/arxiv.2306.13158

Related papers

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

Adam Bouland, Victor Shyaka, Chenyi Zhang

quant-pharXiv:2610.03655Oct 5, 20260 citations

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

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

arXiv:1709.03007Sep 9, 20171 citation

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

Adam Bouland, Tudor Giurgică-Tiron

arXiv:2112.02040Dec 3, 20217 citations

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

Anuradha Mahasinghe, Dulmi Fernando, Kaushika De Silva

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

Quantum compiling problem without the inverses: an approach that reduces to multi-dimensional Knapsack problem

Yertay Zhiyenbayev, V. M. Akulin, Aikaterini Mandilara

Aug 29, 20170 citations

Quantum compiling with diffusive sets of gates

Yertay Zhiyenbayev, V. M. Akulin, Aikaterini Mandilara

arXiv:1708.08909Physical Review AJul 24, 201813 citations

arXiv:2306.13158

Breaking the cubic barrier in the Solovay-Kitaev algorithm

Greg Kuperberg

Published Jun 22, 2023• 4 citations

arXiv HTML PDF

Abstract

We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length

O(n^{3+δ})

to approximate an arbitrary target gate to

n

bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is

O(n^{1.44042\ldots+δ})

. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity.

DOI: 10.48550/arxiv.2306.13158

Related papers

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

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

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

Quantum compiling problem without the inverses: an approach that reduces to multi-dimensional Knapsack problem

Yertay Zhiyenbayev, V. M. Akulin, Aikaterini Mandilara

Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision $\varepsilon$ . Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter `nets' around the unity comprised by successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision $\varepsilon$ scales as $ \log (1/\varepsilon )^{\log 3 / log 2} $ while the pre-compilation time is increased as compared to thatof the Solovay-Kitaev algorithm by the exponential factor 3/2.Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision $\varepsilon$. Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter `nets' around the unity comprised by successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision $\varepsilon$ scales as $ \log (1/\varepsilon )^{\log 3 / log 2} $ while the pre-compilation time is increased as compared to thatof the Solovay-Kitaev algorithm by the exponential factor 3/2.

Aug 29, 20170 citations

Quantum compiling with diffusive sets of gates

Yertay Zhiyenbayev, V. M. Akulin, Aikaterini Mandilara

Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision $\ensuremath{\varepsilon}$. The Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter ``nets'' around unity comprised of successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision $\ensuremath{\varepsilon}$ scales as $log{(1/\ensuremath{\varepsilon})}^{log3/log2}$ while the precompilation time is increased as compared to that of the Solovay-Kitaev algorithm by the exponential factor $3/2$ .Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision $\ensuremath{\varepsilon}$. The Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter ``nets'' around unity comprised of successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision $\ensuremath{\varepsilon}$ scales as $log{(1/\ensuremath{\varepsilon})}^{log3/log2}$ while the precompilation time is increased as compared to that of the Solovay-Kitaev algorithm by the exponential factor $3/2$.

arXiv:1708.08909Physical Review AJul 24, 201813 citations

We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length

O(n^{3+δ})

to approximate an arbitrary target gate to

n

bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is

O(n^{1.44042\ldots+δ})

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.

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

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

\varepsilon

. Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter `nets' around the unity comprised by successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision

\varepsilon

scales as $ \log (1/\varepsilon )^{\log 3 / log 2} $ while the pre-compilation time is increased as compared to thatof the Solovay-Kitaev algorithm by the exponential factor 3/2.

3/2