←Return to chapter

2.2. Quantum circuit optimisation: a review

Much of the foundations of classical computer science rely on boolean logic and discrete mathematics Lehman, 2017Eric Lehman, F. Thomson Leighton and Albert R. Meyer. 2017. Mathematics for Computer Science. Samurai Media Limited. In some regards, this is a poor man’s maths, as much of the structure that comes with continuous infinite mathematical objects is lost along the way when discretised.

In contrast, quantum computation, on the other hand, encompasses the whole breadth of (finite dimensional) quantum physical system evolution. Underlying this is a rich mathematical theory steeped in the theory of Hilbert spaces and Lie groups¹. A direct consequence of the mathematics of quantum computations is the flourishing of an entire field of research dedicated to quantum circuit 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. They leverage the unique structure and symmetries of quantum physics to reduce the noise and resource requirements of quantum computations significantly.

In this section, we will review the main optimisation techniques that established themselves within quantum compilers, focusing on the representation of quantum computations they use and their assumptions about the computations they are optimising.

Cost function #

A key point to settle first when discussing circuit optimisations is the objective of the optimisation – the cost function to be minimised. Unlike much of classical compiler research, which can rely on an established set of hardware targets and benchmarking datasets to profile the empirical, “real world” performance of compiled programs, the quantum world must often contend with simplified noise and architecture models to design proxy metrics, given the limited scale and availability of current quantum devices.

The quantum compilers research community has mostly coalesced 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. In spite (or precisely because) of their simplicity, gate counts serve well as cost functions in many quantum compilation use cases. Most circuit optimisations target one of two hardware regimes.

On most current hardware architectures, the major challenge is achieving 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 and et al. 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. In superconducting qubit and ion trap architectures², for example, the gate set is typically composed of one and two-qubit gate types, with error rates dominated 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. Circuit optimisations for computations on such noisy hardware thus often define cost functions based on the number of two-qubit gates – typically the $\mathit{CX}$ gate, though many other two-qubit gates could be used equivalently.

On the other hand, future generations of hardware for larger scale computations are expected to be more resilient to noise, with the help of error detection and correction techniques. In this regime, the computational power of the hardware is no longer limited 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 straightforward and nigh-impossible. The bottleneck is widely expected to be the execution of single-qubit (non-Clifford) gates, such as the $\mathit{T}$ gate³. These cases can thus just as well be modelled by cost functions based on gate counts.

Unitary synthesis: the perfect optimisation #

