←Return to chapter

2.1. A new compilation regime

We have introduced quantum compilation by drawing an analogy with the well-developed field of classical compilers. However, what makes quantum compilation so incredibly exciting is the novel directions it is taking the field in. Of the many new challenges that are arising, let us discuss here three that together form the core motivation for this work.

Large variations in architecture #

A first distinguishing characteristic of current quantum computing developments is the vast differences between proposed hardware architectures. Unlike classical computing where silicon-based transistors have become the definitive physical foundation for all electronic chips, the search for the most scalable and reliable technology for quantum computing is ongoing – and doubtless one of the most burning questions for the nascent industry. This introduces an incredible variety of compilation problems.

Quantum hardware designs are dictated on the one hand by the choice of the quantum physical system used to encode the data of the computation, and by the technology that serves to control and manipulate the system on the other. Suggestions for the former include charged ions Kielpi., 2002D. Kielpinski, C. Monroe and D. J. Wineland. 2002. Architecture for a large-scale ion-trap quantum computer. Nature 417, 6890 (June 2002, 709--711). doi: 10.1038/nature00784 T. Pel., 1995J. I. Cirac, T. Pellizzari and P. Zoller. 1995. Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model. Physical Review Letters 75, 21 (November 1995, 3788--3791). doi: 10.1103/PhysRevLett.75.3788, neutral atoms Jaksch, 2000D. Jaksch, J. I. Cirac, P. Zoller, S. L. Rolston, R. Côté and M. D. Lukin. 2000. Fast Quantum Gates for Neutral Atoms. Physical Review Letters 85, 10 (Septempter 2000, 2208--2211). doi: 10.1103/physrevlett.85.2208 Deutsch, 2000Ivan H. Deutsch, Gavin K. Brennen and Poul S. Jessen. 2000. Quantum Computing with Neutral Atoms in an Optical Lattice. Fortschritte der Physik 48, 9–11 (Septempter 2000, 925--943). doi: 10.1002/1521-3978(200009)48:9/11<925::aid-prop925>3.0.co;2-a, photons 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, transmons Blais, 2007Alexandre Blais, Jay Gambetta, A. Wallraff, D. I. Schuster, S. M. Girvin, M. H. Devoret and R. J. Schoelkopf. 2007. Quantum-information processing with circuit quantum electrodynamics. Physical Review A 75, 3 (March 2007, 032329). doi: 10.1103/physreva.75.032329 and even Majorana 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 particles. The control systems that drive the desired operations on these particles is then built using some jolly mixture of lasers, magnetic fields, microwaves, dilution fridges etc.

Each of these combinations result in different tradeoffs: some will render a certain computation particularly easy; others hold the promise to scale well to large systems but are very error-prone and unreliable; others still achieve high fidelities at the expense of slow operations.

From the perspective of a compiler engineer, this means that we must equip quantum compilers to handle a large variety of hardware primitives, multiple optimisation goals and hardware specific program constraints. This is a huge challenge that traditional compilation is ill-equipped to handle.

A comparison of machine code for different architectures illustrates well the difference between the quantum and classical worlds. Classical CPUs are dominated by two architectures x86, used mainly by Intel and AMD, and ARM, used by a wide range of desktop and mobile chip manufacturers¹.

mov eax, 5        ; Load 5 into EAX
add eax, 3        ; Add 3 to EAX
mov [result], eax ; Store the result in memory
 

ldr r0, =5        ; Load 5 into R0
add r0, r0, #3    ; Add 3 to R0
ldr r1, =result   ; Load address of result
str r0, [r1]      ; Store the result in memory

There are noticeable differences between the two architectures, mostly around variable naming conventions, as well as explicit memory loads ldr and stores str instructions in the case of ARM, which in x86 are handled implicitly by mov. This simplistic example naturally ignores some of the more fine-grained considerations that can make translations hard in certain edge cases. A discussion of these can be found in Ford, 2021Blake W. Ford, Apan Qasem, Jelena Tesic and Ziliang Zong. 2021. Migrating Software from x86 to ARM Architecture: An Instruction Prediction Approach. In 2021 IEEE International Conference on Networking, Architecture and Storage (NAS), October 2021. IEEE, 1--6. doi: 10.1109/NAS51552.2021.9605443. However, overall the instructions and capabilities that the two platforms are broadly equivalent, as is confirmed by the existence of translation tools such as Apple Rosetta.

