ska-0.1
(An implementation of the Solovay-Kitaev Algorithm)

About

ska-0.1 is an experimental C implementation of the Solovay-Kitaev Algorithm [SK] with an interface to the GAP computational algebra system. The program was written mainly to try out the ideas described in [Nagy] , and was made public in the hope that other people might also find it useful. Another implementation of the Solovay-Kitaev Algorithm can be found here.

Authors

Attila Nagy and Csaba Schneider of the Computer and Automation Research Institute, Budapest.

Download

The implementation can be downloaded by clicking here.

Installation

If you unpack the tgz file, then you obtain a GAP package. Click here to find out how to install GAP packages. The package contains two C programs sk and lattice wich will have to be compiled using the Makefile in the root directory. (There are also Makefiles in the directories src/sk and src/lattice, but you don't have to worry about those at this stage.) The targets specified in the Makefile are as follows.

make all
make all or make (with no target) compiles the programs sk and lattice. The latter needs the libraries gmp and ntl.

make sk
compiles the program sk

make lattice
compiles the program lattice. It uses the libraries gmp and ntl, so make sure that they are available on your system. You might also have to edit the file src/lattice/Makefile to specify how the header files can be accessed.

make clean_sk
cleans the binary files corresponding to program sk.

make clean_lattice
cleans the binary files corresponding to program lattice.

make clean
cleans all binary files.

make tgz
creates a tarball.

After successful compilation, the executables should appear in the directory bin/.

Using the stand-alone programs

sk [-g] [-v] [-o outputfile] inputfile
The optional arguments are:

-g: Prints output in GAP format.
-v: Prints detailed output.
-o outputfile: Prints output into outputfile (stdout is used if this option is missing).
The format of the input file is as follows. It starts with 2 numbers: the first is the dimension of the matrices, and the second is the number of matrices in the basis. Then the entries of the basis elements are listed, and finally the entries of the elements of the matrix to be expressed is listed. The matrix elements must be separated by white spaces and have to be standard decimal complex numbers, such as -0.32323+1.443242*I. For example, see the file examples/exs1_sk.

The output of the program sk is a list of numbers showing how one must multiply the basis elements in order to approximate the input matrix. Negative numbers indicate inverses.

Using the -v option, one can obtain a detailed output that contains more information.


lattice [-o outputfile] inputfile

The input file starts with two numbers: the dimension and the generator number of a matrix group. Then the entries of the generators are listed separated by whites spaces. Each such entry must be a rational number. Example input files can be found in the examples/ directory.


The program outputs a matrix whose rows generate a lattice invariant under the input matrices. If the output fájl is not specified then the output is printed to the fájl inputfile.out.

The GAP functions

The GAP interface contains a number of functions; see the code for details. Here are the most important two.


InvariantLatticeC( G )

G is a rational matrix group. Invokes the program lattice above and outputs a matrix whose rows generate a lattice invariant under G. The GAP variable __lattice_exec (starts with two underline characters) must contain the path of the executable program lattice. Note that there is a built-in GAP function InvariantLattice.


SolovayKitaev( base, mat )

base is a list of matrices, and mat is a matrix which is to be approximated as a product in base. The output is a list of numbers showing how one must multiply the basis elements in order to approximate the input matrix. Negative numbers indicate inverses. The GAP variable __sk_exec (starts with two underline characters) must contain the path of the executable program sk.


Acknowledgement

This work was supported by the IST-2001-37559 program (RESQ) of the European Union. See the SZTAKI Quantum Computing Pages for related work.

Contact

Please let us know if you use this code. We can be contacted at nagy@math.bme.hu or csaba,schneider@sztaki.hu.

References

[SK] Christopher M. Dawson, Michael A. Nielsen. The Solovay-Kitaev algorithm. arxiv.org/abs/quant-ph/0505030.

[Nagy] Attila B. Nagy. On an implementation of the Solovay-Kitaev Algorithm. Proceedings of the 10th Rhine Workshop on Computer Algebra, 2006.