# Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations

The Solovay-Kitaev theorem shows that "this approximation can be made surprisingly efficient, thereby justifying that quantum computers need only implement a finite number of gates to gain the full power of quantum computation".

For a given unitary matrix quantum circuit $$V$$, how to decompose it into a series of shortest possible elementary quantum gates is a fundamental problem in quantum information processing tasks such as quantum computing and quantum simulation. Currently available methods include machine learning, circuit structure search, Solovay-Kitaev algorithm, and so on.

My question is:

Is there programming projects that implement the decomposisiton? Which is the most practical one?

I have found some Python modules/classes that would be helpful: e.g.

But I'm not very familiar with these Quantum Programming Tools, Quantum Programming Tools(Chinese article)

More recommendation? Any help would be appreciated.

First off, the question itself is disparate. You need some version of the Solovay-Kitaev theorem for optimizing a sub-circuit that acts on a single qubit, and you can also use it for two or three qubits. Moreover, the original Solovay-Kitaev theorem is for completely general gate sets, while there are now nearly optimal single-qubit algorithms for special gate sets, in particular Ross-Selinger for the popular Clifford+T gate set.

Circuit optimization for many qubits is a very different scene, except in that you need to know how to play one key on a piano on the way to playing all 88 of them. For comparison, circuit optimization for a few classical bits is trivial, but it looks intractable even for log(n) input bits, never mind for n input bits (where even checking whether two circuits do the same thing is NP-hard). Quantum circuit optimization for many qubits suffers from the same diseases and possibly worse diseases. In both the classical and quantum cases, general circuit optimization invites ad hoc algorithms that you can always try for any purpose, for example machine learning with neural nets.

There is also a big difference between making tools vs using them. They are both worthwhile programming projects, because the tools have to come from somewhere. To make a new tool, you don't necessarily need a comprehensive QC platform such as Qiskit; you can often get pretty far with Python or (say) Sage.

To expand on that last point, I would certainly applaud a programming project to implement and refine my new Solovay-Kitaev-type algorithm. It probably wouldn't be hot-off-the-press quantum engineering, but it could be good as quantum computer science for its own sake. It's true that my paper hasn't yet been published in a journal, but (a) that isn't always real verification either, and (b) I have explained it to various people. Whenever someone implements an algorithm, then I think that that counts as a step towards verifying that it works.

This certainly depends on what one is attempting to do, ie the algorithm or unitary that one is attempting to implement, and the target basis state (along with understanding precision thresholds and gate limitations).

There are a variety of projects on github and the larger web implementing variations of SK, eg; alternatively Qiskit includes qsd.py which is an implementation of https://arxiv.org/abs/quant-ph/0406176 for arbitrary unitaries, with 2x2's and 4x4's being rather trivial. But this is a bit above the Solovay-Kitaev limit.

The recent https://arxiv.org/abs/2306.13158 has improved the Solovay-Kitaev limit quite a bit, but has yet to be verified in peer review and I don't believe has a published implementation.

Other ongoing compiling projects and examples do exist, but depends on the level and type one is looking for.

It has been a long time (>4 years) since the last time I looked at this code, but I implemented a working version of the Solovay-Kitaev algorithm back then.

You will be able to find it in https://gitlab.com/cerfacs/qtoolkit.

A few notes:

• It might not work anymore, it has been more than 4 years.
• All the methods are commented and explained, so you can use this as a way to understand the implementation and re-implement yourself.
• The code license is a little bit unusual, read it before using the code.
• The whole package depends on a (very) old version of Qiskit, but it seems like I am not using it in the Solovay-Kitaev code. You'll have to check that.