On an implementation of the Solovay-Kitaev algorithm
Abstract
Description
In quantum computation we are given a finite set of gates and we have to perform a desired operation as a product of them. The corresponding computational problem is approximating an arbitrary unitary as a product in a topological generating set of $SU(d)$. The problem is known to be solvable in time $polylog(1/ε)$ with product length $polylog(1/ε)$, where the implicit constants depend on the given generators. The existing algorithms solve the problem but they need a very slow and space consuming preparatory stage. This stage runs in time exponential in $d^2$ and requires memory of size exponential in $d^2$. In this paper we present methods which make the implementation of the existing algorithms easier. We present heuristic methods which make a time-length trade-off in the preparatory step. We decrease the running time and the used memory to polynomial in $d$ but the length of the products approximating the desired operations will increase (by a factor which depends on $d$). We also present a simple method which can be used for decomposing a unitary into a product of group commutators for $2<d<256$, which is an important part of the existing algorithm.
10 pages, published on the 10th Rhine Workshop on Computer Algebra
10 pages, published on the 10th Rhine Workshop on Computer Algebra