# Solovay–Kitaev Approximations of Special Orthogonal Matrices

Authors: Anuradha Mahasinghe; Sachiththa Bandaranayake; Kaushika De Silva
Journal: Advances in Mathematical Physics
 (2020)

---

## Abstract

The circuit-gate framework of quantum computing relies on the fact that an arbitrary quantum gate in the form of a unitary matrix of unit determinant can be approximated to a desired accuracy by a fairly short sequence of basic gates, of which the exact bounds are provided by the Solovay–Kitaev theorem. In this work, we show that a version of this theorem is applicable to orthogonal matrices with unit determinant as well, indicating the possibility of using orthogonal matrices for efficient computation. We further develop a version of the Solovay–Kitaev algorithm and discuss the computational experience.


---

## Body

## 1. Introduction

A computer program in the context of classical computing is an ordered list of instructions, expressible in terms of elementary operations, readily convertible to the machine language of a classical computer. A quantum program in quantum computing could be described analogously. According to the circuit-gate framework of quantum computing, a quantum algorithm consists of quantum gates acting on quantum states (qubits) where measuring devices are applied at appropriate instances to collapse the wavefunction. Based on the Heisenberg–Born interpretation of quantum mechanics, this circuit-gate framework has achieved significant progress up to date, as the pioneering model of quantum computing. Also, it is proven to be polynomially equivalent to other quantum computational frameworks. Accordingly, a quantum program can be regarded as the application of several unitary matrices, together with measurements at certain instances.In order to implement unitary operations, basic quantum gates such asPauli gates, Hadamard gate, and phase gate are available in the circuit-gate framework, in analogy with basic gates in classical computing. It is quite natural to ask how many basic gates are needed to implement an arbitrary unitary operation in a quantum circuit. The remarkable contributions in this regard made independently by Solovay [1] and Kitaev [2] answered this question, resulting in what is known today as the Solovay–Kitaev theorem. This theorem states that it is possible to approximate any 2×2 unitary with unit determinant by a product of Olog41/ε physically realizable 2×2 unitaries (which appear as basic gates) to an arbitrary accuracy ε [3, 4]. Recall the other quantum computational frameworks such as quantum walks, quantum Turing machines, and adiabatic computing were proven to be polynomially equivalent to the circuit-gate framework [5–7], the Solovay–Kitaev theorem is widely regarded the theoretical proof for the supremacy of quantum computers. In addition, the number of elementary gates needed to implement an arbitrary unitary provides an indicator of the capacity and limitations of quantum computers.This reveals an interesting aspect of unconventional models of computing. That is, any computational model with similar speed and limitations would be computationally equivalent to quantum computing. If physically realizable, such a model would have the same advantages and limitations as quantum computing. Though little attention has been paid to this subject in the past, several interesting works have investigated the possibility of having such models. A pioneering work was done by Aerts and Czachor in 2007, proposing geometric algebras instead of unitary matrices [8]. The authors named this model cartoon computing and proved its equivalence to quantum computing, demonstrating a simulation of the Deutsch-Jozsa algorithm. A later work investigated entities in cartoon computing equivalent to elementary gates in quantum computing [9]. In 2008, Fernandez and Schneeberger proposed quaternionic computing, in which the possibility of adopting quaternions instead of unitary matrices was proven [10]. In order to show the equivalence to quantum computing, the authors have used the Bernstein–Vazirani theorem in quantum Turing machine framework. In [11], Graydon explored quaternionic quantum processes with respect to standard quantum information theory. Thus, it is an interesting question to ask what other algebraic structures would show similar behaviour, if employed as a computational model.On the other hand, the progress achieved in three-level quantum systems is noteworthy [12–14]. Instead of qubits with states 0 and 1 in standard circuit-gate framework, qutrits having three basis states 0, 1, and 2 are used in these systems. Analogous to the single-qubit quantum gates in the form of 2×2 matrices in the special (unit determinant) unitary group SU2, the single-qutrit gates are 3×3 special unitaries or the elements in the group SU3 [15–17]. Though the realization of SU3 gates has been the topic of interest for several previous works [18–20], computational capacity or theoretical bounds on computing of a three-level quantum system have not been paid the deserved attention. Neither Solovay–Kitaev type approximations were investigated for three-level systems. Nevertheless, a recent work emphasized the significance of the subgroup SO3 of SU3 for qutrit-based quantum computation, showing that any state of a qutrit could be obtained from a one-parameter family of states through the action of SO3 [21]. In this regard, one should not ignore the remarkable relationship between the groups SO3 and SU2. This motivates us to check whether the Solovay–Kitaev theorem is extendable to SO3 and possible to achieve the quantum speedup in three-level quantum systems, when equipped with orthogonal operators. In addition to that, once this question is resolved, one may know exactly whether the 3×3 orthogonal matrices also provide an algebraic structure suitable for efficient computation, such as geometric algebras or quaternions.In this paper, we show that the question is answered positively. That is, the orthogonal matrices play a role in three-level quantum systems, equivalent to what the unitaries play in standard quantum circuit framework. More precisely, we show that a version of the Solovay–Kitaev theorem is applicable to3×3 orthogonal matrices with unit determinant. Thus, we indicate the possibility of theoretically replacing the 2×2 unitaries in quantum computing by 3×3 orthogonals and qubits by qutrits. Using Cornwell’s two-to-one homomorphic map from the special unitary group SU2 to special orthogonal group SO3 [22], we prove the possibility of approximating any 3×3 orthogonal with unit determinant by a product of Olog41/ε elementary 3×3 orthogonals of unit determinants to an arbitrary accuracy ε. We further discuss how to find the sequence of appropriate elementary orthogonals, providing a version of Solovay–Kitaev algorithm in SO3.The remainder of the paper is organized as follows. In Section2, our version of the Solovay–Kitaev theorem for SO3 is proven. An approximation scheme for unit-determinant orthogonal matrices in accordance with this theorem and the standard Solovay–Kitaev algorithm is presented in Section 3. Computational experience is discussed in Section 4, and we discuss the implications of our work in Section 5 with several remarks on potential future works.


