Quantum Circuit Optimization Techniques: A Literature Survey

In this review, we focus on various mathematical aspects of QC synthesis and optimization techniques relevant to the Noisy Intermediate-Scale Quantum (NISQ) era devices. We avoid physical aspects of circuit implementation unless they are relevant to the corresponding mathematical problem stated in the paper. Both heuristic and rigorous techniques are studied.

We included journal articles and conference proceedings papers relevant to the review question, based on the content of the paper. The papers primarily dealing with physical aspects of the circuit synthesis/optimization were excluded unless the corresponding mathematical result relevant to the review question had been significantly elaborated therein. Similarly, relevant papers from closely related fields (such as reversible circuit synthesis) were included if the contents of the paper had significant focus on quantum aspects. Multi-valued quantum logic (qudits) was mostly excluded.

The papers related to optimization of generic (theoretic) QC or those running on quantum hardware were included unless the focus was on some hardware specificity (e.g., papers optimizing QC fidelity by scheduling optimization were excluded), or the optimization was related to a specific class/circuit. We excluded papers relevant to parametrized QC, especially those related to variational optimization approaches, e.g., variational quantum eigensolver (VQE) or quantum approximate optimization algorithm (QAOA), due to ambiguity in the naming (optimization here was the type of operation that was done by this particular class of QC in hybrid computing). Optimization for simulation, both quantum simulation and simulation of a QC on classical hardware (including e.g. optimization of tensor network structure) were excluded.

Papers related to optimization of a particular circuit were mostly excluded because of the lack of generality. For the same reason, we excluded most of the papers related to QC layout/mapping problems (most of them were related to specific hardware), unless a generic circuit or generic method was considered (e.g., mapping as a part of QC transpilation).

Papers dealing with quantum machine learning were excluded, and this field is an interesting but rather separate branch of research. In a similar manner, we excluded distributed quantum computing and QC approximation-related optimization (e.g., by the unitary matrix approximation or by Monte-Carlo techniques). The decision for the papers related to the QC compilation or QC synthesis was made individually, according to the content of the article.

To gather the literature body, we used a hybrid search strategy that combines the following three steps.

Keywords search was performed by means of indexing systems: Web of Science, Scopus, Crossref and Google Scholar. The relevant keywords were “quantum circuit optimization” and “quantum circuit synthesis”. Filtering was performed by manual exclusion based on the abstract and/or content of the paper.

Snowball search was used to extract relevant papers from the references of the corresponding literature body obtained at other stages.

Data clearance was done to avoid repetitions if a series of papers (say, a conference paper and an extended journal paper) was identified; the extended/more recent item was kept in the literature body. We deliberately decided to exclude PhD theses since those are to be based on the formally published results in the form of articles.

The literature used in this review was published up to 2025. This review is based on 179 articles [1–179], which have been published in relevant journals, conference proceedings, and open sources such as ArXiV. In a few cases, when a conference (short) or unpublished (say, ArXiV) version of the article was available together with the journal (complete) or published version, we included the latter only. With similar motivation, we deliberately excluded theses, say [180–188], since those results are to be available in articles.

To make this summary complete, we mention a few interesting articles that contain various circuit optimization techniques but are out of scope due to the inclusion/exclusion criteria selected. These are: a fundamental paper by A. Yu. Kitaev on the factorization problem, where an extension of Shor’s results was done [189]; C. Jones’ method for optimizing the Toffoli gate [190]; optimal small circuits generation paper [191], to name a few.

Finally, we mention several fundamental books relevant to the subject [192–194].

It is important to mention a review paper [195]. Here, the authors characterize existing methodologies and open problems of reversible circuit synthesis. They survey papers devoted to reversible logic, not only to QC. The background on reversible logic and QC is given, followed by a comparison of these types of circuits. Existing physical implementation approaches are also concerned.

The authors provide a detailed general description of representation models, optimization criteria, and optimization techniques. Compared to our review, they highlight less representation models and optimization criteria, but they pay attention to limitations of the approaches. This review is based on 15 papers. The authors explain the existing benchmark families, their functionality and purpose.

