←Return to chapter

2.4. Quantum compilers cannot do it alone

We have (hopefully!) by now convinced our readership 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 in the previous section. 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 measurement 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

in which two measurements write to the same classical bit, it would be impossible to append a gate controlled on the first measurement outcome after the $Z$ gate, as that value was overwritten on the classical wire by the second measurement. The solution could be to introduce¹ 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 \mapsto (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 additional 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 computation 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!

Unfortunately (and as usual), 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 is 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.

No one expects to be able to manipulate matter-based qubits without introducing errors for a very long time. Photons, on the other hand, are prone to data losses throuh absorption and can only be entangled using complex and noisy schemes such as the Knill–Laflamme–Milburn protocol Knill, 2001E. Knill, R. Laflamme and G. J. Milburn. 2001. A scheme for efficient quantum computation with linear optics. Nature 409, 6816 (January 2001, 46--52). doi: 10.1038/35051009². Simply put, it is safe to assume that error correction will be found everywhere – as soon as our quantum computers manage 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 computations 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 – for error correction to be workable, 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 all compiler optimisations enabled: 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 of obtaining 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.

To make matters worse, such classical computations are bound to move to dedicated accelerators that require specialised compilation, such as GPUs and FPGAs, for the most time-critical subroutines: quantum error decoding using GPUs is already well-developed Bausch, 2024Johannes Bausch, Andrew W. Senior, Francisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, George Holland, Dvir Kafri, Juan Atalaya, Craig Gidney, Demis Hassabis, Sergio Boixo, Hartmut Neven and Pushmeet Kohli. 2024. Learning high-accuracy error decoding for quantum processors. Nature 635, 8040 (November 2024, 834--840). doi: 10.1038/s41586-024-08148-8 Cao, 2023Hanyan Cao, Feng Pan, Yijia Wang and Pan Zhang. 2023. qecGPT: decoding Quantum Error-correcting Codes with Generative Pre-trained Transformers. arXiv: 2307.09025 [quant-ph] and more esoteric platforms FPGAs Overwa., 2022Ramon W. J. Overwater, Masoud Babaie and Fabio Sebastiano. 2022. Neural-Network Decoders for Quantum Error Correction Using Surface Codes: A Space Exploration of the Hardware Cost-Performance Tradeoffs. IEEE Transactions on Quantum Engineering 3 (1--19). doi: 10.1109/tqe.2022.3174017 Meinerz, 2022Kai Meinerz, Chae-Yeun Park and Simon Trebst. 2022. Scalable Neural Decoder for Topological Surface Codes. Physical Review Letters 128, 8 (February 2022, 080505). doi: 10.1103/physrevlett.128.080505, superconducting circuits Ueno, 2021Yosuke Ueno, Masaaki Kondo, Masamitsu Tanaka, Yasunari Suzuki and Yutaka Tabuchi. 2021. QECOOL: On-Line Quantum Error Correction with a Superconducting Decoder for Surface Code. In 2021 58th ACM/IEEE Design Automation Conference (DAC), December 2021. IEEE, 451--456. doi: 10.1109/dac18074.2021.9586326 and compute-in-memory architectures Wang, 2024Hao Wang, Erjia Xiao, Songhuan He, Zhongyi Ni, Lingfeng Zhang, Xiaokun Zhan, Yifei Cui, Jinguo Liu, Cheng Wang, Zhongrui Wang and Renjing Xu. 2024. CIM-Based Parallel Fully FFNN Surface Code High-Level Decoder for Quantum Error Correction. arXiv: 2411.18090 [cs.AR] are being actively studied.

These observations should 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 compiler ecosystem. What this means exactly is the subject of the rest of this chapter.

A new quantum programming paradigm? #

We have seen it – quantum circuits are very limited in their expressiveness. They are well suited to presenting sequences of purely quantum operations and how the computation is parallelised across qubits, but they quickly become limiting once both quantum and classical data types are mixed and any type of control flow (conditionals, loops, function calls, etc.) is introduced.

How users express programs in the front end has deep implications for the kind of computations that the compiler must be capable of reasoning about and, hence, for the compiler’s architecture. The great merging of classical and quantum compilers is the perfect opportunity to reconcile program representations and integrate the learnings from decades of classical programming language research into quantum computing.

There have been several trailblazing initiatives to formalise quantum programming and create dedicated languages, such as QCL Ömer, 2000Bernhard Ömer. 2000. Quantum Programming in QCL. (January 2000). Retrieved from http://tph.tuwien.ac.at/ oemer/doc/quprog.pdf, Quipper Green, 2013Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger and Benoît Valiron. 2013. Quipper: a scalable quantum programming language. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2013, New York, NY, USA. Association for Computing Machinery, 333--342. doi: 10.1145/2491956.2462177 Rios, 2018Francisco Rios and Peter Selinger. 2018. A Categorical Model for a Quantum Circuit Description Language (Extended Abstract). Electronic Proceedings in Theoretical Computer Science 266 (February 2018, 164--178). doi: 10.4204/eptcs.266.11 Fu, 2023Peng Fu, Kohei Kishida, Neil J. Ross and Peter Selinger. 2023. Proto-Quipper with Dynamic Lifting. Proceedings of the ACM on Programming Languages 7, POPL (January 2023, 309--334). doi: 10.1145/3571204, Q# Micros., 2024 Microsoft. 2024. Introduction to the quantum programming language Q#. Retrieved on 31/12/2024 from https://learn.microsoft.com/en-us/azure/quantum/qsharp-overview and Silq Bichsel, 2020Benjamin Bichsel, Maximilian Baader, Timon Gehr and Martin Vechev. 2020. Silq: a high-level quantum language with safe uncomputation and intuitive semantics. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2020. ACM, 286--300. doi: 10.1145/3385412.3386007. Their adoption in the quantum ecosystem have so far remained limited, overshadowed by the popularity of python-based APIs for quantum circuit-based representations, as offered by Qiskit Javadi., 2024Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson and Jay M. Gambetta. 2024. Quantum computing with Qiskit. arXiv: 2405.08810 [quant-ph], Pennylane Bergho., 2022Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang and Nathan Killoran. 2022. PennyLane: Automatic differentiation of hybrid quantum-classical computations. arXiv: 1811.04968 [quant-ph] and Cirq Cirq D., 2024 Cirq Developers. 2024. Cirq. There is, as a result, a justified dose of scepticism in the quantum community on how well the ideas from classical programming really translate to quantum.

It is thus all the more notable that we are seeing a new generation of quantum programming tooling being developed Koch, 2024Mark Koch, Alan Lawrence, Kartik Singhal, Seyon Sivarajah and Ross Duncan. 2024. GUPPY: Pythonic Quantum-Classical Programming. (January 2024). Retrieved (talk recording) from https://www.youtube.com/live/D8esZrt7ogk?feature=shared&t=31448 Ittah, 2024David Ittah, Ali Asadi, Erick Ochoa Lopez, Sergei Mironov, Samuel Banning, Romain Moyard, Mai Jacob Peng and Josh Izaac. 2024. Catalyst: a Python JIT compiler for auto-differentiable hybrid quantum programs. Journal of Open Source Software 9, 99 (July 2024, 6720). doi: 10.21105/joss.06720 CUDA-Q., 2024 CUDA-Q Developers. 2024. CUDA-Q Documentation. Retrieved on 31/12/24 from https://nvidia.github.io/cuda-quantum/latest/index.html, driven by the need to write more expressive programs for the improving hardware (as we have been discussing), as well as for performance reasons, to scale quantum compilation to large scale Ittah, 2022David Ittah, Thomas Häner, Vadym Kliuchnikov and Torsten Hoefler. 2022. QIRO: A Static Single Assignment-based Quantum Program Representation for Optimization. ACM Transactions on Quantum Computing 3, 3 (June 2022, 1--32). doi: 10.1145/3491247, accelerate quantum simulations Ittah, 2024David Ittah, Ali Asadi, Erick Ochoa Lopez, Sergei Mironov, Samuel Banning, Romain Moyard, Mai Jacob Peng and Josh Izaac. 2024. Catalyst: a Python JIT compiler for auto-differentiable hybrid quantum programs. Journal of Open Source Software 9, 99 (July 2024, 6720). doi: 10.21105/joss.06720 and integrate with classical high-performance computing (HPC) NVIDIA, 2024 NVIDIA. 2024. NVIDIA Accelerates Quantum Computing Centers Worldwide With CUDA-Q Platform. Retrieved on 31/12/2024 from https://investor.nvidia.com/news/press-release-details/2024/NVIDIA-Accelerates-Quantum-Computing-Centers-Worldwide-With-CUDA-Q-Platform/default.aspx.

The history of programming is, first and foremost, a masterclass in constructing abstractions. Many of the higher-level primitives, that have proven invaluable classically, solve problems that we expect to encounter very soon in our hybrid programs – when we have not already. Examples include

• structured control flow to simplify reasoning about branching in quantum-classical hybrid programs,
• type systems to encode program logic and catch errors at compile time – this is particularly important for quantum programs as there is no graceful way of handling runtime errors on quantum hardware: by the time the error has been propagated to the caller, all quantum data stored on qubits is probably corrupted and lost,
• memory management such as reference counting and data ownership models. Current hardware follows a static memory model, in which the number of available qubits is fixed, and every operation acts on a set of qubits assigned at compile time. This becomes impossible to keep track of in instances such as qubit allocations within loops with an unknown number of iterations at compile time. It thus becomes necessary to manage qubits dynamically, just like classical memory.

To facilitate such a large swath of abstractions, the first step quantum compilers must take is to make a distinction between the language frontend and the intermediate representation (IR) that the compiler uses to reason about the program and perform optimisations. This will be the topic of chapter 3. The graph-based IR that we introduce in that chapter will then form the foundation for the new quantum compilation techniques that will be developed throughout the remainder of the thesis.

←Return to chapter