## 2. Solovay–Kitaev Theorem inSO3

### 2.1. Solovay–Kitaev Theorem

Recall the computational power in the circuit-gate framework is guaranteed by the Solovay–Kitaev theorem; its main focus is on approximating a2d×2d unitary matrix by basic quantum gates. A set of possible basic gates is referred to as an instruction set in the context of this theorem. Considering single qubit unitary gates, an instruction set G is a finite subset of SU2 such that G contains its own inverse and G is dense in SU2. For example, the set of gates H,H†,T,T† makes an instruction set for SU2, where H and T denote, respectively, Hadamard and phase gates in the circuit-gate framework. The set of all strings that can be made from G without using more than l elements is denoted by Gl. Now, the Solovay–Kitaev theorem for a d-qubit system can be stated as follows.Theorem 1 (Solovay–Kitaev).
LetG be an instruction set in SU2d. Then, for any ε>0, Gl provides an ε–net for SU2d where l=Odlog41/ε.The proof of this theorem is highly constructive, and the algorithmic steps of finding the elements in the instruction set that approximate a given element inSU2 can be found from its proof. A comprehensive version of proof can be found in [4]. An algorithmic version of the theorem with a procedure for finding those elements can be found in [23]. We now explore how a version of this theorem can be adapted to SO3. Primary motivation for this is the distance relations of the two groups, preserved by a homomorphism from SU2 onto SO3.


### 2.2. Distance Relations

The two-to-one homomorphic mappingρ from SU2 onto SO3 known today as Cornwell’s mapping is expressible in several ways [22], from which we adopt the following in [24]. An element U in SU2 is expressible as
(1)U=αβ−β¯α¯,where α,β∈ℂ and α2+β2=1 and its image is given by
(2)ρU=Reα2−β2Imα2−β2−2ReαβImα2−β2Reα2+β22Imαβ2Reαβ¯2Imαβ¯α2−β2.In order to measure the distances, as in the proof of the standard Solovay–Kitaev theorem, we too use the metric induced by the trace norm for consistency. It is customary to use the operator norm in quantum computation according to the matrix formulation of quantum mechanics. However, the standard proof of the Solovay–Kitaev theorem uses trace norm, as it helps to make the proof more comprehensive by incorporating a special property of the trace norm at some point. Since our intention is finding an analogous version inSO3, it is more appropriate to consider the trace norm for matrices in SO3 as well.Lemma2 illustrates how the mapping ρ preserves distances to an order Oε in SO3 with respect to trace norm.Lemma 2.
For any twoU,V∈SU2, if U−V<ε, then ρU−ρV<Oε.Proof.
Due to unitary invariance of the trace norm, it suffices to show thatI−ρU<Oε whenever I−U<ε. We use the fact that any element U in SU2 can be expressed as in equation (1) and the mapping ρ given by equation (2). Then,
(3)ρI−ρU=Re1−α2+β2Im1−α2−β22Reαβ−Im1−α2+β2Re1−α2−β2−2Imαβ−2Reαβ¯2Imαβ¯1−α2−β2,from which we derive
(4)ρI−ρU2=1−α2+β22+1−α2−β22+4αβ2+4αβ¯2+1−α2+β22.SupposingI−U<ε, it is not difficult to see that the left side of equation (4) is bounded by Oε2 as follows.I−U2=21−α2+β2<ε2. Accordingly, 1−α<ε/2 and β<ε/2. Also, α<ε/2+1. Therefore, 1−α2≤1−α2=1−α1+α<ε/2ε+22. Similarly, 1−α2+β2≤1−α2+β2<εε+2. Substituting these in equation (4), ρI−ρU2<3εε+22+2εε+222. Therefore, ρI−ρU<Oε.