The list of open problems of state of the art of reversible circuits synthesis is also formulated; e.g., they note that technological mapping is proposed only for specific applications and the number of elementary gates could be estimated more precisely.

Another relevant survey is [196]. This paper is dedicated to comparative practical analysis of evolutionary algorithms, which are used for reversible circuit synthesis. In contrast to [196], we do not perform numerical experiments and study implementation aspects; however, we focus on mathematical aspects and study the problem in a broader sense.

While a revision of this article was prepared, a survey paper on the topic of QC optimization [197], which covers a wide range of hardware-related and hardware-agnostic techniques, was published. Compared to those, we are targeting the mathematical problems/techniques related to QC optimization rather than optimization approaches, and in the present article, the literature body is wider.

In this section, we summarize the models that are behind the corresponding circuit synthesis and optimization techniques. We note that there is a significant heterogeneity in the descriptions below: the items in the list correspond both to the mathematical models that are used for optimization or synthesis purposes and to the models used for, say, representation of a circuit (e.g. graph models). These may coincide, i.e. the commonly used gate sequence representation of the circuit may be transformed into the unitary matrix useful for the optimization algorithm and vice versa. Thus, a single paper may appear in several items of the list if the corresponding models are utilized therein. Sometimes we also highlight the specific mathematical problem that is used in the optimization phase.

It should be noted that the optimization technique may also work with the original circuit representation, which is common for, say, template optimization techniques (the techniques and methods are discussed in Section 3.3). To facilitate understanding, we refine the circuit type (and hence, architecture and/or the elementary gate set) used if it is the key target of the paper.

In this work, we consider an n-qubits circuit. Researchers consider QC from different points of view and different restrictions. We collect these models in groups and present them in the following list.

Standard QC

• –

  Circuit as a Sequence of gates. This is the most common representation allowing one to directly use the quantum program and apply optimization techniques such as pattern matching. Researchers also use the following approaches to improve the optimization results.

  • *

    Parallel algorithms [109] to improve the runtime of the circuit synthesis.

  • *

    Splitting the circuit. The researchers first split the circuit into big blocks and optimize them, then optimize each block independently [168].

  • *

    The circuit can be presented as a ZX-diagram, and researchers use the tensor network-like structure to optimize it [93].

  • *

    Isometry based representation [128].

  Furthermore, graph models are frequently used to state the corresponding mathematical problem. These can be

  • *

    Based on the generic dependency graph [70,122] or the logical data precedence graph [78].

  • *

    Based on qubit line adjacency graph [118].

  • *

    Multi-commodity network flow problem in a staged digraph where nodes at each stage correspond to computational basis states, arcs between stages correspond to gates and costs are defined at gate level and commodities representing output rows in truth table [89].

  Some researchers [60,104,118,139,152,159,168,169] suggested heuristic procedures to minimize the number of gates for noisy models.

  Other researchers optimize circuits from the depth point of view. The authors of [12,30] used meet-in-the-middle technique and another expectational time techniques [74] to improve the search algorithm.

  It is known that increasing the ancilla qubits allows us to get better results. The discussion of a trade-off between the number of ancilla qubits and the number of gates can be found in [105]. When we develop a QC, not only decomposition of an arbitrary unitary is important, but also the decomposition of the main and most expensive parts of the circuit. Optimization of the implementation of Multi-control Toffoli gates can be found in [15]. Optimization of the implementation of Multi-control rotation gate can be found in [198,199]. At the same time, the presented technique requires good precision of the rotation gates. The trade-off between precision and the number of CNOT-gates is presented in [200,201].

  Among the classes of QC considered, one should also mention the ones having probabilistic structure, such as the so-called repeat-until-success circuits [19,45].

