←Return to chapter

3.4. Review of quantum compiler optimisations

Much of the foundations of classical computer science relies on boolean logic and discrete mathematics Lehman, 2017Eric Lehman, F. Thomson Leighton and Albert R. Meyer. 2017. Mathematics for Computer Science. Samurai Media Limited. This is in some regards a poor man’s maths, as much of the structure that comes with continuous infinite mathematical objects is lost along the way when discretised. Quantum computing on the other hand encompasses the whole breadth of quantum physical system evolution, with the underlying mathematics steeped in the theory of Hilbert spaces and Lie groups¹.

A direct consequence of the rich mathematics of quantum computations is the flourishing of an entire field of research dedicated to quantum-specific compiler optimisations Karupp., 2025Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson and Johnson P. Thomas. 2025. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions. Quantum Reports 7, 1 (January 2025, 2). doi: 10.3390/quantum7010002. Using all the assumptions and theory of quantum physics to design smart optimisations is the strength of these techniques, but also their weakness: in the face of rising hybrid classical-quantum computations, it is a priority that the performant algorithms that have been developed for this purpose be adapted to handle intermingled classical computations.

In this section, we will pass in review the main optimisation techniques – and closely related, the representation of quantum computations they use respectively – that have established themselves, with a particular focus on how they intersect with classical compiler design and how they generalise to work on quantum programs expressed in an IR such as minIR.

Cost function #

A key point to settle first when discussing quantum optimisations is what cost function it is we are “optimising”. Unlike much of classical compiler research, which can rely on an established set of hardware targets and benchmark programs to use as optimisation objective, there is as of yet no settled answer on the “right” quantum metric that must be optimised.

Most work can however be clustered in one of two buckets: the cost measure of a quantum program is either designed to approximate the amount of noise (i.e. errors) that would be introduced by current and near-term hardware, or it models the resource requirements for the program execution on a more distant large scale device, with the assumption that all hardware errors will be suppressed using error correction Karupp., 2025Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson and Johnson P. Thomas. 2025. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions. Quantum Reports 7, 1 (January 2025, 2). doi: 10.3390/quantum7010002.

In many current architectures, the major challenge is to achieve high accuracy on entangling operations, i.e. quantum gates that make two or more qubits interact Acharya, 2024Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Joonho Lee, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrà, James Manyika, Leigh S. Martin, Orion Martin, Steven Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Murphy Yuezhen Niu, Thomas E. O’Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, John Redding, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Travis Weidel, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu and Nicholas Zobrist. 2024. Quantum error correction below the surface code threshold. Nature (December 2024). doi: 10.1038/s41586-024-08449-y Pino, 2021J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson and B. Neyenhuis. 2021. Demonstration of the trapped-ion quantum CCD computer architecture. Nature 592, 7853 (April 2021, 209--213). doi: 10.1038/s41586-021-03318-4 Koch, 2007Jens Koch, Terri M. Yu, Jay Gambetta, A. A. Houck, D. I. Schuster, J. Majer, Alexandre Blais, M. H. Devoret, S. M. Girvin and R. J. Schoelkopf. 2007. Charge-insensitive qubit design derived from the Cooper pair box. Physical Review A 76, 4 (October 2007, 042319). doi: 10.1103/PhysRevA.76.042319 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. While experimental realisations of many-qubit interactions have been demonstrated Erhard, 2019Alexander Erhard, Joel J. Wallman, Lukas Postler, Michael Meth, Roman Stricker, Esteban A. Martinez, Philipp Schindler, Thomas Monz, Joseph Emerson and Rainer Blatt. 2019. Characterizing large-scale quantum computers via cycle benchmarking. Nature Communications 10, 1 (November 2019). doi: 10.1038/s41467-019-13068-7 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 Arrazo., 2021J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Bromley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Quesada, A. Repingon, K. K. Sabapathy, M. Schuld, D. Su, J. Swinarton, A. Száva, K. Tan, P. Tan, V. D. Vaidya, Z. Vernon, Z. Zabaneh and Y. Zhang. 2021. Quantum circuits with many photons on a programmable nanophotonic chip. Nature 591, 7848 (March 2021, 54--60). doi: 10.1038/s41586-021-03202-1 Evered, 2023Simon J. Evered, Dolev Bluvstein, Marcin Kalinowski, Sepehr Ebadi, Tom Manovitz, Hengyun Zhou, Sophie H. Li, Alexandra A. Geim, Tout T. Wang, Nishad Maskara, Harry Levine, Giulia Semeghini, Markus Greiner, Vladan Vuletić and Mikhail D. Lukin. 2023. High-fidelity parallel entangling gates on a neutral-atom quantum computer. Nature 622, 7982 (October 2023, 268--272). doi: 10.1038/s41586-023-06481-y and are at the core of certain proposed architectures Bartol., 2023Sara Bartolucci, Patrick Birchall, Hector Bombín, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Terry Rudolph and Chris Sparrow. 2023. Fusion-based quantum computation. Nature Communications 14, 1 (February 2023). doi: 10.1038/s41467-023-36493-1 Bouras., 2021J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci and Ish Dhand. 2021. Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer. Quantum 5 (February 2021, 392). doi: 10.22331/q-2021-02-04-392, the most common computation primitives exposed by current hardware are one and two-qubit gates, with error rates dominated typically by an order of magnitude by the latter Steiger, 2018Damian S. Steiger, Thomas Häner and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (January 2018, 49). doi: 10.22331/q-2018-01-31-49 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92. It has thus become standard to use the number of two-qubit entangling gates as the cost function for near-term programs – typically the CX gate, though many other two-qubit gates could be used equivalently.

When considering error-corrected computations, on the other hand, what is an “expensive” computation is no longer dictated by hardware noise, but rather by the affordances of the error correcting code: depending on how the quantum data is redundantly encoded in the code space, the fault tolerant execution of specific operations may be anywhere between very straight forward and nigh-impossible². Concretely, the bottleneck is widely expected to be the execution of a single-qubit gate, such as the T gate.

In summary, whilst much of the hardware design, the error correcting codes and what programs will actually be executed is still in flux, the research community has mostly coallesced around cost functions based on gate count statistics Karupp., 2025Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson and Johnson P. Thomas. 2025. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions. Quantum Reports 7, 1 (January 2025, 2). doi: 10.3390/quantum7010002. Counting a type of gate is a simple and popular choice. Making some additional assumptions on the gate parallelism of future hardware, one may also consider cost functions based on gate depth, i.e. the length of the longest chain of gates that cannot be run simultaneously Seling., 2013Peter Selinger. 2013. Quantum circuits of T-depth one. Physical Review A 87, 4 (April 2013, 042302). doi: 10.1103/physreva.87.042302 Basile., 2024Daniel Basilewitsch, Clemens Dlaska and Wolfgang Lechner. 2024. Comparing planar quantum computing platforms at the quantum speed limit. Physical Review Research 6, 2 (April 2024, 023026). doi: 10.1103/physrevresearch.6.023026. These may model run times more closely, but come at the price of non-local cost function: whether local transformations of the program will have an effect on a depth-based cost function can only be decided by recomputing the cost over the program globally.