### 2.3. Instruction Sets inSO3

In the context of single qubit unitary gates, an instruction setG is a finite subset of SU2 such that G contains its own inverse and G is dense in SU2. It is possible to adopt the same definition for instruction sets in SO3. Interestingly, the image of an instruction set in SU2 under the homomorphism ρ becomes an instruction set in SO3. Lemmata 3 and 4 prove this claim.Lemma 3.
LetX and Y be metric spaces, and let A be a dense subset of X. If f:X⟶Y is continuous and surjective, then fA is dense in Y.Proof.
LetK=f−1fA¯. Then, A⊆K and since f is continuous, K is closed. This implies A¯⊆K. On the other hand, since A is dense in X, A¯=X. Thus, K=X, and therefore, fA¯=fK=fX=Y.Lemma 4.
IfG is an instruction set in SU2, then ρG is an instruction set in SO3.Proof.
LetG be an instruction set in SU2. Then, ρG must contain its own inverse and is finite as ρ is a homomorphism. Since ρ is continuous and G is dense in SU2, by Lemma 3ρG is dense in SO3. Clearly, since ρ is a homomorphism, we have ρG=ρG. Therefore, ρG is an instruction set in SO3.


### 2.4. Solovay–Kitaev Theorem inSO3

With the results we derived above, it is now possible to establish a version of the Solovay–Kitaev theorem forSO3.Theorem 5.
LetG be an instruction set in SU2. Then, ρG is an instruction set for SO3 such that for any ε>0, ρGl provides an ε–net for SO3 where l=Olog41/ε.Proof.
From Lemma4, ρG is an instruction set. Let V∈SO3. Then, there exists some U∈SU2 such that V=ρU. The Solovay–Kitaev theorem guarantees the existence of U1,U2,⋯,Ul∈G such that U−U1U2⋯Ul<ε such that l=Olog41/ε. By Lemma 2, ρU−ρU1U2⋯Ul<Oε. Since ρ is a homomorphism, ρU1U2⋯Ul=ρU1ρU2⋯ρUl. That is, V−ρU1ρU2⋯ρUl<Oε, where l=Olog41/ε.


## 2.1. Solovay–Kitaev Theorem

Recall the computational power in the circuit-gate framework is guaranteed by the Solovay–Kitaev theorem; its main focus is on approximating a2d×2d unitary matrix by basic quantum gates. A set of possible basic gates is referred to as an instruction set in the context of this theorem. Considering single qubit unitary gates, an instruction set G is a finite subset of SU2 such that G contains its own inverse and G is dense in SU2. For example, the set of gates H,H†,T,T† makes an instruction set for SU2, where H and T denote, respectively, Hadamard and phase gates in the circuit-gate framework. The set of all strings that can be made from G without using more than l elements is denoted by Gl. Now, the Solovay–Kitaev theorem for a d-qubit system can be stated as follows.Theorem 1 (Solovay–Kitaev).
LetG be an instruction set in SU2d. Then, for any ε>0, Gl provides an ε–net for SU2d where l=Odlog41/ε.The proof of this theorem is highly constructive, and the algorithmic steps of finding the elements in the instruction set that approximate a given element inSU2 can be found from its proof. A comprehensive version of proof can be found in [4]. An algorithmic version of the theorem with a procedure for finding those elements can be found in [23]. We now explore how a version of this theorem can be adapted to SO3. Primary motivation for this is the distance relations of the two groups, preserved by a homomorphism from SU2 onto SO3.


## 2.2. Distance Relations