• –

  Naturally reversible, QC that provide boolean output for boolean input can be considered as Reversible logic circuits (aka reversible Boolean circuits/reversible circuits). Being a subset of QC that essentially performs the permutation of a boolean input, these allow one to use corresponding representations such as multiple control Toffoli [111,139] to optimize them, say, by the rewrite rules [105]. Another options would be to use some equivalent algebraic construction and corresponding apparatus, such as the so-called positive Davio lattice [100], binary decision diagram [81,161], exclusive sum of products [36,79], Kronecker functional lattice diagram [100], cycle-based permutation representation [7,178], graph based algorithms and data structures [125], Toffoli networks [106], to name a few.

• –

  Nearest neighbor (NN) circuits. Many types of quantum computers (for example, quantum devices based on superconductors) do not allow us to apply two-qubit gates to an arbitrary pair of qubits but have a graph that represents such a restriction. It is called a qubit connectivity graph. Vertices of the graph correspond to qubits, and two-qubit gates can be applied only to qubits corresponding to vertices connected by an edge. We say that such a graph represents the qubit topology for a device. The most simple connectivity graph is a chain, where all qubits are presented as a line, and each qubit can interact only with the next and the previous qubits. This architecture is called Linear Nearest-neighbor (LNN) or one-dimensional Nearest neighbor (1D NN) architecture. Mottonen et. al. [198] suggest a method to represent any unary transformation using only 1.5 times more gates, comparing to the circuit without restrictions on graph connectivity. The result for an arbitrary qubit connectivity graph is based on similar results for the uniformly controlled rotation gate [202,203].

  Different heuristics approaches for mapping a circuit to the LNN architecture can be found in [28,41,95,166,178] and using specific strategies [3,6,9,10,18,50,87,138]. One of the algorithms that are used for optimizing a circuit for the LNN architecture is A*. The authors of [22,138] used it to find the best permutation of the qubit order that allows us to minimize the number of gates in the case of the LNN architecture. Other researchers use the Minimum linear arrangement problem as a target problem for optimizing a circuit [1]. Interesting approaches include ones based on the Boolean satisfiability problem [138], pseudo-Boolean optimization [13], and integer programming [42].

  Other types of NN architecture were considered. In the case of a 2D grid, heuristic solutions and specific strategies were suggested [4,20,28,41].

  In the case of a 3D grid, heuristic solutions were suggested [11,13,41].

Circuit with Multi-qubit gates. Some types of quantum computers allow one to use Multi-qubit gates, that is why researchers optimize such circuits as well [14].

One-way quantum computation is a model of universal quantum computations in which a specific highly entangled state called a cluster state allows one to perform quantum computation by single-qubit measurements [8].

It can be seen that the circuit as a sequence of gates is the most widely used representation (e.g. [168]). This, however, restricts the possible methods, and the researchers imply other representations of the objects of interest to solve the optimization problems, such as graph-based [118], or matrix-based [119]. Furthermore, a few exotic examples include meta-optimization of the hyperparameters of the synthesis algorithm [169].

There are many simple and complex criteria used for QC synthesis and optimization. These usually are to be minimized (smaller-better) and most of them are motivated by some specific hardware requirements (e.g. the number of gates the machine can handle) or physical requirements (e.g. decoherence time of a qubit). Hereafter we summarize these, based on the literature considered, and discuss in brief their meaning accordingly.

Below we describe the simple (one-parametric) optimization criteria and give the references where corresponding criteria are used, including the cases when a specific criterion is used as part of a more complex one.

Depth of the circuit [12,30,31,57,65,68] that indicates the longest path from the input to the output of the circuit, which is inversely proportional to the coherence time (larger - better), including

• T-depth being the largest number of sequential T-gates in the circuit that cannot be conducted in parallel [2,17,119];

• Depth of measurement pattern being the maximum number of levels of operations for the execution of the pattern due to the dependencies of measurement and correction commands [8];

Gate count, i.e., the number of gates in the circuit [7,25,30,36,50,59,63,65,68,76,79,104,106,111,118,139,159,171, 178], including