The best: unitary synthesis #

The ne plus ultra of quantum compilation is unitary synthesis. It leverages the representation of a quantum computation as a square, complex-valued, unitary matrix, which is then re-synthetised as a new, equivalent (and hopefully optimised!) quantum circuit. This approach thus breaks down quantum optimisation into two separate sub-problems:

1. Reduce a $n$-qubit quantum circuit into a $2^n \times 2^n$ matrix. This matrix is a unique representation of the computation, meaning that any two equivalent computations will be mapped to the same matrix.
2. Find the optimal decomposition of matrix into primitive quantum gates, which can be expressed as a new, equivalent quantum circuit.

The uniqueness of the unitary matrix representation makes it invaluable as a resource for computation optimisation. Not only does it reduce any potentially large collection of equivalent inputs to a single form; it also – crucially – provides a sound metric on the space of all circuits that can be used to measure the distance between synthesised circuits and direct the search towards the optimal solution.

Early work explored general unitary decomposition schemes obtained analytically from linear algebra. These express arbitrary unitaries as a a product of unitaries that typically correspond to one and two-qubit gates in the quantum circuit model Iten, 2016Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home and Matthias Christandl. 2016. Quantum circuits for isometries. Physical Review A 93, 3 (March 2016, 032318). doi: 10.1103/PhysRevA.93.032318 Iten, 2019Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli and Roger Colbeck. 2019. Introduction to UniversalQCompiler. arXiv: 1904.01072 [quant-ph]. Approaches using the Cosine-Sine decomposition Mött�., 2004Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm and Martti M. Salomaa. 2004. Quantum Circuits for General Multiqubit Gates. Physical Review Letters 93, 13 (Septempter 2004, 130502). doi: 10.1103/PhysRevLett.93.130502, the Quantum Shanon decomposition Krol, 2022Anna M. Krol, Aritra Sarkar, Imran Ashraf, Zaid Al-Ars and Koen Bertels. 2022. Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers. Applied Sciences 12, 2 (January 2022, 759). doi: 10.3390/app12020759 and the QR decomposition Sedlák, 2008Michal Sedlák and Martin Plesch. 2008. Towards optimization of quantum circuits. Open Physics 6, 1 (March 2008, 128--134). doi: 10.2478/s11534-008-0039-8 have been proposed. While some schemes have been shown to be asymptotically efficient for almost all unitaries [?], such strategies typically generate fixed-sized circuits and fail to synthesise short circuits when such circuits exist. The size of synthesised circuits grows exponentially with the number of qubits, making most such schemes impractical beyond three qubits.

Unitary matrix decomposition can also be combined with tools from classical circuit design: in Loke, 2014T. Loke, J. B. Wang and Y. H. Chen. 2014. OptQC : An optimized parallel quantum compiler. Computer Physics Communications 185, 12 (December 2014, 3307--3316). doi: 10.1016/j.cpc.2014.07.022, Loke et al. proposed an approach merging reversible circuit (see below), a classical compilation problem, with unitary matrix synthesis. They show that searching for decompositions $U = PU'Q$, where $P$ and $Q$ are classical reversible circuits can yield shorter circuits when using the Cosine-Sine decomposition for the unitaries $U$ and $U'$.

To address the shortcomings of analytical decompositions, search-based approaches have been developed. Unlike the algebraic approaches, in search-based circuit synthesis the circuit decomposition problem is viewed as an optimisation problem. The space of all possible quantum circuits is explored to find the one that implements the desired unitary whilst minimising the cost function. The major challenge of such methods is the gigantic (typically super-exponential) size of the search space of all possible programs: without mitigation, most work in this space struggle to scale beyond a handful of qubits.

Up to 3 qubits, T-depth optimal circuits can be found using exhaustive brute force search first proposed in Amy, 2013M. Amy, D. Maslov, M. Mosca and M. Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 6 (June 2013, 818--830). doi: 10.1109/TCAD.2013.2244643 and improved in Gheorg., 2022Vlad Gheorghiu, Michele Mosca and Priyanka Mukhopadhyay. 2022. A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits. npj Quantum Information 8, 1 (Septempter 2022). doi: 10.1038/s41534-022-00624-1. Aymptotic bounds on the number of T gates required for general unitary synthesis was recently given in Gosset, 2024David Gosset, Robin Kothari and Kewen Wu. 2024. Quantum state preparation with optimal T-count. arXiv: 2411.04790 [quant-ph].

To scale to 4 qubits and handle gate sets with continuous parameters, required for non-fault tolerant circuits, an A* search with smart pruning heuristics was proposed in Davis, 2020Marc G. Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi and Costin Iancu. 2020. Towards Optimal Topology Aware Quantum Circuit Synthesis. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), October 2020. IEEE, 223--234. doi: 10.1109/QCE49297.2020.00036. Outputs of this approach are no longer provably optimal but the results match optimal decompositions in all known instances. This line of work has subsequently be further refined with heuristics based on pre-defined circuit templates Smith, 2023Ethan Smith, Marc Grau Davis, Jeffrey Larson, Ed Younis, Lindsay Bassman Oftelie, Wim Lavrijsen and Costin Iancu. 2023. LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach. ACM Transactions on Quantum Computing 4, 1 (February 2023, 1--23). doi: 10.1145/3548693 Madden, 2022Liam Madden and Andrea Simonetto. 2022. Best Approximate Quantum Compiling Problems. ACM Transactions on Quantum Computing 3, 2 (March 2022, 1--29). doi: 10.1145/3505181, parameter instantiation Younis, 2022Ed Younis and Costin Iancu. 2022. Quantum Circuit Optimization and Transpilation via Parameterized Circuit Instantiation. arXiv: 2206.07885 [quant-ph] Younis, 2021Ed Younis, Koushik Sen, Katherine Yelick and Costin Iancu. 2021. QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), October 2021. IEEE, 232--243. doi: 10.1109/QCE52317.2021.00041 Rakyta, 2022Péter Rakyta and Zoltán Zimborás. 2022. Approaching the theoretical limit in quantum gate decomposition. Quantum 6 (May 2022, 710). doi: 10.22331/q-2022-05-11-710, machine learning Weiden, 2023Mathias Weiden, Ed Younis, Justin Kalloor, John Kubiatowicz and Costin Iancu. 2023. Improving Quantum Circuit Synthesis with Machine Learning. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE. doi: 10.1109/QCE57702.2023.00093 and tensor networks Kuklia., 2023Alon Kukliansky, Ed Younis, Lukasz Cincio and Costin Iancu. 2023. QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Septempter 2023. IEEE, 814--824. doi: 10.1109/QCE57702.2023.00096.

