dorsal/arxiv
View SchemaOn an implementation of the Solovay-Kitaev algorithm
| Authors | Attila B. Nagy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606077 |
| URL | https://arxiv.org/abs/quant-ph/0606077 |
Abstract
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/\epsilon)$ with product length $polylog(1/\epsilon)$, 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.
{
"annotation_id": "7b0efea3-0953-439c-b99f-a5333dd664b5",
"date_created": "2026-03-02T18:02:27.359000Z",
"date_modified": "2026-03-02T18:02:27.359000Z",
"file_hash": "bea659237594617f04e277f2cfd82015a8a26a66432942334be0466eb3440c1e",
"private": false,
"record": {
"abstract": "In quantum computation we are given a finite set of gates and we have to\nperform a desired operation as a product of them. The corresponding\ncomputational problem is approximating an arbitrary unitary as a product in a\ntopological generating set of $SU(d)$. The problem is known to be solvable in\ntime $polylog(1/\\epsilon)$ with product length $polylog(1/\\epsilon)$, where the\nimplicit constants depend on the given generators. The existing algorithms\nsolve the problem but they need a very slow and space consuming preparatory\nstage. This stage runs in time exponential in $d^2$ and requires memory of size\nexponential in $d^2$. In this paper we present methods which make the\nimplementation of the existing algorithms easier. We present heuristic methods\nwhich make a time-length trade-off in the preparatory step. We decrease the\nrunning time and the used memory to polynomial in $d$ but the length of the\nproducts approximating the desired operations will increase (by a factor which\ndepends on $d$). We also present a simple method which can be used for\ndecomposing a unitary into a product of group commutators for $2\u003cd\u003c256$, which\nis an important part of the existing algorithm.",
"arxiv_id": "quant-ph/0606077",
"authors": [
"Attila B. Nagy"
],
"categories": [
"quant-ph"
],
"title": "On an implementation of the Solovay-Kitaev algorithm",
"url": "https://arxiv.org/abs/quant-ph/0606077"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cf61555f-4ffa-4d77-86b8-ab96f4f193dd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}