2006/06/08 by Attila Nagy, Attila B. Nagy, Nagy, Attila B.
Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #Spectral Theory in Mathematical Physics #Stochastic processes and financial applications #advanced mathematical theories #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0606077
10 pages, published on the 10th Rhine Workshop on Computer Algebra
arxiv created 2006/06/08 · openalex publication_date 2006/06/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 d2 and requires memory of size exponential in d2. 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.