Some of these heuristics also make it possible to synthesise circuits with device constraints in mind and to trade off decomposition accuracy for shallower circuit depth and lower noise. In Wu, 2020Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong and Costin Iancu. 2020. QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis. arXiv: 2012.09835 [quant-ph] Kuklia., 2023Alon Kukliansky, Ed Younis, Lukasz Cincio and Costin Iancu. 2023. QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Septempter 2023. IEEE, 814--824. doi: 10.1109/QCE57702.2023.00096, the authors have also explored partitioning the circuit into smaller parts that are optimised independently to scale these techniques to large circuit sizes. Despite the reduced optimisation performance that the boundaries of the partitioned circuits introduce, the combination of circuit partitioning with the techniques listed above yields some of the best performing circuit optimisation techniques developed to date Costin., 2025Bert Costin Iancu. 2025. Berkeley Quantum Synthesis Toolkit. Retrieved on 09/01/2025 from https://bqskit.lbl.gov/.

However, a fundamental flaw of all unitary synthesis schemes is the $4^n$-scaling in the number of qubits $n$ of the unitary representation itself. This means that no matrix-based synthesis method, however efficient, will ever be able to handle computations with much more than a dozen qubits. Circuit partitioning schemes do not solve this problem as much as they avoid it, by considering only a subset of the computation – at the cost of inferior performance.

Closer to the concerns of this thesis, the unitary representation is also a poor candidate to express hybrid computations. In an exciting recent development, first studies of synthesis schemes in the presence of mid-circuit measurements have been performed that generalise search-based circuit synthesis to reason about measurements and conditional gates Alam, 2024Faisal Alam and Bryan K. Clark. 2024. Learning dynamic quantum circuits for efficient state preparation. arXiv: 2410.09030 [quant-ph] Niu, 2024Siyuan Niu, Efekan Kokcu, Anupam Mitra, Aaron Szasz, Akel Hashim, Justin Kalloor, Wibe Albert de Jong, Costin Iancu and Ed Younis. 2024. AC/DC: Automated Compilation for Dynamic Circuits. arXiv: 2412.07969 [quant-ph]. They present promising results, with significant reductions in circuit depth for state preparation and circuit synthesis. However, the expressiveness of the programs considered in these recent advances remains limited to circuit-based representations. It is unclear if and how these techniques could be extended to synthesise more complex hybrid programs, such as repeat-until-success schemes, let alone the kind of arbitrary hybrid programs expressible in minIR.

See Ge, 2024Yan Ge, Wu Wenjie, Chen Yuheng, Pan Kaisen, Lu Xudong, Zhou Zixiang, Wang Yuhan, Wang Ruocheng and Yan Junchi. 2024. Quantum Circuit Synthesis and Compilation Optimization: Overview and Prospects. arXiv: 2407.00736 [quant-ph] for a recent review of work in this space. IS THIS ANY GOOD? Should I just read it?

The search for scalable representations #

Our study of unitary synthesis introduced us to a convenient two-step approach to quantum computation optimisation. The input computation (circuits, for the most part) is first transformed into a “global” representation that captures the computation as a whole, abstracting away the precise sequences of gates that composed the original circuit. This representation is then the input for the second half of the problem, which produces a circuit of the desired shape, equivalent to the original input but with reduced cost.

In addition to simplifying the original problem, such global intermediate representations are also well positioned to leverage the quantum-specific structure and symmetries in the computation. They can thus enable more advanced optimisations and are robust to varying circuit representation and local optimisation landscape.

The unitary matrix is the most common representation of quantum computations, but as we have seen it suffers from severe scaling problems in the number of qubits. The problem is not so much that arbitrary quantum computations require exponential space to be described – the space of all $n$-qubit unitaries $SU(2^n)$ is after all exponentially large. Rather, the issue is that the set of unitaries implementable in practice will be restricted to quantum computations with a polynomial number of gates; these only form a tiny subset of $SU(2^n)$³.

Another fruitful avenue of work for quantum optimisation has thus been the development of alternative representations for quantum computations that can encode polynomially sized quantum programs efficiently whilst enabling novel optimisations.

Phase Polynomials and Pauli Gadgets #

A particularly convenient global representation of many quantum computations is as products of Pauli exponentials, also known as Pauli “Gadgets” Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13. These unitaries are of the form

These exponentials are always valid $n$-qubit unitaries and can express entangling operations across any number of qubits: the qubits on which an operation $exp(i \alpha \cdot s)$ acts non-trivially are given by the indices of the characters in $s$ that are not the identity $I$. For instance, the exponential

The use of these primitives for quantum compilation was first explored in Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13, and further generalised in Cowtan, 2020Alexander Cowtan, Will Simmons and Ross Duncan. 2020. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv: 2007.10515 [quant-ph]. Starting from an (unordered) sequence of Pauli gadgets, the gadgets are clustered into sets of mutually commuting gadgets. These can then be jointly synthesised into a circuit, markedly reducing the number of entangling operations as compared to naively implementing one exponential at a time.

Further improvements to this work have since been presented in Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer- van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354 and Schmitz, 2024Albert T. Schmitz, Nicolas P. D. Sawaya, Sonika Johri and A. Y. Matsuura. 2024. Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition. Physical Review A 109, 4 (April 2024, 042418). doi: 10.1103/PhysRevA.109.042418, where new heuristics are introduced to choose the Pauli gadget ordering. In Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer- van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354, the hardware-specific connectivity constraints between qubits is also taken into account to produce programs that can be executed on the targetted architecture without overhead.

A close relative of Pauli gadgets – a strict smaller subset of it, to be precise – are the so-called phase polynomials Amy, 2018Matthew Amy, Parsiad Azimzadeh and Michele Mosca. 2018. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology 4, 1 (Septempter 2018, 015002). doi: 10.1088/2058-9565/aad8ca, obtained when restricting the Pauli strings $s \in \{I, Z\}^n$ to combinations of Z Pauli matrices and identities. These are particularly amenable to optimisation as in this case, all exponential terms commute. This gives the compiler a lot of freedom during circuit synthesis.

The action of phase polynomials on quantum states is actually quite easy to understand. Instead of the exponentials of $I$ and $Z$-based Pauli string, the computation can equivalently be given by its action on the basis states

The exponential expression is just a real number – indeed each term in the sum simply evaluates to either $a_i$ or $0$. A phase polynomial is thus a diagonal unitary matrix: it maps every basis state $\ket {b_1 \cdots b_n}$ to itself, multiplied by some phase $e^{i \theta}$.

Polynomially-sized circuits that implement diagonal matrices correspond to phase polynomials with $k = \mathcal{O}(n^p) \ll 2^n$, i.e. they can represent quantum computations efficiently and scale well with the number of qubits – thus allowing efficient algorithms that scale polynomially in the number of qubits $n$.

The Graysynth algorithm, as presented in Amy, 2018Matthew Amy, Parsiad Azimzadeh and Michele Mosca. 2018. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology 4, 1 (Septempter 2018, 015002). doi: 10.1088/2058-9565/aad8ca, has become the reference synthesis method for phase polynomials. The key observation that the authors made was that all terms of the sum within the exponential can be cycled through and obtained following the binary Gray codes Gray, 1953F. Gray. 1953. Pulse code communication. Retrieved from http://www.google.com/patents/US2632058. The Hamming distance of one that separates successive bitstrings in the code translate into a single two-qubit CX gate in Graysynth.