The ne plus ultra of quantum circuit optimisation is unitary synthesis. It leverages the representation of a quantum computation as a square, complex-valued, unitary matrix, which is then re-synthesised as a new, equivalent (and ideally 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 matrix decomposition into primitive quantum gates, thus obtaining a new quantum circuit, equivalent to the original.

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 distance metric on the space of all circuits, in the form of the Haar measure. This can be used in search-based approaches to measure the distance between synthesised circuits and thus direct a search heuristic towards the optimal solution.

Early work explored general unitary decomposition schemes obtained analytically from linear algebra. These express arbitrary unitaries as 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 have been proposed 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. While some schemes have been shown to be asymptotically efficient for almost all unitaries 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, 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 synthesis (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'$.

Search-based approaches have been developed to address the shortcomings of analytical decompositions. Unlike the algebraic approaches, the circuit decomposition problem is viewed as an optimisation problem in search-based circuit synthesis. 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 struggles 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. Asymptotic bounds on the number of T gates required for general unitary synthesis were recently given in Gosset, 2024David Gosset, Robin Kothari and Kewen Wu. 2024. Quantum state preparation with optimal T-count. arXiv: 2411.04790 [quant-ph].

Scaling to 4 qubits and handling 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. This approach’s outputs are no longer provably optimal, but the results match optimal decompositions in all known instances. This line of work has subsequently been 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 can 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 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/. Circuit synthesis schemes have also been extended to generate circuits on a more expressive gate set, including elementary classical operations 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].

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 such as 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 effectively circumvent the problem, but they are heavily dependent on the partitioning quality.

The search for scalable representations #

Our study of unitary synthesis introduced us to a convenient two-step approach to quantum computation optimisation. First, the input circuit is transformed into a “global” representation that captures the computation as a whole, abstracting away the precise sequences of gates that compose 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 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 quantum computations require exponential space to be described in the worst case – after all, the space of all $n$-qubit unitaries $SU(2^n)$ is exponentially large. However, the set of unitaries implementable in practice can only be a tiny subset of $SU(2^n)$⁴ – the set of unitaries that admit a polynomial-sized circuit representation.

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 circuits 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

where $\alpha_s \in \mathbb [0, 2\pi)$ are real coefficients and $s \in P = \{I, X, Y, Z\}^n$ are strings of length $n$ of the four Pauli matrices – so-called Pauli strings. In this formulation, $n$ fixes the number of qubits of the computation.

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

is a valid quantum computation on 3 qubits, entangling the first and third qubits. Beyond useful abstractions for optimisation, such entangling operations appear naturally when simulating quantum systems, for example in quantum chemistry McClean, 2016Jarrod R McClean, Jonathan Romero, Ryan Babbush and Alán Aspuru-Guzik. 2016. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics 18, 2 (February 2016, 023023). doi: 10.1088/1367-2630/18/2/023023.

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 are also taken into account to produce programs that can be executed on the targeted architecture without overhead.

A close relative of Pauli gadgets – a strictly 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 to combinations of Z Pauli matrices and identities: $s \in \{I, Z\}^n$ . These are particularly amenable to optimisation as in this case, the ordering of the gadgets becomes irrelevant – all exponential terms commute. This gives the compiler a lot of freedom during circuit synthesis.

The action of phase polynomials on quantum states is 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. A quantum basis state – just like a classical state – is given by a bistring $b_1 \cdots b_n$ of bits $b_i \in \{0, 1\}$. Writing $e_{b_1 \cdots b_n}$ for the basis state corresponding to the bitstring $b_1 \cdots b_n$, the action of a phase polynomial $U$ on $e_{b_1 \cdots b_n}$ is given by

where $\tilde{s}_1 \cdots \tilde{s}_n$ is now also a bitstring of booleans $\tilde{s}_i \in \{0, 1\}$, and $\oplus$ denotes the boolean XOR operation. The boolean $\tilde{s}_i$ has value $1$ if and only if the $i$-th character in the Pauli string $s$ is $Z$,

The exponential expression in (1) is just a real number – indeed each term in the sum simply evaluates to either $a_s$ 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$ non-zero terms $a_s \neq 0$, 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 made by its authors is 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 translates into a single two-qubit $\mathit{CX}$ gate when synthesised to a quantum circuit by 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 the 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 and their implementation were 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 and, where available, additional qubits as ancilla registers to parallelise computations further 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.

The Clifford subgroup of quantum circuits admits an efficient $\Theta(2n^2)$-sized program representation known as 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. This has been used profusely for compiler optimisation. 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 Maslov, 2023Dmitri Maslov and Willers Yang. 2023. CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate. npj Quantum Information 9, 1 (Septempter 2023). doi: 10.1038/s41534-023-00760-2.

Just as in unitary synthesis, circuit decompositions of Clifford operations more efficient than the general analytical expressions can be obtained case-by-case 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 have a rich history in diagrammatic representations Feynman, 1949R. P. Feynman. 1949. Space-Time Approach to Quantum Electrodynamics. Physical Review 76, 6 (Septempter 1949, 769--789). doi: 10.1103/physrev.76.769 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 one to picture complex physical processes as intuitive operations in a graphical language and have – as a nice side effect – led to a plethora of state-of-the-art quantum circuit optimisation techniques!

A diagrammatic representation of 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 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 significant contribution of these diagrammatic representations is the introduction of graph transformation systems (GTS) 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. More on this in chapter 3 (and much of the rest of this thesis)!

Reversible classical circuits #

Many more representations have either been taken over from classical compiler optimisations or were developed for specific purposes. The last we will mention is reversible circuit synthesis, an entirely classical circuit design problem which can draw from the 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 complex phase 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 fast circuit synthesis of 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 in which the problem was studied initially. This affords additional freedom for decomposition schemes, such as decompositions of $\textit{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 $\mathit{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-$\mathit{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, 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 cornerstone 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.

←Return to chapter