The two-to-one homomorphic mappingρ from SU2 onto SO3 known today as Cornwell’s mapping is expressible in several ways [22], from which we adopt the following in [24]. An element U in SU2 is expressible as
(1)U=αβ−β¯α¯,where α,β∈ℂ and α2+β2=1 and its image is given by
(2)ρU=Reα2−β2Imα2−β2−2ReαβImα2−β2Reα2+β22Imαβ2Reαβ¯2Imαβ¯α2−β2.In order to measure the distances, as in the proof of the standard Solovay–Kitaev theorem, we too use the metric induced by the trace norm for consistency. It is customary to use the operator norm in quantum computation according to the matrix formulation of quantum mechanics. However, the standard proof of the Solovay–Kitaev theorem uses trace norm, as it helps to make the proof more comprehensive by incorporating a special property of the trace norm at some point. Since our intention is finding an analogous version inSO3, it is more appropriate to consider the trace norm for matrices in SO3 as well.Lemma2 illustrates how the mapping ρ preserves distances to an order Oε in SO3 with respect to trace norm.Lemma 2.
For any twoU,V∈SU2, if U−V<ε, then ρU−ρV<Oε.Proof.
Due to unitary invariance of the trace norm, it suffices to show thatI−ρU<Oε whenever I−U<ε. We use the fact that any element U in SU2 can be expressed as in equation (1) and the mapping ρ given by equation (2). Then,
(3)ρI−ρU=Re1−α2+β2Im1−α2−β22Reαβ−Im1−α2+β2Re1−α2−β2−2Imαβ−2Reαβ¯2Imαβ¯1−α2−β2,from which we derive
(4)ρI−ρU2=1−α2+β22+1−α2−β22+4αβ2+4αβ¯2+1−α2+β22.SupposingI−U<ε, it is not difficult to see that the left side of equation (4) is bounded by Oε2 as follows.I−U2=21−α2+β2<ε2. Accordingly, 1−α<ε/2 and β<ε/2. Also, α<ε/2+1. Therefore, 1−α2≤1−α2=1−α1+α<ε/2ε+22. Similarly, 1−α2+β2≤1−α2+β2<εε+2. Substituting these in equation (4), ρI−ρU2<3εε+22+2εε+222. Therefore, ρI−ρU<Oε.


## 2.3. Instruction Sets inSO3

In the context of single qubit unitary gates, an instruction setG is a finite subset of SU2 such that G contains its own inverse and G is dense in SU2. It is possible to adopt the same definition for instruction sets in SO3. Interestingly, the image of an instruction set in SU2 under the homomorphism ρ becomes an instruction set in SO3. Lemmata 3 and 4 prove this claim.Lemma 3.
LetX and Y be metric spaces, and let A be a dense subset of X. If f:X⟶Y is continuous and surjective, then fA is dense in Y.Proof.
LetK=f−1fA¯. Then, A⊆K and since f is continuous, K is closed. This implies A¯⊆K. On the other hand, since A is dense in X, A¯=X. Thus, K=X, and therefore, fA¯=fK=fX=Y.Lemma 4.
IfG is an instruction set in SU2, then ρG is an instruction set in SO3.Proof.
LetG be an instruction set in SU2. Then, ρG must contain its own inverse and is finite as ρ is a homomorphism. Since ρ is continuous and G is dense in SU2, by Lemma 3ρG is dense in SO3. Clearly, since ρ is a homomorphism, we have ρG=ρG. Therefore, ρG is an instruction set in SO3.


## 2.4. Solovay–Kitaev Theorem inSO3

With the results we derived above, it is now possible to establish a version of the Solovay–Kitaev theorem forSO3.Theorem 5.
LetG be an instruction set in SU2. Then, ρG is an instruction set for SO3 such that for any ε>0, ρGl provides an ε–net for SO3 where l=Olog41/ε.Proof.
From Lemma4, ρG is an instruction set. Let V∈SO3. Then, there exists some U∈SU2 such that V=ρU. The Solovay–Kitaev theorem guarantees the existence of U1,U2,⋯,Ul∈G such that U−U1U2⋯Ul<ε such that l=Olog41/ε. By Lemma 2, ρU−ρU1U2⋯Ul<Oε. Since ρ is a homomorphism, ρU1U2⋯Ul=ρU1ρU2⋯ρUl. That is, V−ρU1ρU2⋯ρUl<Oε, where l=Olog41/ε.


## 3. Approximations inSO3

Now we describe how an arbitrary unit-determinant orthogonal matrix can be approximated byρG, where G is an instruction set in SU2. Recall the proof of the Solovay–Kitaev theorem is highly constructive; it provides essential ingredients for finding the sequence of elements from the instruction set approximating the given unitary to a given accuracy ε. As implied by Theorem 5, our algorithmic version for SO3 too is based on the steps in finding those elements as in the proof of the original theorem.For completion, we first describe the algorithm for finding the approximations inSU2. We follow the procedure given by Dawson and Nielsen [23] in this regard.