• CNOT count, i.e., the number of CNOT gates in the circuit [16,60,87,128,136,140,142,168, 204] motivated by the fact that such gates are error-prone and this criterion is proportional to depth;

• SWAP count, i.e., the number of SWAP gates [1,3,4,6,9–11,13,18,20,22,28,41,50,95,166] widely used in architecture-specific (e.g. NN) circuit optimization;

• T-count i.e. the total number of T gates or Hermitian transposes of the T gate in a QC [2,5,19, 45,56,74,77,93,94,109,160] since such gates have significant resource cost;

• MS-count, i.e., the number of entangling Mølmer–Sørensen gates [14,130] which is important for the gate set used in the so-called trapped-ion technology;

• Hadamard count [94];

• Primitive quantum one-qubit and two-qubit gate count [12];

• Elementary one-qubit gate count [115];

Cost, including

• Two-qubit cost i.e. the number of two-qubit gates [105] and named as the number of entanglements in a pattern required to be applied at the beginning to produce the cluster (highly entangled) state in [8];

• Quantum cost being the number of basic quantum gates required to implement the given function [18,25,31,36,89,100,125,137,138,152,161,165];

• Interaction cost [31] and, specific to the NN architecture, the NN cost [3,138,167], being the sum of distances between gate qubits of any two-qubit gates;

• Clifford+T gate cost [17];

Number of lines in the circuit (where ancillae lines can be used) [15,150];

Number of ancillae lines [113];

Number of levels in the circuit meaning the number of sub-sequences of commuting gates that can be applied in parallel [104];

Size of pattern, being the number of qubits in a measurement pattern in one-way quantum computation [8];

In a few works, complex criteria were used such as:

• weighted additive inverse of errors and costs [99]: α(1−ErrorMaxError)+βCost,\alpha \left( {1 - {{Error} \over {MaxError}}} \right) + {\beta \over {Cost}},

Finally, a few works were focused on practical aspects of the implementation of the algorithms, such as:

• testcase-based empirical error [169];

• runtime [117], including synthesis time [65,81];

• memory consumption [117];

• system size, or method scalability [122].

For various technologies, there are several bounds known on the optimization criteria for a generic circuit. We summarize a few sources on these in Appendix 3.

It is also interesting to note that due to diverse perspective architectures studied in the literature, specific criteria used are sometimes more common for specific architectures, e.g. SWAP count is common for the NN architecture, whereas MS-count is typical for trapped-ion technology.

In this section, we summarize the optimization methods used in the reviewed papers. In general, there are two basic options to synthesize optimized circuits: either by using the exact method (which guaranties to find a global minimum) or by using some (meta) heuristic approach to obtain nearly optimal solution. However, even the exact optimization method, while delivering the global minimum for the given optimization criterion, may synthesize the circuit that differs from the original (unitary operator) with a given tolerance (we elaborate more on this quality evaluation issue in Appendix C). As such, both synthesis options are equally valuable from the point of view of solution quality.

In the list below we structure the papers according to the more general procedure names, and give more details in the summary table.

• Rewrite rules/templates based simplification (usually performed in a greedy way) [36,50,63,93,104–106,111,118,125,138,169], in particular,

  • –

    enhanced with cost metric evaluation [3,9];

  • –

    randomized [169];

  • –

    based on specific properties of generalized Toffoli gates [140] or Toffoli gates with multiple target lines [165];

  • –

    using negative and positive control lines in CNOT [152];

  • –

    enhanced with reinforcement learning [68];

  • –

    used in exhaustive search to construct a database of circuits [19];

  • –

    including the lines reordering [11,138,167] and ancillae adding [105];

  • –

    reduction rules (simplification, interchanging, and commutation) [12] including relative phase gate substitutions [56];

  • –

    peephole optimization [48] including relaxed peephole [98];