This approach was adapted to work with hardware connectivity constraints in Griend, 2022Arianne Meijer- van de Griend and Ross Duncan. 2022. Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 116--140. doi: 10.4204/EPTCS.394.8, Gogioso, 2022Stefano Gogioso and Richie Yeung. 2022. Annealing Optimisation of Mixed ZX Phase Circuits. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 415--431. doi: 10.4204/EPTCS.394.20 and Vandae., 2022Vivien Vandaele, Simon Martiel and Timothée Goubault de Brugière. 2022. Phase polynomials synthesis algorithms for NISQ architectures and beyond. Quantum Science and Technology 7, 4 (Septempter 2022, 045027). doi: 10.1088/2058-9565/ac5a0e. An up-to-date study of performance of phase polynomial-based compiler optimisations and comparisons with standard approaches is performed in Meijer., 2025Arianne Meijer - van de Griend. 2025. A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation. Journal of Systems and Software 221 (March 2025, 112224). doi: 10.1016/j.jss.2024.112224.

The study of phase polynomials can also be generalised to arbitrary diagonal operators. Tight asymptotic bounds on the resource requirements for arbitrary diagonal operator synthesis, along with their implementation, was recently given in Sun, 2023Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan and Shengyu Zhang. 2023. Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 10 (October 2023, 3301--3314). doi: 10.1109/TCAD.2023.3244885. The authors propose using a smart meshing of different Gray codes in parallel, as well as, where available, additional qubits as ancilla registers to further parallelise computations and minimise circuit depth. The resulting general purpose decomposition of arbitrary diagonal operators yields circuits of depth $\mathcal O(\frac{2^n}{n})$ and size $\mathcal O(\frac{n^2}{\log n}) + 2^{n+3}$, as well as improved bounds in the presence of $m \geq 2n$ ancilla qubits.

Clifford synthesis #

The group of all $n$-qubit unitaries $SU(2^n)$ contains a subgroup that has become an object of study across many domains of quantum computing science: the Clifford group. We have already mentioned that it is at the centre of quantum error correction theory Bravyi, 2005Sergey Bravyi and Alexei Kitaev. 2005. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A 71, 2 (February 2005, 022316). doi: 10.1103/PhysRevA.71.022316; it is also a cornerstone of measurement-based quantum computing Rausse., 2001Robert Raussendorf and Hans J. Briegel. 2001. A One-Way Quantum Computer. Physical Review Letters 86, 22 (May 2001, 5188--5191). doi: 10.1103/PhysRevLett.86.5188 and graph states Hein, 2004M. Hein, J. Eisert and H. J. Briegel. 2004. Multiparty entanglement in graph states. Physical Review A 69, 6 (June 2004, 062311). doi: 10.1103/physreva.69.062311, as well as one of the most promising approaches for fast quantum simulations Gottes., 1999Daniel Gottesman. 1999. The Heisenberg representation of quantum computers. In Group 22: Proceedings of the 12th International Colloquium onGroup Theoretical Methods in Physics,. International Press, 32--43 Bravyi, 2019Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset and Mark Howard. 2019. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum 3 (Septempter 2019, 181). doi: 10.22331/q-2019-09-02-181 Kissin., 2022Aleks Kissinger and John van de Wetering. 2022. Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions. Quantum Science and Technology 7, 4 (July 2022, 044001). doi: 10.1088/2058-9565/ac5d20.

It has also given rise to a quantum program representation that has been used profusely for compiler optimistaion. Indeed, the Clifford fragment, i.e. the quantum circuits with unitaries in the Clifford group, admit an efficient, $\Theta(2n^2)$-sized representation, known as a Clifford tableau Aarons., 2004Scott Aaronson and Daniel Gottesman. 2004. Improved simulation of stabilizer circuits. Physical Review A 70, 5 (November 2004, 052328). doi: 10.1103/PhysRevA.70.052328.

In Aarons., 2004Scott Aaronson and Daniel Gottesman. 2004. Improved simulation of stabilizer circuits. Physical Review A 70, 5 (November 2004, 052328). doi: 10.1103/PhysRevA.70.052328 the first Clifford circuit synthesis procedure is given, using an analytical decomposition of clifford tableaus into $O(n^2 /\log n)$ one and two-qubit gates. An improved, Bruhat-based decomposition that is optimal in the number of Hadamard gates was subsequently proposed in Maslov, 2018Dmitri Maslov and Martin Roetteler. 2018. Shorter Stabilizer Circuits via Bruhat Decomposition and Quantum Circuit Transformations. IEEE Transactions on Information Theory 64, 7 (July 2018, 4729--4738). doi: 10.1109/tit.2018.2825602. In the case of a clifford fragment directly followed by measurements, the procedure can be further refined to replace gates with classical computation on the measurement outcomes Bravyi, 2021Sergey Bravyi and Dmitri Maslov. 2021. Hadamard-Free Circuits Expose the Structure of the Clifford Group. IEEE Transactions on Information Theory 67, 7 (July 2021, 4546--4563). doi: 10.1109/TIT.2021.3081415. Finally, an alternative normal form that is well-suited to hardware with limited nearest neighbours connectivity was also derived using a diagrammatic approach [?].

Just as in unitary synthesis, circuit decompositions more efficient than the general analytical expressions can be obtained on a case-by-case basis using search and optimisation. The pendant to the provably optimal decompositions of unitaries obtained through brute force search Amy, 2013M. Amy, D. Maslov, M. Mosca and M. Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 6 (June 2013, 818--830). doi: 10.1109/TCAD.2013.2244643 also exists for Clifford circuits Kliuch., 2013Vadym Kliuchnikov and Dmitri Maslov. 2013. Optimization of Clifford circuits. Physical Review A 88, 5 (November 2013, 052307). doi: 10.1103/physreva.88.052307. Due to the more efficient representation and smaller search space, all optimal Clifford circuits could be found up to 6 qubits. Using modern SAT solvers, optimal clifford synthesis has recently been pushed much further, with known optimal circuits beyond 20 qubits Peham, 2023Tom Peham, Nina Brandl, Richard Kueng, Robert Wille and Lukas Burgholzer. 2023. Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers. In IEEE International Conference on Quantum Computing and Engineering, QCE 2023, Bellevue, WA, USA, September 17-22, 2023. IEEE, 802--813. doi: 10.1109/QCE57702.2023.00095 Schnei., 2023Sarah Schneider, Lukas Burgholzer and Robert Wille. 2023. A SAT Encoding for Optimal Clifford Circuit Synthesis. In Proceedings of the 28th Asia and South Pacific Design Automation Conference, January 2023. IEEE. doi: 10.1145/3566097.3567929.

