An implementation of the Kitaev-Solovay algorithm

The Kitaev-Solovay algorithm lets us efficiently approximate an arbitray single-qubit gate by a sequence of gates from a given instruction set. By instruction set we just mean a small set of universal single-qubit gates, for example the Hadamard gate 'H' and the /8 gate 'T'. The algorithm is described in detail in this review article.

Source archive: sk-0.1.tar.gz

Win32 binary: sk-0.1_w32.zip

The sources have been successfully compiled with g++ 3.3.5 and with MS Visual C++ 7.1. The Win32 binary contains a pre-compiled version of the Python module which may or may not work on your system.

To compile the Python module you'll need the latest Boost C++ libraries. Installing them is easier than it sounds.

Overview

The main part of the whole Solovay-Kitaev thing is the initial epsilon-net. This is encapsulated by the Net class which allows you generate, save and load nets, and of course, run the algorithm. The main idea behind it is to divide an SU(2) parameter space up into tiles. Each instruction sequence that is generated is associated with nearby tiles, and then when it's time to find an initial approximation to some operator U we just search through the sequences in U's tile.

When generating a Net for the first time you need to provide a 'tile width'. The less instruction sequences in a tile the better so you don't want the tiles too big. On the otherhand you don't want the tiles too small otherwise it's possible that won't have any instruction sequences in it. One of the main problems with the current implementation is that it uses a stupid SU(2) paramaterization and choosing a good tile width is difficult, but see the TODO section below for details.

The examples should be enough to get started with, and the accompanying class documentation should be enough to go further.

TODO

If I were trying to improve this code, these are some of the things I'd do (in order of priority):

• SU(2) can be parameterized by a 4D unit vector (t,x,y,z) such that . So the tiling is just division of into equally sized hypercubes. This is stupid because the intersection of the unit sphere with these hypercubes varies enormously so no matter what the tile width is choosen to be the amount of 'net points' associated with each tile also varies enormously. A much better idea would be to divide the unit 3-sphere up into equal areas using polar coordinates.

• Currently every single net point is saved. And although the Net is clever enough to not follow something up by its inverse or exceed a gate's order it isn't clever enough to know things like . The size of the Net's that are generated is enormous, so even saving and loading them can take a long time (on my aged laptop de-allocating the memory actually takes a few seconds). So whenever we add a Net point we could check to see that it doesn't duplicate an existing one, or even limit ourselves to one net points per tile or something. This means it would take a little longer to generate the nets, but the save / load routines that are already written so generation only needs to be done once.

• When a Net is being generated or loaded from a file, the memory for each Net::knot (a point in the net) is allocated seperately. It would be a lot quicker to allocate a big array all at once, particularly when loading the net from a file when we already know exactly how many there are.

• I'm sure there is more.

---