[Feature Request] Adding Solovay-Kitaev Pass

[ZakW-1qbit]

Hello,

I'm actually not sure if this is the right place to put this, but I'm interested in determining whether a Solova-Kitaev type algorithm would be of interest to this project. For non-quantum experts, this is basically a classical algorithm to transform an input circuit into some pre-determined (usually finite) gate-set, such as Clifford+T, which is really useful when trying to construct fault-tolerant circuits. I've been looking online for a while, and there aren't too many implementations of this. Qiskit recently added a SK pass to their system, (although it is rather slow), and I don't believe that Q# has an implementation. Since everything compiles down to QIR, and this is really more of a compiler pass, I was thinking that this might be useful to the community, especially as people move away from NISQ type algorithms.

I currently work at 1QBit, and we need such an implementation for one of the projects we're working on. We could develop this internally, but I personally think this is something that the entire community will eventually require. Since it's something the community needs and the algorithm is freely available, I think it will be better maintained and more useful if its done in an open source project like QAT. Assuming I get my manager's ok, I'd be happy to contribute to this, but while I have decent programming experience, I'm more of a scientist, and my code often reflects that.

Basically, is this the right place for an algorithm like this, and is the project interested in helping me implement it as well? If you have a better idea of where in the software stack something like this should go, I'd also appreciate it if you could direct me there.

Thank you for your time.

[swernli]

Hi @ZakW-1qbit! Thanks for expressing interest. I do think it would be interesting to design out how Solovay-Kitaev could work as a pass. However, I wonder if it might be trying to generalize something that can be accomplished in a more straightforward, specific way. For example, while implementing Solovay-Kitaev would allow for dynamic generation of decompositions from gate set A to gate set B defined at compile time, usually when targeting a specific profile (like QAT is designed to do) the set of target gates is known ahead of time and the gates used in the input language are also well known. This could allow for running the algorithm to generate decompositions once, then treating those as a library that gets linked into the submitted code to provide alternate definitions of gates that are not natively supported. So rather than something that runs as a pass on every program, this would be run once per front-end + back-end combination to create the library that gets used each time thereafter. For one way that linking can work, see Replacement Linking in the QAT documentation (though note that is one area we are considering simplifying the workflow and relying on more traditional linking mechanisms). Perhaps what this points to is a utility that can perform ahead of time Solovay-Kitaev analysis to produce libraries that are used to link against QIR programs to change the gate set?

[ZakW-1qbit]

Thanks for responding @swernli. I'll admit, I'm not too familiar with the entire QAT ecosystem, so there's always the possibility that something more straightforward might work. As far as the replacement linking goes, that certainly sounds promising, as SK type algorithms do generally replace particular gates with some sequence from the target gate set, so doing this replacement as a library might be possible. However, the particular replacement rules for SK don't only depend on the two gate sets, they also depend on an error parameter, as generally each replacement isn't exact, and depends on how close you need to get to the target unitary. I suppose it's possible to generate this replacement for several different errors and create a library for each of them, but I think in general it will be needed to have the ability to run this for on a circuit for a given set of parameters.

I will admit, that I'm thinking of using this as an intermediate step in a larger ecosystem, where part of the output is to just get a circuit that's in a particular gate set. I imagine that once fault-tolerant devices become more prevalent, each device might depend on a different code, and there would then be another transform to translate what's being done logically to what's actually necessary on the physical device. I know that I personally actually want to get this Clifford+T gate circuit so that we can then do some additional transformations to it that are needed for a particular implementations of the surface code.

[swernli]

Ah, that's an interesting element that I hadn't considered: including different decompositions based on noise tolerances. I can see how that would lead to this being more of a live/adaptive process that incorporates the latest data from hardware calibration and user preferences. I agree with you that this could be an amazing piece of a larger ecosystem. I can imagine something that takes in a user program in QIR along with their error preferences, calculates the SK decompositions from the gates used by that program and information about the target, and then produces either a) the fully updated program with the replacement already completed or b) the library QIR with the decompositions generated that the program should be linked against. I think that tool is specific enough to exist outside of QAT, but could be part of a pipeline that operates on the program along with QAT and other tools.

One recommendation I could make is checking out PyQIR if you haven't already. The latest versions have updated the APIs to make it easier to write a workflow in Python (or Rust) that parses QIR, analyzes and modifies it, and then re-emits the program. That might be a good option for starting in on processing QIR without having to jump into the deep end of processing LLVM as a pass in C++!

[ZakW-1qbit]

Yeah, even given a physical error on the underlying qubits, eventually with error correction you should be able to get arbitrarily small logical errors, and thus the error of any single gate should depend on the length of the circuit you want to simulate. As such, the user will need a lot of freedom in choosing what error threshold their decomposition uses so that they use as small of a circuit as possible. Its definitely a lot different from current NISQy type applications, where the error rate of a particular system is so key to what you can implement.

Thanks for sending me to PyQIR, I'll definitely check it out. I will admit, that I was a bit intimidated by trying to dive into LLVM's, and this might be a nice place to create a Rust program that does the decomposition without having to learn everything. It should definitely make it easier to get what I want up and running in a relatively short period of time.

I don't disagree that this would be a fairly general purpose tool, albeit one only needed in specific circumstances. I originally wanted to add this to QAT, as I didn't think I'd be able to manage a full repository in the QIR-alliance myself and thought that QAT would be a nice eventual home for this program. However, if you think it would be a good first step to get something up and running in another repository, and maybe eventually add it later, that's certainly something I can work towards. The end goal is to transform a user circuit into something that can be run on a fault-tolerant device, and I can imagine all of that would make up it's own repository. I imagine that eventually there will be a pipeline from user generated code, something that converts the code to 2-qubit Cliffords + arbitrary single qubit gates, this SK algorithm to convert to Clifford+T, something which turns the code into a form that can be run on a chosen surface code, and finally something which translates this surface-code level procedure into actual circuits on the physical qubits. I was thinking that all of this would eventually be in the QAT repository, since most of this should be some form of QIR, but if that isn't the goal of QAT I definitely understand. I'm doubt I'd want to be responsible for all of this, but simply implementing SK should be a good start, especially if I can program it in Rust.

[swernli]

Makes sense. I think being able to write SK as a Rust-based tool that processes QIR is a great place to start. Then we can circle back and re-evaluate whether it makes sense to directly incorporate that as an LLVM pass in QAT or keep it as a stand alone tool that can be part of a QIR processing pipeline in conjunction with QAT and other tools in the ecosystem. I think QAT is a starting place to organize LLVM passes written in C++, but it can be just one piece of the tools and transformations performed on a QIR program.

I'll close this issue for now and we can revisit when appropriate.