Heuristic optimisation approaches have also been shown to be effective on Clifford optimisation Bravyi, 2021Sergey Bravyi and Dmitri Maslov. 2021. Hadamard-Free Circuits Expose the Structure of the Clifford Group. IEEE Transactions on Information Theory 67, 7 (July 2021, 4546--4563). doi: 10.1109/TIT.2021.3081415 Fagan, 2018Andrew Fagan and Ross Duncan. 2018. Optimising Clifford Circuits with Quantomatic. In Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, 85--105. doi: 10.4204/EPTCS.287.5 and scale to larger systems. For Clifford computations on devices with restricted connectivity, an architecture-aware synthesis method was proposed in Winderl, 2024David Winderl, Qunsheng Huang, Arianne Meijer-van de Griend and Richie Yeung. 2024. Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus. arXiv: 2309.08972 [quant-ph].

Diagrammatic representations #

Quantum computer science and quantum mechanics in general have a rich history in diagrammatic representations Feynman, 1949R. P. Feynman. 1949. The Theory of Positrons. Physical Review 76, 6 (Septempter 1949, 749--759). doi: 10.1103/physrev.76.749 Coecke, 2017Bob Coecke and Aleks Kissinger. 2017. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press. doi: 10.1017/9781316219317 Backens, 2019Miriam Backens and Aleks Kissinger. 2019. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. Electronic Proceedings in Theoretical Computer Science 287 (January 2019, 23--42). doi: 10.4204/EPTCS.287.2. These have allowed to picture complex physical processes as intuitive operations in a graphical language and have – as a nice side-effect – led to a plethoral of state of the art quantum circuit optimisation techniques!

A diagrammatic representation of a quantum computation is obtained by lifting the gates that form a quantum circuit into the nodes of a more abstract graph-based graphical calculus. The most commonly used flavour of calculus used for circuit optimisation is the ZX calculus Coecke, 2008Bob Coecke and Ross Duncan. 2008. Interacting Quantum Observables Coecke, 2012Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang. 2012. Strong Complementarity and Non-locality in Categorical Quantum Mechanics. In 2012 27th Annual IEEE Symposium on Logic in Computer Science, June 2012. IEEE, 245--254. doi: 10.1109/lics.2012.35 Weteri., 2020John van de Wetering. 2020. ZX-calculus for the working quantum computer scientist. arXiv: 2012.13966 [quant-ph] Yeung, 2024Richie Yeung, Konstantinos Meichanetzidis, Alexandre Krajenbrink and François Charton. 2024. Teaching small transformers to rewrite ZX diagrams. MathAI submission.

By breaking up multi-qubit gates into several non-unitary tensors, the ZX calculus and related variants Roy, 2011Shibdas Roy, Dipankar Home, Guruprasad Kar and Archan S. Majumda. 2011. Towards Normal Forms for GHZ∕W Calculus. In AIP Conference Proceedings. AIP, 112--119. doi: 10.1063/1.3635852 Backens, 2019Miriam Backens and Aleks Kissinger. 2019. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. Electronic Proceedings in Theoretical Computer Science 287 (January 2019, 23--42). doi: 10.4204/EPTCS.287.2 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 expose some of the symmetry and structure of quantum physics in the form of simple and intuitive graphical rules. This has enabled the discovery of many quantum optimisation techniques (e.g Duncan, 2019Ross Duncan, Aleks Kissinger, Simon Perdrix and John van de Wetering. 2019. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. arXiv: 1902.03178 [quant-ph] Weteri., 2024John van de Wetering, Richie Yeung, Tuomas Laakkonen and Aleks Kissinger. 2024. Optimal compilation of parametrised quantum circuits. arXiv: 2401.12877 [quant-ph]), some of which we have already reviewed Huang, 2024Qunsheng Huang, David Winderl, Arianne Meijer- van de Griend and Richie Yeung. 2024. Redefining Lexicographical Ordering: Optimizing Pauli String Decompositions for Quantum Compiling. CoRR abs/2408.00354. doi: 10.48550/ARXIV.2408.00354 Gogioso, 2022Stefano Gogioso and Richie Yeung. 2022. Annealing Optimisation of Mixed ZX Phase Circuits. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 415--431. doi: 10.4204/EPTCS.394.20 Griend, 2022Arianne Meijer- van de Griend and Ross Duncan. 2022. Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices. In Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, 116--140. doi: 10.4204/EPTCS.394.8 Cowtan, 2019Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons and Seyon Sivarajah. 2019. Phase Gadget Synthesis for Shallow Circuits. In Proceedings 16th International Conference on Quantum Physics and Logic, QPL 2019, Chapman University, Orange, CA, USA, June 10-14, 2019, 213--228. doi: 10.4204/EPTCS.318.13 Cowtan, 2020Alexander Cowtan, Will Simmons and Ross Duncan. 2020. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz. arXiv: 2007.10515 [quant-ph]. This selection of papers is not quite exhaustive⁴ – there are currently over 300 hundred papers on the topic as indexed by zxcalculus.com.

Aside from being an invaluable tool for research and compiler pass design, a major contribution of these diagrammatic representations is the introduction of graph rewriting systems Ehrig, 1973Hartmut Ehrig, Michael Pfender and Hans Jürgen Schneider. 1973. Graph-Grammars: An Algebraic Approach. In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973. IEEE Computer Society, 167--180. doi: 10.1109/SWAT.1973.11 Rozenb., 1997Grzegorz Rozenberg. 1997. Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific König, 2018Barbara König, Dennis Nolte, Julia Padberg and Arend Rensink. 2018. A Tutorial on Graph Transformation. In Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. Springer, 83--104. doi: 10.1007/978-3-319-75396-6_5 to quantum computing. Rewriting systems were first introduced on strings Dersho., 1990Nachum Dershowitz and Jean-Pierre Jouannaud. 1990. Rewrite Systems, then generalised to trees and terms Bezem, 2003Marc Bezem, Jan Willem Klop and Roel Vrijer. 2003. Term Rewriting Systems (1. publ. ed.). Cambridge University Press, Cambridge.

From a formal point of view, rewrite systems endow quantum compilation with well-defined semantics and strong theoretical foundations Lack, 2005Stephen Lack and Pawel Sobocinski. 2005. Adhesive and quasiadhesive categories. RAIRO Theor. Informatics Appl. 39, 3 (511--545). doi: 10.1051/ITA:2005028. Just as importantly (or more so), they establish a practical, purely declarative framework in which compiler transformations can be defined, debugged and analysed. System properties such as completeness, confluence and termination of rewriting systems Verma, 1995Rakesh M. Verma. 1995. Transformations and confluence for rewrite systems. Theoretical Computer Science 152, 2 (December 1995, 269--283). doi: 10.1016/0304-3975(94)00255-0 Backens, 2014Miriam Backens. 2014. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics 16, 9 (Septempter 2014, 093021). doi: 10.1088/1367-2630/16/9/093021 Biamon., 2023J Biamonte and A Nasrallah. 2023. The ZX-Calculus is Canonical in the Heisenberg Picture for Stabilizer Quantum Mechanics. arXiv: 2301.05717 [quant-ph] can be analytically studied, proven and then be relied on by compilers for soundness and performance guarantees Duncan, 2020Ross Duncan, Aleks Kissinger, Simon Perdrix and John van de Wetering. 2020. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum 4 (June 2020, 279). doi: 10.22331/q-2020-06-04-279 Kissin., 2020Aleks Kissinger and John van de Wetering. 2020. PyZX: Large Scale Automated Diagrammatic Reasoning. In Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019. Open Publishing Association, 229-241. doi: 10.4204/EPTCS.318.14 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92 Borgna, 2023Agustí Borgna. 2023. Towards a compiler toolchain for quantum programs.

