Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Solovay-Kitaev Algorithm
The Solovay-Kitaev theorem states that an arbitrary single-qubit gate may be constructed approximately to arbitrary accuracy with a sequence of length of gates from a fixed and finite set. Here, we demonstrate an algorithm that gives a sequence of length with ., assuming a generating set of the Hadamard gate , octant phase gate and its inverse . The Solovay-Kitaev theorem is, of course, far more general, and for algorithms for general cases, see the references at the end of this document.
ϵ
n≃
α
Log
1
ϵ
n≃
α
Log
1
ϵ
α≃3.97
H
T
-1
T
Solovay | Reprents an elementary generator |
TheSolovay | The matrix representation an elementary generator |
SolovayChains | Returns the list of all possible sequence of elementary generators |
SolovayKitae | Implements the Solovay-Kitaev algorithm |
Functions related to the Solovay-Kitaev algorithm.
Load the package.
In[1]:=
<<Solovay`
Some Utility Functions
Here are some functions that are used in the algorithm or may be useful to analyse the algorithm.
BalancedCommutator
BalancedCommutator
In[85]:=
?
 | GroupCommutator |
Out[85]=
Symbol | |
GroupCommutator[a, b] returns the group commutator of a and b; that is, a**b**Inverse[a]**Inverse[b]. | |
In[26]:=
new=
[ThePauli[1],ThePauli[2]];new//MatrixForm
 | GroupCommutator |
Out[27]//MatrixForm=
-1 | 0 |
0 | -1 |
In[31]:=
Let[NonCommutative,a,b]
In[32]:=
| GroupCommutator |
Out[32]=
ab
-1
a
-1
b
In[33]:=
?
| BalancedCommutator |
Out[33]=
Symbol | |
BalancedCommuator[u] returns the group commuator decomposition of 2 x 2 unitary matrix u; that is, a pair of two group elements a and b such that u = GroupCommutator[a, b]. | |
In[34]:=
mat=
0.9689945920647197`-0.18643612090113915` | 0.15825427836029116`+0.035307743526686745` |
-0.15825427836029105`+0.035307743526662085` | 0.9689945920646759`+0.18643612090129802` |
Out[34]=
{{0.968995-0.186436,0.158254+0.0353077},{-0.158254+0.0353077,0.968995+0.186436}}
In[35]:=
MatrixForm/@{uu,vv}=
[mat]
[uu,vv]-mat//Chop//MatrixForm
 | BalancedCommutator |
| GroupCommutator |
::notuni
Out[35]=
,
0.935676-0.267733 | -0.0843935-0.213791 |
0.0843935-0.213791 | 0.935676+0.267733 |
0.935676-0.0576092 | -0.293097+0.187844 |
0.293097+0.187844 | 0.935676+0.0576092 |
Out[36]//MatrixForm=
0 | 0 |
0 | 0 |
———
In[18]:=
MatrixForm/@
[One[2]]
 | BalancedCommutator |
Out[18]=
,
1 | 0 |
0 | 1 |
1 | 0 |
0 | 1 |
———
In[19]:=
Domat=TheEulerRotation@RandomReal[{-1,1}Pi,3];{V,W}=
[mat];gc=Chop@Chop@
[V,W];Echo[mat-gc//Chop//MatrixForm],10
 | BalancedCommutator |
 | GroupCommutator |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
»
0 | 0 |
0 | 0 |
———
This is one of the dangerous case.
In[20]:=
mat={{0.6176764285966168`+0.19302865391947965`,0.6924904732390966`+0.31886158877364695`},{-0.6924904732390966`+0.31886158877364695`,0.6176764285966168`-0.19302865391947965`}};mat//MatrixForm
Out[21]//MatrixForm=
0.617676+0.193029 | 0.69249+0.318862 |
-0.69249+0.318862 | 0.617676-0.193029 |
In[22]:=
{V,W}=
[mat];gc=Chop@Chop@
[V,W];mat-gc//Chop//MatrixForm
| BalancedCommutator |
| GroupCommutator |
Out[24]//MatrixForm=
0 | 0 |
0 | 0 |
———
In[25]:=
mat=TheRotation[2Pi/3,2];mat//N//MatrixForm{V,W}=
[N@mat];gc=Chop@Chop@
[V,W];mat-gc//Chop//MatrixForm
| BalancedCommutator |
| GroupCommutator |
Out[26]//MatrixForm=
0.5 | -0.866025 |
0.866025 | 0.5 |
Out[29]//MatrixForm=
0 | 0 |
0 | 0 |
Solovay, TheSolovay
Solovay, TheSolovay
For efficiency, each element in any operator sequence is represented by a certain prefixed index. Functions Solovay and TheSolovay are to convert the indices to human readable operators and matrices, respectively.
In[2]:=
?
| Solovay |
Out[2]=
Symbol | |
Solovay[k] represents the element associated with index k in the densely generating set H, T, -1 T | |
In[3]:=
?TheSolovay
Out[3]=
Symbol | |
TheSolovay[k] returns the matrix representation of Solovay[k]. | |
Consider the following sequence, where the generators are represented by some prefixed indices.
Convert the indices to human readable operators.
Convert the indices or operators to human readable matrices.
Exhaustive Search
Here is a list of all possible sequences of generators of length 4. The sequences are represented by indices for efficiency.
Convert the indices in the sequences to human readable operator symbols.
This is a small utility function that examine the length of the sequence.
Applying the above utility function confirms that the previously constructed sequences are of length 4.
Convert the sequences to human readable matrices.
Solovay-Kitaev Algorithm
Here, an implementation of the Solovay-Kitaev algorithm is demonstrated.
Function SolovayKitaev
Function SolovayKitaev
Take a unitary matrix you like to approximate.
Now, try to find a better approximation using two levels of recursion.
In the above result, the actual sequence is store in variable chain.
For convenience and efficiency, the matrix corresponding to the sequence is also given in variable out.
Check how good the approximate result is.
More details of the sequence
More details of the sequence
Consider the initial state.
This is the final state achieved by the ideal gate.
The initial and final states are displayed on the Bloch sphere.
Convert the gates in the sequence to 2×2 matrices.
Get the sequence of quantum states that results from applying the gates to the initial state.
Check the accuracy of the final state.
Finally, display the sequence of the quantum states on the Bloch sphere. The balls in blue, red and yellow are the initial, ideal finial, and approximate final states, respectively.
Higher-level recursions
Higher-level recursions
Try to find an approximation using two levels of recursion.
Now, increases the number of levels to three.
With four levels of recursion, the sequence gets longer and the accuracy is improved.