Fast implementations of quantum algorithms.

Just like a traditional programming language, a quantum programme is an ordered list of instructions. In traditional computers, the hardware understands only machine language where the instructions are elementary logic gates such as AND, NOT or ADD. Any other programming language must be translated (compiled) into a device level language. The language of quantum computing is also a list of instructions: quantum logic gates that must be applied to qubits in a certain order. A standard notation is the circuit notation and below is an example.

Each line represents a single qubit, so above we have 6 qubits. Quantum logic gates acting on a single qubit are shown with a square box on a particular line. The are many different types of quantum logic gate and so they are labelled: above is built using gates known as S, T and H. Qubits also need to interact via two-qubit quantum logic gates shown with a vertical join between lines.

Time runs from left to right and dictates the order of execution. When two gates are drawn with the same left/right positioning, then it doesn’t matter what order they are performed in, and they can even be performed in parallel.

Given a circuit, there will be many other equivalent circuits (they perform the same computation, or at least approximately the same) but with a different arrangement and number of logic gates. Quantum computers are all about speed and so it is crucial that we find circuits with the fewest number of gates and the lowest depth (the depth is the time from first to the last gate). This optimisation task is called the gate-synthesis or compiling problem. It is another theory area where is it essential we have fast software tools before we can build fast quantum computers.

When building fault-tolerant quantum computers, the quantum logic gates we can perform come from a very limited gate set that depends on the architecture of the hardware. Usually, this is the Clifford + T gate set (the circuit above is built from these gates). There are many logic gates outside this set, but they must be built up from these building blocks. Furthermore, the T-gate is typically much more expensive because it is implemented via magic state distillation. So often the gate-synthesis comes down to reducing the number of T gates rather than the total number of gates.

Problems in gate synthesis come in two flavours: exact and inexact. In exact synthesis, we are able to exactly implement the desired computation with a finite size circuit. In an inexact circuit, the desired computation can only be achieved approximated with the available quantum logic gates. However, this approximation can increase the accuracy of the approximation by using deeper and deeper circuits.

This is really a new area of work for me, but we have some recent results that are really exciting and I plan to work on more on this topic.

The exact CNOT+T synthesis problem

In 2016, I came across a fascinating paper by Matt Amy and Mike Mosca. They investigated the problem of optimally solving an important compiling problem that had a lot of mathematical overlap with the distillation problem I had been working on. We applied some of their ideas in the setting of magic state distillation, but also found some new methods relevant to synthesis. These techniques efficiently solve the optimisation problem using at most a quadratic number of gates, whereas the best previous scaling as cubic. So there is potential for a significant speed-up of quantum computers. These first insights got squeezed into our long synthillation paper and can be found in Section 4 of Phys. Rev. A 95 022316 (2017). This paper has just a small section on the synthesis problem and no software implementations of these ideas.

When Luke Heyfron started a PhD with me, we decided to dive into a more comprehensive project focused on the CNOT+T synthesis problem. Over the first year of Luke’s PhD, he developed C++ implementations of some existing compilers and also came up with a new one that we call TODD. The results are really promising. We found that our newer software consistently generated circuits with fewer T gates (usually over 30% fewer). You can read more about this in our preprint https://arxiv.org/abs/1712.01557.

Random compiling

Bizarrely, randomness can be useful in inexact synthesis! We use randomness by making decisions about what logic gates to implement by effectively rolling dice. This process doesn’t lead to a completely random circuit. Rather we create a list of circuits that all behave approximately the same, and use randomness to select between them. This helps us combat coherence in noise processes and surprisingly enables us to use smaller circuits to achieve the same of precision. The headline result is that this technique doubles the speed of quantum computers (with no change to hardware). Read more here Phys. Rev. A. 95 042306 (2017).