However, there is an apparent tension in the integration of diagrammatic calculi into compilers between the search for abstract primitives admitting a simple rewriting logic Heurtel, 2024Nicolas Heurtel. 2024. A Complete Graphical Language for Linear Optical Circuits with Finite-Photon-Number Sources and Detectors. arXiv: 2402.17693 [quant-ph] Booth, 2024Robert I. Booth, Titouan Carette and Cole Comfort. 2024. Graphical Symplectic Algebra. arXiv: 2401.07914 [cs.LO] Felice, 2023Giovanni de Felice, Razin A. Shaikh, Boldizsár Poór, Lia Yeh, Quanlong Wang and Bob Coecke. 2023. Light-Matter Interaction in the ZXW Calculus. Electronic Proceedings in Theoretical Computer Science 384 (August 2023, 20--46). doi: 10.4204/EPTCS.384.2 Carette, 2023Titouan Carette, Timothée Hoffreumon, Émile Larroque and Renaud Vilmart. 2023. Complete Graphical Language for Hermiticity-Preserving Superoperators. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), June 2023. IEEE, 1--22. doi: 10.1109/LICS56636.2023.10175712 and the requirement to capture all the expressivity and constraints of hardware targets.

An example of this is the ZX circuit extraction problem Quanz, 2024Marcel Quanz, Korbinian Staudacher and Karl Fürlinger. 2024. Parallel Quantum Circuit Extraction from MBQC-Patterns. In 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 1078-1087. doi: 10.1109/IPDPSW63119.2024.00179 Backens, 2021Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski and John van de Wetering. 2021. There and back again: A circuit extraction tale. Quantum 5 (March 2021, 421). doi: 10.22331/q-2021-03-25-421​: it is in general hard to recover an executable quantum circuit from a ZX diagram as the latter is strictly more general and primitives cannot be mapped one-to-one. Similarly, while simple quantum-classical hybrid computations can be expressed using extensions of ZX Borgna, 2021Agustí Borgna, Simon Perdrix and Benoî Valiron. 2021. Hybrid Quantum-Classical Circuit Simplification with the ZX-Calculus. In Programming Languages and Systems, Cham. Springer International Publishing, 121--139. doi: 10.1007/978-3-030-89051-3_8 Carette, 2021Titouan Carette, Emmanuel Jeandel, Simon Perdrix and Renaud Vilmart. 2021. Completeness of Graphical Languages for Mixed State Quantum Mechanics. ACM Transactions on Quantum Computing 2, 4 (December 2021, 1--28). doi: 10.1145/3464693 Koziel., 2024Alexander Koziell-Pipe and Aleks Kissinger. 2024. Hybrid Quantum-Classical Machine Learning with String Diagrams. arXiv: 2407.03673 [quant-ph], it will never be possible to capture the full breadth and generality of classical CPU instruction sets in a practical and extensible (and algebraically satisfying) way.

Reversible classical circuits #

There are many more representations, that have either been taken over from classical compiler optimsations or were developed for specific purposes. The last we will mention is reversible circuits synthesis, a fully classical circuit design problem which can draw from results of decades of research. From a quantum perspective, reversible classical circuits correspond to unitaries (and more generally, isometries) that send basis states to basis states – and thus do not introduce any entanglement Shende, 2002V.V. Shende, A.K. Prasad, I.L. Markov and J.P. Hayes. 2002. Reversible logic circuit synthesis. In IEEE/ACM International Conference on Computer Aided Design, 2002, November 2002. IEEE, 353--360. doi: 10.1109/iccad.2002.1167558. We highlight a selection of the more recent work in the field and refer the reader to the much more complete, albeit ageing, survey of Saeedi, 2013Mehdi Saeedi and Igor L. Markov. 2013. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys 45, 2 (February 2013, 1--34). doi: 10.1145/2431211.2431220.

Up to 4 (qu)bits, all reversible circuits and their optimal synthesis can be generated by brute force Li, 2014Zhiqiang Li, Hanwu Chen, Xiaoyu Song and Marek Perkowski. 2014. A Synthesis Algorithm for 4-Bit Reversible Logic Circuits with Minimum Quantum Cost. ACM Journal on Emerging Technologies in Computing Systems 11, 3 (December 2014, 1--19). doi: 10.1145/2629542. Viewing reversible circuits as a permutation of all $2^n$ bitstrings, Susam et al. pre-compute optimal circuits only for swaps of two bitstrings (transpositions). These can then be used as part of a standard selection sort to synthesise arbitrary permutations. The number of such permutations scales much more favourably compared to arbitrary permutation, allowing for fast circuit synthesis up to 20+ (qu)bits in a fraction of a second, with good performance.

Truth-table or matrix representations of reversible circuits suffer from the same exponential scaling as unitaries. To address these, other representations that have been used include exclusive sums of product terms (ESOP) Fazel, 2007K. Fazel, M. A. Thornton and J. E. Rice. 2007. ESOP-based Toffoli Gate Cascade Generation. In 2007 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, August 2007. IEEE. doi: 10.1109/pacrim.2007.4313212 Bandyo., 2014Chandan Bandyopadhyay, Hafizur Rahaman and Rolf Drechsler. 2014. A Cube Pairing Approach for Synthesis of ESOP-Based Reversible Circuit. In 2014 IEEE 44th International Symposium on Multiple-Valued Logic, May 2014. IEEE, 109--114. doi: 10.1109/ismvl.2014.27, positive polarity Reed-Müller codes (PPRM) Jegier, 2017Jerzy Jegier and Paweł Kerntopf. 2017. PPRM-based approach to synthesis of reversible functions. In Photonics Applications in Astronomy, Communications, Industry, and High Energy Physics Experiments 2017, August 2017. SPIE, 1044523. doi: 10.1117/12.2280943 and decision diagrams Stojko., 2019Suzana Stojković, Radomir Stanković, Claudio Moraga and Milena Stanković. 2019. Reversible Circuits Synthesis from Functional Decision Diagrams by using Node Dependency Matrices. Journal of Circuits, Systems and Computers 29, 05 (August 2019, 2050079). doi: 10.1142/s0218126620500796 Wille, 2010Robert Wille and Rolf Drechsler. 2010. Effect of BDD Optimization on Synthesis of Reversible and Quantum Logic. Electronic Notes in Theoretical Computer Science 253, 6 (March 2010, 57--70). doi: 10.1016/j.entcs.2010.02.006 Pang, 2011Yu Pang, Shaoquan Wang, Zhilong He, Jinzhao Lin, Sayeeda Sultana and Katarzyna Radecka. 2011. Positive Davio-based synthesis algorithm for reversible logic. In 2011 IEEE 29th International Conference on Computer Design (ICCD), October 2011. IEEE, 212--218. doi: 10.1109/iccd.2011.6081399.