### 3.1. Solovay–Kitaev Algorithm

As described in [23], the Solovay–Kitaev algorithm is explainable using the following lemma.Lemma 6 [23].
SupposeV,W,V~, and W~ are unitaries such that V−V~,W−W~<Δ, and also I−V,I−W<δ. Then,
(5)VWV†W†−V~W~V~†W~†<8Δδ+4Δδ2+8Δ2+4Δ3+Δ4.The algorithm inSU2 can be expressed in pseudocode as follows.Pseudocode 1
function Solovay–Kitaev(GateU, depth n)if (n==0)Return Basic ApproximationUelseSetUn−1= Solovay–Kitaev(U,n−1)SetV,W= GC-Decompose(UUn−1†)SetVn−1= Solovay–Kitaev(V,n−1)SetWn−1= Solovay–Kitaev(W,n−1)ReturnUn=Vn−1Wn−1Vn−1†Wn−1†The algorithm is a function which takes two inputs:U is an arbitrary element in SU2 which we desire to approximate by G, and n a nonnegative integer which controls the accuracy of the approximation. This function returns sequence elements from an instruction set G in SU2 which approximates U to an accuracy of εn, a strictly decreasing function of n. The Solovay–Kitaev algorithm is recursive and the recursion terminates when n=0.
(6)ifn==0ReturnBasicApproximationU.In this step, we find anε0 approximation to U. To find such an approximation, we have to assure that we have constructed an ε0-net: a set containing elements from G such that for any unitary matrix we can find an ε0 approximation from it. Since ε0 is a constant and G is dense in SU2, we can build a gate net by enumerating and sorting a large number of elements from Gl0 for sufficiently large but fixed positive integer l0 and creating a search algorithm to find the closed approximation. If n≠0, then we find an εn−1 approximation to U:
(7)SetUn−1=Solovay–KitaevU,n−1.IfΔ~ is an εn approximation to Δ=UUn−1†, then by the unitary invariance of the norm,
(8)U−Δ~Un−1=UUn−1†−Δ~=Δ−Δ~<εn.Thus, finding anεn approximation to Δ with εn<εn−1allows us to find an improved approximation (i.e., εn<εn−1) to U. To find such an approximation, first we decompose Δ=UVW†V†, where U,V are unitaries with I−V,I−U<k1εn−1, where k1 is positive constant:
(9)SetV,W=GC−DecomposeUUn−1†.This decomposition is known as the balance group commutator. To find such a decomposition, we use the fact that any arbitrary unitary can be represented as a rotation in the Bloch sphere. IfΔ is a rotation by an angle θ about some axis n on the Bloch sphere, consider α satisfying
(10)sinθ2=2sin2α21−sin4α2,α=sin−11−cosθ/2424.Then, ifV~ is a rotation by α about the x axis and W~ is a rotation by α about the y axis, on the bloch sphere, then N=V~W~V~†W~† is conjugate to Δ (i.e., Δ=SNS†) for some unitary S. Since N and Δ are unitary matrices, they are diagonalizable; moreover, they have the same eigenvalues. Thus, by diagonalizing N and Δ, we find a diagonal matrix D and two unitary matrices SΔ and SN such that
(11)M=SΔDSΔ†,N=SNDSN†.Now, lettingS=SΔSN†, we have V=SV~S† and W=SW~S† satisfying
(12)Δ=UVW†V†.Also, for sufficiently smallεn−1, V and W satisfy
(13)I−V,I−W<k1εn−1for some positive constant k1.Now, we findεn−1 approximations to both V and W:
(14)SetVn−1=Solovay–KitaevV,n−1,SetVn−1=Solovay–KitaevV,n−1.By replacingΔ by εn−1 and δ by k1εn−1 in Lemma 6, the group commutator of Vn−1 and Wn−1 turns out to be a k2εn−13/2 approximation to Δ for some positive constant k2. Now, if 1/k22<εn−1, then k2εn−13/2<εn−1. Hence, εn=k2εn−13/2 provides an improved approximation for U. Accordingly, the value of ε0 is determined by this constant k2; i.e., for this construction to guarantee that ε0>ε1>⋯, the value of ε0 must be strictly less than 1/k22 (i.e., ε0<1/k22). This algorithm concludes by returning the sequences of elements in G that approximate the group commutator as well as Un−1.