Let us contrast this with the difference between two quantum architectures. Consider on the one hand an architecture that can natively perform CX and H gates on qubits (e.g. superconducting qubits, ion traps, etc) and on the other a platform based on photons and optical components.

h q[0];
cz q[0],q[1];

bs.h(5*pi/2, pi, pi, 2*pi) m[0], m[1];
bs.h m[2], m[3];
perm([2, 1, 3, 0]) m[1], m[2], m[3], m[4];
barrier m[0], m[1], m[2], m[3], m[4], m[5];
bs.h(1.910633) m[0], m[1];
bs.h(1.910633) m[2], m[3];
bs.h(1.910633) m[4], m[5];
perm([1, 0]) m[2], m[3];
bs.h m[3], m[4];
perm([3, 0, 1, 2]) m[1], m[2], m[3], m[4];

On the left is a quantum circuit as expressed in the OpenQASM2 standard Cross, 2017Andrew W. Cross, Lev S. Bishop, John A. Smolin and Jay M. Gambetta. 2017. Open Quantum Assembly Language. arXiv: 1707.03429 [quant-ph]. The right hand side is the equivalent linear optics circuit computed by Perceval Heurtel, 2023Nicolas Heurtel, Andreas Fyrillas, Gré Gliniasty, Raphaë Le Bihan, Sé Malherbe, Marceau Pailhas, Eric Bertasi, Boris Bourdoncle, Pierre-Emmanuel Emeriau, Rawad Mezher, Luka Music, Nadia Belabas, Benoît Valiron, Pascale Senellart, Shane Mansfield and Jean Senellart. 2023. Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing. Quantum 7 (February 2023, 931). doi: 10.22331/q-2023-02-21-931, expressed in an OpenQASM2-like format. The conversion is by no means straight-forward! Some of the challenges include encoding qubits into multiple photon modes and mapping quantum operations to an optically realizable procedure made of optical components and measurements Felice, 2023Giovanni de Felice and Bob Coecke. 2023. Quantum Linear Optics via String Diagrams. In Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022. Open Publishing Association, 83-100. doi: 10.4204/EPTCS.394.6.

Other architectures, such as neutral atoms, may broadly support qubit-based operations but might not offer control over individual qubits, and instead require any operations to be applied in parallel to large groups of qubits Bluvst., 2022Dolev Bluvstein, Harry Levine, Giulia Semeghini, Tout T. Wang, Sepehr Ebadi, Marcin Kalinowski, Alexander Keesling, Nishad Maskara, Hannes Pichler, Markus Greiner, Vladan Vuletić and Mikhail D. Lukin. 2022. A quantum processor based on coherent transport of entangled atom arrays. Nature 604, 7906 (April 2022, 451--456). doi: 10.1038/s41586-022-04592-6. Finally, it is to be expected that error correcting codes that individual platforms will introduce to reduce error rates at the hardware level will introduce further constraints and new instruction sets yet again.

It is worthwhile to note that current trends in the classical world are also pushing compilers towards more heterogenous architectures that may include GPUs, FPGAs and other accelerators. This has led to significant changes in the design of current compilers, which we will touch upon later. Nonetheless, this shift has so far mostly “limited” itself to new forms of parallelism and the introduction of more specialised instruction sets, rather than a fundamental redesign of existing tools and computing paradigms. The breadth of technologies and trade-offs that quantum compilers must face have for the time being no equivalent in the classical world.

Asymmetric computational resources #

A second exciting paradigm shift in compilation that quantum is driving forward is cross-compilation. A common assumption in compilation is that the program is executed on the same machine (or at least the same architecture) that it was compiled on. By contrast, in cross-compilation the compiler and the compiled binary program run on different machines, possibly with different architectures. An instance of this would be using a recent MacOS ARM machine to create a binary program for a PC running Windows on an Intel chip. While this is a supported feature in most modern compilers, such tasks are the exception rather than the norm and are often laborious to get to work well in practice.