The quantum framework is strictly more general than the classical regime the problem was originally studied in. This affords additional freedom for decomposition schemes, such as decompositions of CCX gates on 3 qubits into single and two-qubit gates Shende, 2008Vivek V. Shende and Igor L. Markov. 2008. On the CNOT-cost of TOFFOLI gates. arXiv: 0803.2316 [quant-ph]. Various optimised decompositions for sequences of Toffoli gates have also been similarly developed Scott, 2008Nathan O. Scott and Gerhard W. Dueck. 2008. Pairwise decomposition of toffoli gates in a quantum circuit. In Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 2008. ACM, 231--236. doi: 10.1145/1366110.1366168 Arabza., 2010Mona Arabzadeh, Mehdi Saeedi and Morteza Saheb Zamani. 2010. Rule-based optimization of reversible circuits. In 2010 15th Asia and South Pacific Design Automation Conference (ASP-DAC), January 2010. IEEE, 849--854. doi: 10.1109/aspdac.2010.5419684 Datta, 2013Kamalika Datta, Gaurav Rathi, Robert Wille, Indranil Sengupta, Hafizur Rahaman and Rolf Drechsler. 2013. Exploiting Negative Control Lines in the Optimization of Reversible Circuits Rahman, 2014Md Zamilur Rahman and Jacqueline E. Rice. 2014. Templates for Positive and Negative Control Toffoli Networks Datta, 2015Kamalika Datta, Indranil Sengupta and Hafizur Rahaman. 2015. A Post-Synthesis Optimization Technique for Reversible Circuits Exploiting Negative Control Lines. IEEE Transactions on Computers 64, 4 (April 2015, 1208--1214). doi: 10.1109/tc.2014.2315641 Arpita, 2015Pyreddy Mary Arpita, Kamalika Datta, Rohith Vemula and Indranil Sengupta. 2015. Optimization of reversible circuits using triple-gate templates at quantum gate level. In 2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), January 2015. IEEE, 120--124. doi: 10.1109/edcav.2015.7060551 Abdess., 2016Nabila Abdessaied, Matthew Amy, Mathias Soeken and Rolf Drechsler. 2016. Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits. In 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), May 2016. IEEE, 150--155. doi: 10.1109/ismvl.2016.33 Gado, 2021Mariam Gado and Ahmed Younes. 2021. Optimization of Reversible Circuits Using Toffoli Decompositions with Negative Controls. Symmetry 13, 6 (June 2021, 1025). doi: 10.3390/sym13061025. Mohammadi and Eshghi introduced 4-valued truth tables to extend classical circuit synthesis to include $\sqrt{X}$ (also known as V) gates Mohamm., 2008Majid Mohammadi and Mohammad Eshghi. 2008. Behavioral description of quantum V and V+ gates to design quantum logic circuits. In 2008 5th International Multi-Conference on Systems, Signals and Devices, July 2008. IEEE, 1--5. doi: 10.1109/ssd.2008.4632850. References Soeken, 2012M. Soeken, Z. Sasanian, R. Wille, D. M. Miller and R. Drechsler. 2012. Optimizing the Mapping of Reversible Circuits to Four-Valued Quantum Gate Circuits. In 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, May 2012. IEEE, 173--178. doi: 10.1109/ismvl.2012.64 as well as Rahman, 2012Md. Mazder Rahman, Gerhard W. Dueck and Anindita Banerjee. 2012. Optimization of Reversible Circuits Using Reconfigured Templates incorporated controlled-V gates into template matching strategies and showed significant improvements in synthesised gate count . Finally, Maslov, 2016Dmitri Maslov. 2016. Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Physical Review A 93, 2 (February 2016, 022311). doi: 10.1103/physreva.93.022311 proposed decomposing Toffolis only up to relative phase, introducing a lot of freedom in the quantum decompositions that are required compared to the traditional classical decompositions.

In summary, our exploration of various quantum computation representations and synthesis techniques highlights both their remarkable strengths and inherent limitations. On the positive side, a variety of scalable representations – such as phase polynomials, Pauli gadgets, Clifford tableaus, diagrammatic calculi, and reversible circuits – have been developed to abstract computations and enable highly tailored optimisation methods. These approaches leverage the unique structure and symmetries of quantum computations, achieving significant reductions in circuit size, depth, and hardware-specific overheads. Techniques such as phase polynomial synthesis and Clifford tableau representations are widely applicable and are a cornerstore of modern quantum compilers Amy, 2019Matthew Amy. 2019. Formal methods in Quantum Circuit Design. Retrieved from https://uwspace.uwaterloo.ca/handle/10012/14480 Meijer., 2025Arianne Meijer - van de Griend. 2025. A comparison of quantum compilers using a DAG-based or phase polynomial-based intermediate representation. Journal of Systems and Software 221 (March 2025, 112224). doi: 10.1016/j.jss.2024.112224. Meanwhile, diagrammatic calculi, such as the ZX calculus, provide a flexible and theoretically robust framework for optimisations, often revealing simplifications invisible in the traditional gate-based model.

However, this specialisation comes with trade-offs. These representations and techniques target purely unitary computations and rely on strict assumptions about the primitives they support. While efficient for the scenarios they were designed for, these methods can struggle to incorporate new primitives and are hard to adapt to hybrid programs. In order to develop more versatile and adaptable compilation platforms, a foundation built on more general purpose tooling is required.

Resorting to peephole optimisations #

We have so far considered quantum-specific compiler optimisations, which can attain near-optimal results (unitary synthesis) as well as perform scalable non-local program resynthesis and optimisation (phase polynomials, Clifford tableaus etc.). We have however seen that these techniques struggle to generalise to hybrid programs and require custom program representations, which carry with them a high implementation burden for compilers. In contrast, peephole optimisations McKeem., 1965W. M. McKeeman. 1965. Peephole optimization. Communications of the ACM 8, 7 (July 1965, 443--444). doi: 10.1145/364995.365000 Tanenb., 1982Andrew S. Tanenbaum, Hans van Staveren and Johan W. Stevenson. 1982. Using Peephole Optimization on Intermediate Code. ACM Transactions on Programming Languages and Systems 4, 1 (January 1982, 21--36). doi: 10.1145/357153.357155 are a general purpose optimisation technique as old as compilation itself that act directly on the program IR and come with wide support within classical compiler ecosystems Menend., 2017David Menendez and Santosh Nagarakatte. 2017. Alive-Infer: data-driven precondition inference for peephole optimizations in LLVM. ACM SIGPLAN Notices 52, 6 (June 2017, 49--63). doi: 10.1145/3140587.3062372 Lopes, 2015Nuno P. Lopes, David Menendez, Santosh Nagarakatte and John Regehr. 2015. Provably correct peephole optimizations with alive. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2015. ACM, 22--32. doi: 10.1145/2737924.2737965 Riddle, 2021River Riddle. 2021. PDLL: a new declarative rewrite frontend for MLIR. (November 2021). Retrieved on 13/01/2025 (RFC on Discourse) from https://discourse.llvm.org/t/rfc-pdll-a-new-declarative-rewrite-frontend-for-mlir/4798.