### 3.2. Solovay–Kitaev Algorithm inSO3

In light of the algorithmic steps described, now it is possible to provide the algorithmic version forSO3 as follows.Pseudocode 2
function Solovay–Kitaev(S,depth n)SetU=SO3ToSU2SSetU~=SKU,nSetS~=SU2ToSO3S~ReturnS~This algorithm is a function which takes two inputs:S: an arbitrary element in SO3 which we intend to approximate and n: a nonnegative integer which controls the accuracy of the approximation. This function returns a sequence of elements from an instruction set ρG⊂SO3, where G is an instruction set in SU2, which approximates S to an accuracy of εn, where εn is a decreasing function of n, i.e, εn⟶0 as n⟶∞.
(15)SetU=SO3ToSU2S.In this step, we findU∈SU2 such that ρU=S, where ρ is the homomorphic mapping from SU2 to SO3, so that we can find a Solovay–Kitaev approximation for U in SU2 (SK.,. is the Solovay–Kitaev function in SU2):
(16)SetU~=SKU,n.Supposing that for a given depthm the SK function approximates any unitary matrix V∈SU2 to accuracy km, we find a kn approximation U~ to U. Next, we find ρU~:
(17)SetS~=SUToSO3S.By Lemma2, S~ turns out to be an εn=ckn approximation for S, for some positive constant c. Since U~ is a sequence of elements from G, there are U1,U2,⋯Un∈G such that U~=U1U2⋯Un. Then, S~=ρU~=ρU1U2⋯Un=ρU1ρU2⋯ρUn, because ρ is a homomorphism. Thus, S~ is a sequence of elements from ρG which approximates S to an accuracy εn. For a given depth m, km is approximation error associated with the Solovay–Kitaev approximations in SU2. Therefore, we can ensure that k0>k1>⋯, which implies ε0>ε2>⋯. Finally, this function returns a sequence of instructions from ρG which approximates S to an accuracy of kn.


## 3.1. Solovay–Kitaev Algorithm

As described in [23], the Solovay–Kitaev algorithm is explainable using the following lemma.Lemma 6 [23].
SupposeV,W,V~, and W~ are unitaries such that V−V~,W−W~<Δ, and also I−V,I−W<δ. Then,
(5)VWV†W†−V~W~V~†W~†<8Δδ+4Δδ2+8Δ2+4Δ3+Δ4.The algorithm inSU2 can be expressed in pseudocode as follows.Pseudocode 1
function Solovay–Kitaev(GateU, depth n)if (n==0)Return Basic ApproximationUelseSetUn−1= Solovay–Kitaev(U,n−1)SetV,W= GC-Decompose(UUn−1†)SetVn−1= Solovay–Kitaev(V,n−1)SetWn−1= Solovay–Kitaev(W,n−1)ReturnUn=Vn−1Wn−1Vn−1†Wn−1†The algorithm is a function which takes two inputs:U is an arbitrary element in SU2 which we desire to approximate by G, and n a nonnegative integer which controls the accuracy of the approximation. This function returns sequence elements from an instruction set G in SU2 which approximates U to an accuracy of εn, a strictly decreasing function of n. The Solovay–Kitaev algorithm is recursive and the recursion terminates when n=0.
(6)ifn==0ReturnBasicApproximationU.In this step, we find anε0 approximation to U. To find such an approximation, we have to assure that we have constructed an ε0-net: a set containing elements from G such that for any unitary matrix we can find an ε0 approximation from it. Since ε0 is a constant and G is dense in SU2, we can build a gate net by enumerating and sorting a large number of elements from Gl0 for sufficiently large but fixed positive integer l0 and creating a search algorithm to find the closed approximation. If n≠0, then we find an εn−1 approximation to U:
(7)SetUn−1=Solovay–KitaevU,n−1.IfΔ~ is an εn approximation to Δ=UUn−1†, then by the unitary invariance of the norm,
(8)U−Δ~Un−1=UUn−1†−Δ~=Δ−Δ~<εn.Thus, finding anεn approximation to Δ with εn<εn−1allows us to find an improved approximation (i.e., εn<εn−1) to U. To find such an approximation, first we decompose Δ=UVW†V†, where U,V are unitaries with I−V,I−U<k1εn−1, where k1 is positive constant:
(9)SetV,W=GC−DecomposeUUn−1†.This decomposition is known as the balance group commutator. To find such a decomposition, we use the fact that any arbitrary unitary can be represented as a rotation in the Bloch sphere. IfΔ is a rotation by an angle θ about some axis n on the Bloch sphere, consider α satisfying
(10)sinθ2=2sin2α21−sin4α2,α=sin−11−cosθ/2424.Then, ifV~ is a rotation by α about the x axis and W~ is a rotation by α about the y axis, on the bloch sphere, then N=V~W~V~†W~† is conjugate to Δ (i.e., Δ=SNS†) for some unitary S. Since N and Δ are unitary matrices, they are diagonalizable; moreover, they have the same eigenvalues. Thus, by diagonalizing N and Δ, we find a diagonal matrix D and two unitary matrices SΔ and SN such that
(11)M=SΔDSΔ†,N=SNDSN†.Now, lettingS=SΔSN†, we have V=SV~S† and W=SW~S† satisfying
(12)Δ=UVW†V†.Also, for sufficiently smallεn−1, V and W satisfy
(13)I−V,I−W<k1εn−1for some positive constant k1.Now, we findεn−1 approximations to both V and W:
(14)SetVn−1=Solovay–KitaevV,n−1,SetVn−1=Solovay–KitaevV,n−1.By replacingΔ by εn−1 and δ by k1εn−1 in Lemma 6, the group commutator of Vn−1 and Wn−1 turns out to be a k2εn−13/2 approximation to Δ for some positive constant k2. Now, if 1/k22<εn−1, then k2εn−13/2<εn−1. Hence, εn=k2εn−13/2 provides an improved approximation for U. Accordingly, the value of ε0 is determined by this constant k2; i.e., for this construction to guarantee that ε0>ε1>⋯, the value of ε0 must be strictly less than 1/k22 (i.e., ε0<1/k22). This algorithm concludes by returning the sequences of elements in G that approximate the group commutator as well as Un−1.