• Heuristics [65,68,87,118,119]

  • –

    using properties of the so-called ∈-nets in Solovay–Kitaev algorithm implementation [12,117];

  • –

    based on functional diagram dependency matrices (local and global) [150];

  • –

    based on A* search [7,22,59,60,168,204];

  • –

    based on subtree-to-gate mapping lookup table [81];

  • –

    based on decomposition and symmetry rules [100];

  • –

    based on operating with total Hamming distance [171];

  • –

    lookahead-based [1,10,95];

  • –

    graph partitioning [6];

  • –

    based on qubit count [20];

  • –

    based on preference index of qubits [4];

  • –

    Skipping Table Algorithm [12] that skips redundant sequences to speed up the exhaustive search;

• Metaheuristics based:

  • –

    genetic algorithms for circuit synthesis [11,25,99,139,159];

  • –

    Harmony search with local optimization of SWAP gate insertion [28];

  • –

    graph traversal by ant colony [41];

• Decomposition based schemes [15,94,128,137], in particular, based on the cosine-sine decomposition [8, 136,142], quantum Shannon decomposition [8,136], multiobjective QC decomposition [8];

• Numerical optimization [65], including gradient-based optimization [130] and Quasi-Newton method of Broyden, Fletcher, Goldfarb, and Shanno (BFGS) [14];

• Sequential generation (with error correction) of sub-circuits returning the desired result with high probability in exponential [19] or polynomial [5] time, or with a fixed (given) number of steps guaranteed by ’fallback’ circuit [45], and using such a method as a framework for nonlinear arithmetics [160];

• Cycle-based permutation representation: optimized using total Hamming distance [178], bin packing problem for cycle distribution among the available registers [31], using A* search [7];

• Boolean satisfiability based [76,77,167], in particular, Pseudo-Boolean optimization (PBO) [13,166];

• Large-scale approaches, including hierarchical synthesis of QC [122] and circuit partitioning [65,168];

• Meet-in-the-middle [30,74,109];

• Multi-commodity Network flow combined with arc-subset selection problem [89];

• Variational hybrid quantum-classical approach with quantum cost evaluation [57];

• Exhaustive search with speedup using heuristic search tree pruning [79], rules-based substitutions [161];

• Positive Davio Lattice Diagram construction [18];

• SWAP insertion methods [20];

• Global consideration of transformation matrix [17];

• Matroid partitioning algorithm [2];

• Steiner tree problem [16];

It is important to mention that in some papers the optimality of some circuit may be given by design of the corresponding synthesis method, e.g.

• in [76] the corresponding SAT problem gives a solution (i.e. the function is SAT), if there exists a circuit of a given (fixed) depth d, and thus optimality is obtained by solving a number of problems with increasing d;

• in [45] the so-called probabilistic QC with fallback consists of a finite (fixed, given) number of subcircuits followed by a fallback circuit (the last step is offered with small probability) with a given precision and low (average) cost;

• in [14], the solution is obtained in an iterative way by increasing the target (number of entangling gates) sequentially, and thus obtaining the minimum.

We note that among the benchmarks used, a few are relatively popular between researchers, these include

RevLib, the benchmark for reversible functions, including the QC [205], http://revlib.org/;

Maslov, Reversible logic synthesis benchmark page by D. Maslov, available at http://www.cs.uvic.ca/dmaslov/ since 2002, and the new version available at https://reversiblebenchmarks.github.io/.

LGSynth, one of the benchmarks available at https://ddd.fit.cvut.cz/www/prj/Benchmarks/.

optimizer, Benchmark QC before and after optimization available at https://github.com/njross/optimizer, using techniques from [118],

RevKit, a toolkit for reversible circuit design, available at http://www.revkit.org,

Cirq, available at https://github.com/quantumlib/Cirq.

We also mention a few synthesis/optimization tools that were introduced or used in the corresponding papers.

BayeSyn synthesizer [169] - QC generation by high-level languages (C or C++) framework implementation via stochastic synthesis;

QFAST package for Python [65];

pQCS written in C++11 [109];

RMRLS written in C [79];

QULASYN [18];

Revkit https://github.com/msoeken/revkit used in the paper [161].