←Return to chapter

3.1. Quantum compilers cannot do it alone

We have convinced ourselves in the previous chapter that quantum programs must interface with our established classical infrastructure, and should rather be understood as an interleaved execution of both classical and quantum operations. The obvious question that thus poses itself is

How do we equip quantum compilers to deal with classical operations?

The simplest solution is to adopt the extended quantum circuit formalism with support for classically-controlled operations, as we have introduced it in the previous chapter. Using this representation, the basic types available for computation are the qubit and the classical bit. We can also at that point introduce purely classical operations on bits, for instance to compute boolean logic on measurements outcomes, such as “if both the first AND the second measurement outcomes are 1, then …”.

However, the circuit model is inherently designed with the no-cloning principle in mind: specifically, with the assumption that at any one time, there are exactly $n$ (for some fixed value of $n$) resources available for computation. This for example means that in the following program

These are run-of-the-mill classical compiler problems! One might at first hope that the set of overlapping problems between classical and quantum compilers is manageably small. After all, in all the use cases we have covered so far, the amount of classical compute was very minimal, limiting itself to conditionals and loops based on simple boolean expressions. Surely the full-blown powers of a classical compiler are not required!

You bet.

Scientists have shown no lack of imagination in this field – and so have found very compelling use cases for complex classical computations within quantum programs. To drive this point home, let us consider the concrete example of quantum error correction.

The quantum error correction use case #

Error correcting protocols do as their name suggests: they detect whenever data was subjected to errors and thus modified in an unexpected way. They then attempt to recover the intended valid state. In the classical world, such schemes are employed whenever the hardware is not reliable enough: this is hardly the case for computations themselves, but is widespread in communications (e.g. within the TCP/IP protocol for the internet Eddy, 2022Wesley Eddy. 2022. Transmission Control Protocol (TCP). (August 2022). Retrieved as RFC 9293 from https://www.rfc-editor.org/info/rfc9293), or for memory and storage in critical applications.

For quantum hardware, no-one expects to be able to manipulate qubits without introducing errors for a very long time², and so, error correction will be absolutely everywhere, as soon as our quantum computers will have managed to implement such protocols.

A sketch of quantum error correction goes roughly as follows: the data that would be stored on $k$ qubits is instead encoded in a redundant way on a larger number $n > k$ of qubits. Thus when errors occur on a subset of the $n$ qubits, the data can be restored using the qubits that have not been corrupted. Before errors can be corrected they must be detected. To this end, we first add fresh ancilla qubits to the program. Through smartly designed interactions with the data qubits, the ancilla qubits pick up the errors from the data. When we subsequently perform measurements on the ancilla qubits, these errors result in modified outcomes, called the error “syndrome”.

The challenging bit comes next: from a run of syndrome measurements, one must infer the most likely errors – a step known as “syndrome decoding”. This is a purely classical maximum likelihood problem that requires a non-trivial amount of compute to resolve. For small problem instances, all possible input syndromes can be tabled and the outputs precomputed – in which case the problem at runtime is reduced to fast table lookups. However, the higher the fault tolerance we require, the more qubits must be used in the encodings, and so invariably, the problem quickly becomes very demanding computationally.

Meanwhile, these “cycles” of error detection and correction are under strict latency constraints: idling qubits waiting for corrections to be applied will accumulate new errors that must themselves be corrected – in other words, we must be capable of detecting and correcting for errors faster than they are being introduced. The entire error correction cycle just described can be summarised by the following diagram:

The decoding time is a crucial factor in determining the overall cycle time, and thus the clock rate of fault tolerant quantum hardware. Consider for example a 32-qubit Toric code Kitaev, 2003A.Yu. Kitaev. 2003. Fault-tolerant quantum computation by anyons. Annals of Physics 303, 1 (January 2003, 2--30). doi: 10.1016/S0003-4916(02)00018-0, one of the most well-studied quantum error correcting codes. Without going into the details of the code itself, we can use the C++ implementation made available by the MQT toolkit Burgho., 2021Lukas Burgholzer and Robert Wille. 2021. Advanced Equivalence Checking for Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40, 9 (Septempter 2021, 1810--1824). doi: 10.1109/tcad.2020.3032630 to study the decoder performance for this code.

Consider first a “naive” compilation of the decoder – the kind of program that we could hope to get from a quantum compiler that “understands” classical operations but only implements optimisations directly relevant to quantum computations. Such a compiler does not currently exist, but the decoder being a C++ program, we can approximate what the compiled binary would look like by turning off all optimisations from an established classical compiler³.

The runtime averaged over 1000 runs of the decoder is $0.73\pm0.06\,ms$. This is within the latency requirements of certain trapped ion architectures Ryan-A., 2021C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown, T. M. Gatterman, S. K. Halit, K. Gilmore, J. A. Gerber, B. Neyenhuis, D. Hayes and R. P. Stutz. 2021. Realization of Real-Time Fault-Tolerant Quantum Error Correction. Physical Review X 11, 4 (December 2021, 041058). doi: 10.1103/physrevx.11.041058, but far beyond the sub-microsecond regime that will be required to make error correction a reality on superconduction-based quantum computers Carrer., 2024Almudena Carrera Vazquez, Caroline Tornow, Diego Ristè, Stefan Woerner, Maika Takita and Daniel J. Egger. 2024. Combining quantum processors with real-time classical communication. Nature 636, 8041 (November 2024, 75--79). doi: 10.1038/s41586-024-08178-2. this can be contrasted with the program output by the same compiler, but with optimisations activated: the average runtime is reduced by a factor close to 10x to $0.078\pm0.004\,ms$ – still a factor 100x away from the required performance on superconductors, but huge gains nonetheless! The details of the experiment with all build flags, the hardware used and how to reproduce the results are available here.

There is no hope to obtain these types of speedups without an in-depth understanding of classical hardware and battle tested implementations for every optimisation pass under the sun – in short, the full thrust of a modern state of the art compiler such as clang or gcc.

These observations will hopefully leave the reader convinced that in order to compile and realise the kind of hybrid quantum classical programs that we expect will become the norm in the field, quantum compilers will need to embrace and encompass the full breadth and depth of classical compilers. This leaves us with no choice but to fully transform and integrate the existing quantum tooling and quantum optimisation research into the established compilers ecosystem. What this means exactly is the subject of the rest of this chapter.

←Return to chapter