The situation is very different for quantum computing. Quantum computational resources are so limited that native compilation, in which the program is compiled and run on the same machine, is unfeasible – and will remain so for the foreseeable future². When we put the possibility of pure-quantum compilation aside, what we are left with is a purely classical cross-compilation problem, the output of which happens to be destined to run on a quantum computer.

Cross-compilation presents significant challenges. As quantum programs grow in size and complexity, debugging and verifying their correctness without access to the target hardware becomes increasingly difficult Rovara, 2024Damian Rovara, Lukas Burgholzer and Robert Wille. 2024. A Framework for Debugging Quantum Programs. arXiv: 2412.12269 [quant-ph], as we hit the limits of what can be simulated classically. Quantum simulation is a vibrant research area that has been and will continue to be the subject of theses (e.g. Flanni., 2020Stuart Flannigan. 2020. The application of quantum simulation to topological and open many-body systems Azad, 2024Fariha Azad. 2024. Tensor networks for classical andquantum simulation of open and closedquantum systems. (January 2024)) in its own right.

On the flip side, using classical hardware for quantum program compilation comes with a giant opportunity for compilers: the classical computational resources available to the compiler are many orders of magnitude larger (and cheaper!) than on the hardware that the compiled program is destined to. We can today execute tens to hundreds of billions of operations per second (GFLOPS) on desktop computers, scaling all the way up to the “exascale”, i.e. $10^{15}$ FLOPS, for the largest supercomputers Dongar., 2024Strohmaier, E., Simon, H., Meuer, H. Dongarra. 2024. TOP500 List. (November 2024). Retrieved on 30/12/2024 from https://top500.org/lists/top500/list/2024/11/. Quantum hardware on the other hand will not be executing programs with sizes beyond 1000 error-corrected gates, or 10,000 physical gates, for another three years – that is believing the most optimistic roadmaps in the industry IBM, 2024 IBM. 2024. Expanding the IBM Quantum roadmap to anticipate the future of quantum-centric supercomputing. Retrieved on 30/12/2024 from https://www.ibm.com/quantum/blog/ibm-quantum-roadmap-2025 Quanti., 2024 Quantinuum. 2024. Quantinuum Unveils Accelerated Roadmap to Achieve Universal, Fully Fault-Tolerant Quantum Computing by 2030. Retrieved on 30/12/2024 from https://www.quantinuum.com/press-releases/quantinuum-unveils-accelerated-roadmap-to-achieve-universal-fault-tolerant-quantum-computing-by-2030.

It is expected that even a few thousand quantum gates will suffice to solve problems that our largest supercomputers struggle with. Meanwhile, every gate that must be performed comes at a high cost: it may fail, introduce errors or simply take a long time to complete. It therefore behooves us to use all the classical resources at our disposal to reduce quantum operations to a minimum. Due to the stringent hardware limitations

Given the stringent hardware limitations all near term architectures are expected to face, quantum compilation must evolve into cross-compilers that are able to utilize the full power of classical hardware available to them; doing so will push the boundaries of what is possible with quantum computing just a bit further – in a field where every marginal gain may unlock new applications.

The confluence of classical and quantum compilation #

TODO: rewrite this section

Finally, quantum compilation also stands in front of some momentous engineering challenges. Until recently, the great majority of research efforts in the field were focused on the compilation and optimisation of quantum programs expressed as quantum circuits – more on these in section XY. This formalism has its roots in quantum information theory, the field that gave birth to quantum computing. It makes for an ideal framework to develop the theory as well as optimisation techniques. However it does not include any of the fundaments of compiler and programming language design that make classical software engineering as compostable and scalable as it is today. For example there is no concept of subroutine or function calls; neither can a program execution branch or loop based on runtime values. This makes code reuse impossible, resulting in huge program sizes and unsurmountable challenges for scaling up compilation to problems of real world interest.

The community is thus moving away from circuit-based representations to incorporate learnings from the decades of experience that have been gathered in computer science. Many of the tools and software that were originally developed for the classical community are now being adopted and adapted to the specificities of quantum. We are thus finding ourselves at the confluence of two fascinating fields, heralding great future developments.

←Return to chapter