## 3.2. Solovay–Kitaev Algorithm inSO3

In light of the algorithmic steps described, now it is possible to provide the algorithmic version forSO3 as follows.Pseudocode 2
function Solovay–Kitaev(S,depth n)SetU=SO3ToSU2SSetU~=SKU,nSetS~=SU2ToSO3S~ReturnS~This algorithm is a function which takes two inputs:S: an arbitrary element in SO3 which we intend to approximate and n: a nonnegative integer which controls the accuracy of the approximation. This function returns a sequence of elements from an instruction set ρG⊂SO3, where G is an instruction set in SU2, which approximates S to an accuracy of εn, where εn is a decreasing function of n, i.e, εn⟶0 as n⟶∞.
(15)SetU=SO3ToSU2S.In this step, we findU∈SU2 such that ρU=S, where ρ is the homomorphic mapping from SU2 to SO3, so that we can find a Solovay–Kitaev approximation for U in SU2 (SK.,. is the Solovay–Kitaev function in SU2):
(16)SetU~=SKU,n.Supposing that for a given depthm the SK function approximates any unitary matrix V∈SU2 to accuracy km, we find a kn approximation U~ to U. Next, we find ρU~:
(17)SetS~=SUToSO3S.By Lemma2, S~ turns out to be an εn=ckn approximation for S, for some positive constant c. Since U~ is a sequence of elements from G, there are U1,U2,⋯Un∈G such that U~=U1U2⋯Un. Then, S~=ρU~=ρU1U2⋯Un=ρU1ρU2⋯ρUn, because ρ is a homomorphism. Thus, S~ is a sequence of elements from ρG which approximates S to an accuracy εn. For a given depth m, km is approximation error associated with the Solovay–Kitaev approximations in SU2. Therefore, we can ensure that k0>k1>⋯, which implies ε0>ε2>⋯. Finally, this function returns a sequence of instructions from ρG which approximates S to an accuracy of kn.


## 4. Computational Experience