Peephole optimisations are local transformations of the IR, based on the heuristic that local optimisations to the program will produce a well-optimised result overall. The principle is very simple: a sliding window traverses the IR and considers a few operations at a time. Once established which peeophole optimisations would apply on the current window, one optimisation is selected and applied. Finally, the result obtained is used to replace the operations within the window. We refer to classical compiler literature, e.g. Muchni., 2007Steven S. Muchnick. 2007. Advanced compiler design and implementation ([Nachdr.] ed.). Morgan Kaufmann, San Francisco, Calif. [u.a.], for more details.

Quantum compilers adopted peephole-style optimisations from the beginning Cheung, 2007Donny Cheung, Dmitri Maslov and Simone Severini. 2007. Translation techniques between quantum circuit architectures. In Workshop on quantum information processing, 1--3 Steiger, 2018Damian S. Steiger, Thomas Häner and Matthias Troyer. 2018. ProjectQ: an open source software framework for quantum computing. Quantum 2 (January 2018, 49). doi: 10.22331/q-2018-01-31-49 Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92. In fact, they encompass some of the most common optimisations in quantum computing, including the Euler Angle reduction Chatzi., 2009K. Ch. Chatzisavvas, G. Chadzitaskos, C. Daskaloyannis and S. G. Schirmer. 2009. Improving quantum gate fidelities using optimized Euler angles. Physical Review A 80, 5 (November 2009, 052329). doi: 10.1103/physreva.80.052329, the two-qubit KAK decomposition Tucci, 2005Robert R. Tucci. 2005. An Introduction to Cartan's KAK Decomposition for QC Programmers. arXiv: quant-ph/0507171 [quant-ph] Cross, 2019Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation and Jay M. Gambetta. 2019. Validating quantum computers using randomized model circuits. Physical Review A 100, 3 (Septempter 2019, 032328). doi: 10.1103/physreva.100.032328 and all gate set rebases contri., 2025TKET contributors. 2025. Documentation: pytket.passes.AutoRebase. Retrieved on 13/01/2025 (TKET docs) from https://docs.quantinuum.com/tket/api-docs/passes.html#pytket.passes.AutoRebase. A quantum-specific flavour of peephole optimisation, template matching Maslov, 2008D. Maslov, G.W. Dueck, D.M. Miller and C. Negrevergne. 2008. Quantum Circuit Simplification and Level Compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 3 (March 2008, 436--444). doi: 10.1109/tcad.2007.911334 Iten, 2022Raban Iten, Romain Moyard, Tony Metger, David Sutter and Stefan Woerner. 2022. Exact and Practical Pattern Matching for Quantum Circuit Optimization. ACM Transactions on Quantum Computing 3, 1 (January 2022, 1--41). doi: 10.1145/3498325, achieved state of the art results for Clifford circuit optimisation Bravyi, 2021Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu and Dmitri Maslov. 2021. Clifford Circuit Optimization with Templates and Symbolic Pauli Gates. Quantum 5 (November 2021, 580). doi: 10.22331/q-2021-11-16-580. Recently, quantum peephole optimisations were also proposed that leverage provable state information to perform contextual optimisations Liu, 2021Ji Liu, Luciano Bello and Huiyang Zhou. 2021. Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits. In 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), February 2021. IEEE, 301--314. doi: 10.1109/cgo51591.2021.9370310, similar to strength reduction and optimisation with preconditions in classical compilation Lopes, 2015Nuno P. Lopes, David Menendez, Santosh Nagarakatte and John Regehr. 2015. Provably correct peephole optimizations with alive. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2015. ACM, 22--32. doi: 10.1145/2737924.2737965.

There have further been advances in the theoretical underpinnings of peephole optimisations for quantum optimisation: Clement et al recently presented the first complete equational theories for quantum circuit Cléme., 2023Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix and Benoît Valiron. 2023. A Complete Equational Theory for Quantum Circuits. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), June 2023. IEEE, 1--13. doi: 10.1109/lics56636.2023.10175801 Cléme., 2024Alexandre Clément, Noé Delorme and Simon Perdrix. 2024. Minimal Equational Theories for Quantum Circuits. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, July 2024. ACM, 1--14. doi: 10.1145/3661814.3662088, proving that for any two equivalent quantum circuits there is a sequence of local transformations that rewrite one into the other. In other words, it is in principle possible to achieve optimal circuit compilation using peephole transformations only.

Peephole optimisation is fast, general and scalable. However, its performance is heavily dependent on well-designed heuristics and may vary widely across input programs. This is often refered to in compiler research as the phase ordering problem Click, 1995Cliff Click and Keith D. Cooper. 1995. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems 17, 2 (March 1995, 181--196). doi: 10.1145/201059.201061​: whenever a compiler can rewrite code in more than one way, it must decide which transformations should be applied and in which order, to obtain the most optimised result Whitfi., 1997Deborah L. Whitfield and Mary Lou Soffa. 1997. An approach for exploring code improving transformations. ACM Transactions on Programming Languages and Systems 19, 6 (November 1997, 1053--1084). doi: 10.1145/267959.267960 Liang, 2023Youwei Liang, Kevin Stone, Ali Shameli, Chris Cummins, Mostafa Elhoushi, Jiadong Guo, Benoit Steiner, Xiaomeng Yang, Pengtao Xie, Hugh Leather and Yuandong Tian. 2023. Learning Compiler Pass Orders using Coreset and Normalized Value Prediction. In Proceedings of the 40th International Conference on Machine Learning. JMLR.org. doi: 10.48550/ARXIV.2301.05104. This issue is also a key challenge within quantum compilation: unitary sythesis tools can sometimes outperform current, mostly peephole-based compilers Sivara., 2020Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington and Ross Duncan. 2020. t|ket⟩: a retargetable compiler for NISQ devices. Quantum Science and Technology 6, 1 (November 2020, 014003). doi: 10.1088/2058-9565/ab8e92 by up to 50%⁵ Wu, 2020Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong and Costin Iancu. 2020. QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis. arXiv: 2012.09835 [quant-ph].

We come away from our review having explored two competing worlds. On the one hand, using custom quantum-specific program representations, it is possible to capture quantum semantics precisely and enable global program transformations. On the other hand, one can rely on standard compiler techniques and its dedicated mature infrastructure to drive scalable and extensible quantum optimisation techniques. So far, the latter has always come at the cost of some performance, making tailored solutions the preferred approach.

We argue that going forward, however, the scaling and engineering challenges that will come with building out custom compiler tooling will prove difficult, given the large variations in quantum architectures and the unavoidable integration with classical hardware such as CPUs, GPUs and FPGAs. The remainder of this thesis presents contributions that aim to close the gap in performance, so as to enable state of the art compilation of large scale, hybrid quantum classical programs based on standardised IR formats.

Before proceeding with that, however, we propose one more section reviewing past work. It focuses on two advanced classical compilation techniques that form the foundation of the quantum compiler architecture we will propose in chapter 4.

←Return to chapter