### Quantum compilers cannot do it alone

←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 nn (for some fixed value of n nn) resources available for computation. This for example means that in the following program

{ "qubits": [{ "id": 0, "numChildren": 1 }, { "id": 1 }], "operations": [ { "gate": "Measure", "isMeasurement": true, "controls": [{ "qId": 0 }], "targets": [{ "type": 1, "qId": 0, "cId": 0 }] }, { "gate": "X", "targets": [{ "qId": 1 }] }, { "gate": "Measure", "isMeasurement": true, "controls": [{ "qId": 1 }], "targets": [{ "type": 1, "qId": 0, "cId": 0 }] }, { "gate": "correction-q1", "targets": [], "isConditional": true, "controls": [ { "type": 1, "qId": 0, "cId": 0 } ], "children": [ { "gate": "X", "targets": [{ "qId": 0 }], "conditionalRender": 2 } ] } ] }
it would be impossible to append a gate controlled on the first measurement outcome to this circuit, as that value was overwritten on the classical wire by the second measurement. The solution could be to introduce1 a new, fresh classical wire for each measurement and avoid overwriting outcomes. However, there are also many other ways to break this wires-based representation: suppose you have an operation with one input and two outputs, such as a copy operation x↦(x, x)x \mapsto (x,x)x↦(x, x). We would need two wires for the output, but the input would only provide us with one… We now have to start creating addition wires ahead of time for this purpose and solve memory allocation problems to decide which wire should be given to which operation.

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 time2, 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 k k qubits is instead encoded in a redundant way on a larger number n>k n > kn>k of qubits. Thus when errors occur on a subset of the n nn 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 compiler3.

The runtime averaged over 1000 runs of the decoder is 0.73±0.06 m s 0.73\pm0.06\,ms0.73±0.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±0.004 m s 0.078\pm0.004\,ms0.078±0.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.

1. Or as we would say in programming parlance: to allocate. ↩︎

2. At the risk of stoking controversy, we should at this point acknowledge the commendable efforts of scientists chasing the Majorana particle Sau, 2010Jay D. Sau, Roman M. Lutchyn, Sumanta Tewari and S. Das Sarma. 2010. Generic New Platform for Topological Quantum Computation Using Semiconductor Heterostructures. Physical Review Letters 104, 4 (January 2010, 040502). doi: 10.1103/physrevlett.104.040502 Haaf, 2024Sebastiaan L. D. ten Haaf, Qingzhen Wang, A. Mert Bozkurt, Chun-Xiao Liu, Ivan Kulesh, Philip Kim, Di Xiao, Candice Thomas, Michael J. Manfra, Tom Dvir, Michael Wimmer and Srijit Goswami. 2024. A two-site Kitaev chain in a two-dimensional electron gas. Nature 630, 8016 (June 2024, 329--334). doi: 10.1038/s41586-024-07434-9 Mourik, 2012V. Mourik, K. Zuo, S. M. Frolov, S. R. Plissard, E. P. A. M. Bakkers and L. P. Kouwenhoven. 2012. Signatures of Majorana Fermions in Hybrid Superconductor-Semiconductor Nanowire Devices. Science 336, 6084 (May 2012, 1003--1007). doi: 10.1126/science.1222360. The topological quantum computers these would enable are to my knowledge the only quantum architecture proposed that would do away with error correction. ↩︎

3. Here we are using `Apple clang v15.0.0`, running macOS 14.7 on an Apple M3 Max chip. ↩︎

←Return to chapter