One challenge encountered in the computation is thatρ−1 fails to exist as the map is not one to one. This however was overcome using the fact that for given A∈SO3 it is possible to find U∈SU2 such that ρU=A, for which the following construction was used. Any element in SO3 can be represented by a real number θ, the angle of rotation, and a rotation axis a=ax,ay,az, which is a 3-dimensional unit vector, denoted by Raθ. The corresponding matrix Raθ can be expressed explicitly by
(18)Raθ=I+sinθNa+1−cosθNa2,where
(19)Na=0−azayaz0−ax−ayax0.For a given rotational matrixRaθ, define
(20)U=cosθ2−iazsinθ2−aysinθ2−iaxsinθ2aysinθ2−iaxsinθ2cosθ2+iazsinθ2.One can verify thatU∈SU2 and ρU=Raθ. Therefore, for an element A∈SO3, in order to find an element U∈SU2 such that ρU=A, under this construction, we need to find a unit vector a∈ℝ3 and a real number θ such that Raθ=A.LetA∈SO3, and suppose A is the corresponding rotational matrix of Raθ (i.e., A=Raθ). If v is any vector parallel to a, then it must satisfy Av=v, because the rotation of v around the axis of rotation must result in a. Since A∈SO3, we can always find an eigenvalue A which is equal to 1, from which it immediately follows that a is an eigenvector which corresponds to the eigenvalue 1. So by diagonalizing A, we find the unit vector a′ which is parallel to each other a. Now, since both a and a′ are unit vectors, we must have a=a′ or a′=a. By equation (18), the trace of the matrix A reduces to TrA=1+2cosθ, which immediately results in θ=cos−1TrA−1/2. Now, by defining α∈ℝ such that α=θ and choosing the right sign for α to match the rotational axis a′ (i.e., aθ=a′α), we get Ra′θ=Raα=A.Accordingly, we implemented our algorithm inSO3 to find the Solovay–Kitaev approximates to several special unitary matrices. The computational experiment was conducted in accordance with the algorithmic steps mentioned and the bound was obeyed as in Theorem 5. We implemented with different instruction sets and the implementation with the instruction set S1,S2,S3,S1†,S2†,S3† in SU2 where
(21)S1=151+2i111−2i,S2=1512i2i1,S3=1512−21resulted in much shorter length for a givenε than the others. It would be an interesting future work to identify any classes or subgroups of matrices that can be approximated best by each instruction set, perhaps with a comparison of different instruction sets.


## 5. Discussion

Unconventional computing with different algebraic structures had been the topic of interest for a few previous works for which the primary motivation was quantum computing. Based on the fact that the circuit-gate framework of quantum computing relies on the Solovay–Kitaev theorem, we investigated the possibility of deriving a version of this theorem forSO3 on a three-level quantum system, indicating the potential of using orthogonal matrices for efficient computation.Three-level quantum systems and relevant operators had already been a topic of interest. In analogy with standard circuit-gate framework, it was customary to use the elements in the unitary groupSU3 as the operators in these systems. Despite the recent experimental achievements, theoretical bounds, capacity, and other related questions on three-level quantum systems were seldom explored. With our version of the Solovay–Kitaev theorem, it is now known that efficient computation is possible with the orthogonal subgroup SO3 of SU3. This is a noticeable distinction when compared with the subgroup SO2 of SU2. Being an Abelian group, it is impossible to perform Solovay–Kitaev type approximations on SO2. Thus, an instruction set in standard quantum computation enforces the inclusion of T (the phase gate), T2, or T†2, the nonorthogonal gates. However, the fault-tolerant implementation of the phase gate T is much more complicated than the orthogonal gates [25]. Therefore, quantum speedup only using orthogonals is beyond feasibility in standard circuit-gate framework, though desired. In contrast to this, as our results indicate, quantum speedup with orthogonals is theoretically feasible in a three-level quantum system.It is worthwhile to consider our version of the Solovay–Kitaev theorem in the context quantum compilation [26, 27] in which the conversion of a nonfault-tolerant circuit into a fault tolerant one is investigated. A recent paper introduced several efficient methods for quantum compilation using physical machine descriptions, which included one method based on the Solovay–Kitaev approximations [28]. Although compilation and optimization of three-level quantum circuits have been the subject of a few other works [19, 20, 29], none is based on the Solovay–Kitaev theorem. It would be an interesting future task to investigate whether efficient compilations are possible for a three-level system with orthogonals. This would be possible by constructing a Solovay–Kitaev-based compilation method analogous to the one in [28], for which our algorithm in Section 3.1 would be helpful.Our aim was particularly on exploring the approximation power of special orthogonal matrices. Therefore, we confined our study to a particular form of instruction sets inSO3; that is, the images of instruction sets in SU2. A closer inspection reveals that an arbitrary instruction set in SO3 behaves similarly, resulting in the same length for a given accuracy. Therefore, it is an immediate consequence of Theorem 5 that slightly different versions of the Solovay–Kitaev theorem and algorithm for SO3 can be established. However, the applicability of the Solovay–Kitaev theorem to other Lie groups than SO3 still remains a nontrivial and theoretically interesting topic, which has not been investigated in literature. It would be a potential future task to see if the theorem is extendable to those groups.



---

*Source: 2530609-2020-06-24.xml*