Quantum Circuit Optimization Techniques: A Literature Survey

Mariia Makarova; Davide Pastorello; Valter Cavecchia; Enrico Blanzieri; Kamil Khadiev; Alexander Rumyantsev

doi:10.2478/qic-2026-0008

1. Introduction

Quantum technologies are currently under the spotlight of scientific and industrial communities for their disruptive potential in outperforming classical solutions of information processing. In particular, there is intense research activity towards scalable quantum computers with promising results. The technical challenge of providing large-scale, fault-tolerant, programmable quantum hardware must be accompanied by a relevant effort in developing suitable mathematical techniques aimed at making the implementation of quantum algorithms as efficient as possible.

Quantum circuits (QC) provide a universal model for quantum computation in terms of sequences of elementary quantum gates on qubit registers that are, mathematically, unitary operators on Hilbert spaces. Quantum algorithms are typically expressed in terms of QC assuming the availability of a set of elementary gates. The problem of QC synthesis is basically given by the quest of constructing a QC implementing a given algorithm. Moreover, in general, there are several ways in composing quantum gates for the implementation of the algorithm, then a remarkable task, say QC optimization, is finding the less expensive implementation in terms of available resources, according to some criteria.

In this paper, we survey the literature related to QC optimization. Instead of formalizing the notions and giving some background on quantum computing (these tasks are done in the Appendices), in Section 2 we define the review question, inclusion/exclusion criteria, and search strategy of the papers to be reviewed. As a result of strategy implementation, a systematic analysis is provided over 179 papers. To perform the analysis, in Section 3 we describe the dimensions: optimization models, criteria, and methods, and support the taxonomy with illustrative examples. A concise stratification is done in a summary table, which is located on a shared cloud resource due to size constraints. The survey is intended to be a guide to the relevant literature in the research area. We finalize the paper with a conclusion.

2. Methodology

In this section, we summarize the key settings of this survey paper, characterize the literature body, and perform a comparison to relevant reviews available in the literature. The notions used hereafter are explained in the Appendices in more detail.

2.1. Focused Review Question

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.

2.2. Inclusion/Exclusion Criteria

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.

2.3. Search Strategy

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.

2.4. Literature Body Characteristics

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].

2.5. Relevant Surveys

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.

3. Literature Review

In this section, we structure the literature body on the basis of several important characteristics: optimization model used (Section 3.1), optimization criteria (Section 3.2), and optimization method (Section 3.3). Details on quality evaluation, if applicable, are given in Appendix 3. When introducing or discussing related entities, we cite the corresponding papers where such a model or criterion was used, to illustrate the taxonomy. Note that these citations are not intended to be exhaustive and serve as examples. A complete, ordered list of papers and their descriptions is given in the summary table. Due to the huge size of the list of articles and in an effort to provide additional filtering capabilities, we decided to present the summary table as a separate document, available at https://docs.google.com/spreadsheets/d/13ZrxgFcxkCm4MiuQmZWeGxl9m2K0AoW_SZaq9AFYnpU/edit?usp=sharing.

3.1. QC Optimization Models

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].

3.2. Optimization Criteria

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 - \frac{E r r o r}{M a x E r r o r}) + \frac{β}{C o s t},$

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.

3.3. QC Optimization Methods

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.

3.4. Software and Benchmarks

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].

4. Discussion

A large number of reviewed papers deals with direct manipulation on the gates in circuit representation. In this case, the search space of the optimization coincides with the configuration space of the circuit itself. Not surprisingly, in this case the cost measures are mainly statistics computed on the circuit characteristics like depths, gate (or specific gate) counts and quantum cost. Exceptions use testbase empirical error [169].

Some of the papers are targeting architecture-specific NN circuits that are relevant to the commonly used NN architecture. Note also that while the majority of the papers are optimizing circuits of finite length, a few circuits are by design non-deterministic and possibly have infinite length, such as the RUS circuits [19]. This opens a way to studying the convergence of circuit optimization algorithms.

The most original and promising papers, however, are the ones in which a different representation is chosen in order to perform the optimization. In this case, we appreciate from our analysis of the literature how diverse and wide the choice of representations can be. In this category of papers, the representation is usually chosen in a way to exploit an optimizer already developed for such a representation. Among the most popular representations of such a type are various graph models that allow one to use (classical) graph traversal/search algorithms and various (meta)heuristics.

Let us consider the tendencies that emerge over time. It is possible to see how papers that actually change the representation in order to perform the optimization appear in more recent years. Moreover, in recent years the comparison against an existing compiler has been more and more common. Surprisingly, even recent papers sometimes lack comparison with competitors and present just validation with simple circuits or against baselines.

It is also important to mention the relationship between optimization and compilation. It is reasonable that some sort of optimization can in principle be performed by the compiler. However, it is important to distinguish between the optimization process that we are considering and the compiler that have to take into account the actual physical architecture of the target machine. A successful proposal for the optimization could be included in a compiler but we argue, given that the QC research area is still relatively recent, research should be pursued separately.

It is worth to mention that no attempt has been reviewed to target QC for Quantum Machine Learning. In our opinion, an actual optimization of the circuit that takes the data into account could be an interesting prospective to take. In this regard, also the training of quantum neural networks represented in terms of parametric circuits can be meant as a circuit synthesis where a classical backpropagation can be used but also the parameter shift rule for differentiating the function implemented by the circuit and performing gradient descent can be implemented. Moreover it is worth to cite a couple of recent papers that go in the directions of integrating machine learning [68,169].

There seem to be no shared and commonly-adopted benchmarks, in fact is hard to rank the methods in a sensible way, because there are no shared state-of-the-art to compare against. Some exceptions, however, are the RevLib and Maslov benchmark sources. Still we see that it is becoming common to compare against compilers.

5. Conclusion

We have reviewed the papers that deal with mathematical aspects of quantum gates circuit optimization and synthesis. The area appears to be wide and diverse, with no shared benchmarks, representations, and an easy-to-identify stare-of-the-art approach. That makes the area interesting for research and possibly contributions. Moreover, we argue that it is still possible to work on optimization separately from the actual practical implementation of a quantum compiler.

We expect that the research area of QC optimization will eventually meet the trend of application of machine learning techniques as deep learning to the optimization process itself. Moreover, we also expect the development of optimization specific techniques devoted to QML algorithms. As argued in this review, optimization techniques are central in QC synthesis processes. In a natural way, the seek of an optimized QC implementing a given computation can be cast into the training of a machine learning model. In this sense, classical algorithms of machine learning can be applied to learn a synthesis process, for example adapting QC belonging to a given collection. An instance-based learning approach can be adopted where the synthesis is carried on from a training set of QC which have already been synthesized. An example of this approach is given in [206], where a hybrid quantum classical algorithm is proposed, in which the runs of an adiabatic quantum computer are iterated in order to find a representation of a given optimization problem in a Hamiltonian operator.

Another possibility that we foresee is the actual application of specific-purpose machines like quantum annealers to the actual task of QC optimization. If the QC synthesis can be formulated in terms of a combinatorial optimization problem, one can suppose to exploit quantum resources to accomplish the task. A few research papers are targeting this direction, e.g., [207]. Being formulated in QUBO form, the problem may be solved by, the quantum approximate optimization algorithm (QAOA) on a gate-based machine, but also runs on a quantum annealer can be considered for an efficient QC optimization.

The limits of the current quantum machines are such that an optimization step will be probably proved to be necessary in order to bridge the gap between theoretical quantum algorithms and practical implementations. To this end the characteristics of the hardware will dictate which will be the cost functions to be optimized, and optimization will be included eventually in any architecture-specific compiler. The development of standard and shared benchmarks could accelerate the development of techniques and the emergence of a recognizable state of the art. Moreover, multiobjective optimization has not been fully addressed yet in this realm. These circumstances make the optimization of QC an interesting and important field of research in the near future.

Acknowledgments

The work has been supported by the Q@TN consortium. We thank the referees for their constructive criticism that helped us complete this work.

Notes

[1] Contributed by Author Contributions

Conceptualization, M.M., E.B. and A.R.; M.M. and A.R. collected the metadata; M.M., E.B., A.R. and K.K. analyzed and interpreted the results found in the literature; M.M., E.B., A.R., K.K., D.P. and V.C. wrote the paper; edited the paper and reviewed the drafts. All authors have read and agreed to the published version of the manuscript.

[2] Conflicts of interest Conflicts of Interest

The authors declare no conflicts of interest.

[3] Data Availability Statement

No new data were created during this study.

Appendices

Appendix A. Quantum Computing Basics

Within this section, well-known material on quantum computing is briefly explained, for an explicit source see e.g., [193]. In applications, often Dirac formalism is adopted, and the so-called “bra-ket” notation used. This means that |ψ〉 is the column vector and 〈ψ| is the conjugate row vector in a (finite dimensional) Hilbert space ℋ that is a complex vector space equipped with an inner product 〈 | 〉. The physical states of a quantum system are represented by the positive linear operators on ℋ with unit trace called density matrices. The set of density matrices:

A1

S (ℋ) = {ρ \in ℒ (ℋ) : ρ \geq 0, tr ρ = 1},

where ℒ(ℋ) is the space of linear operators on ℋ, is convex and its extreme elements are the 1-dimensional orthogonal projectors ρ = |ψ〉〈ψ| with ∥ψ∥ = 1, called pure states. Therefore, the pure states are in one-to-one correspondence to the projective rays of ℋ then a pure state can be completely represented by a normalized vector |ψ〉 ∈ ℋ up to a multiplicative phase factor. The mixed states are density matrices given by convex combination of pure states, i.e. elements in 𝒮(ℋ) that are not pure. Without explicit specifications, we deal with pure states.

A qubit is any quantum system described in a 2-dimensional Hilbert space, it turns out to be a quantum analog of a bit in binary logic. The special symbols |0〉 and |1〉 correspond to the computational basis states of a two-state qubit system and are given as

| 0 〉 = [\begin{array}{l} 1 \\ 0 \end{array}], | 1 〉 = [\begin{array}{l} 0 \\ 1 \end{array}] .

Any qubit state |ψ〉 is a superposition of the states |0〉 and |1〉, meaning that

| ψ 〉 = α | 0 〉 + β | 1 〉 = [\begin{array}{l} α \\ β \end{array}], α, β \in ℂ, | α |^{2} + | β |^{2} = 1.

The components, called amplitudes, of a qubit have a specific physical meaning, since the measurement of a qubit would produce the value |0〉 with probability |α|² and |1〉 with probability |β|², which resembles a Bernoulli random variable. In particular, the unbiased coin is represented by the state |+〉 such that $α = β = 1 / \sqrt{2}$ . However, it is important to note that measurement of a single qubit can be made only once, since the measurement procedure essentially collapses the qubit to one of the binary states reproducing the same state under subsequent measurements.

As a general property of quantum systems, composition of multiple qubits as well as multi-qubit circuits are performed via the Kronecker product of matrices:

A \otimes B = (\begin{matrix} a_{11} B & \dots & a_{1 n} B \\ ⋮ & ⋱ & ⋮ \\ a_{n 1} B & \dots & a_{n n} B \end{matrix})

In particular, considering the product |ψ〉 ⊗ |φ〉 of two 1-qubit states, we obtain the state of a qubit pair described by a vector in ℂ⁴. To shorten the notation, very common abbreviations are used such as:

| ψ 〉 \otimes | φ 〉 \equiv | ψ 〉 | φ 〉 \equiv | ψ φ 〉 .

The compact notation often applies to the vectors of the computational basis, e.g. |00〉 = (1, 0, 0, 0)^T (where a row vector is transposed). In general, since the state of a n-qubit system is a vector in ℂ²ⁿ, then in quantum computing one can represent data in a space whose dimension scales exponentially in the number of qubits. A system of multiple qubits may not always be decomposed into a product of individual qubits due to the so-called entanglement demonstrated e.g. by the following Bell state

A2

| Ψ 〉 = \frac{1}{\sqrt{2}} | 00 〉 + \frac{1}{\sqrt{2}} | 11 〉,

such a state is not decomposable to a Kronecker product of two 1-qubit states. Entangled states, like the Bell state (A2), encode quantum correlations that cannot be reproduced classically as proved by the experimental violation of the Bell inequalities. Due to its dramatic deviation from classical phenomena, entanglement is one of the main resources exploited in quantum computing.

Similarly to a single qubit, an n-qubit system, also called n-qubit register, can be in a quantum superposition of the all possible 2ⁿ binary states numbered lexicographically. As such, the state of a n-qubit system is represented by a vector |ψ〉 of length n as

| ψ 〉 = \sum_{i \in {0, 1}^{n}} α_{i} | i 〉, \sum_{i \in {0, 1}^{n}} {| α_{i} |}^{2} = 1,

where the components a_i have similar meaning, and i is the n-digit binary string corresponding to the pure n-qubit state. It is worth noting that a measurement is possible to be taken over a part of the system of n qubits which will subsequently reduce the number of components of a vector by fixing them, causing re-normalization in the coefficients.

Constructing a QC is performed using several basic elements known as quantum gates and acting as operators on the corresponding vectors. Algebraically these correspond to matrices that define operators on the state space of the model, where the only restriction for the matrix U used to perform a quantum operation is that U should be unitary, that is, U^† U = I, where U^† = (U^T)* is the transposed and complex conjugate matrix of U and I is the identity matrix of corresponding dimension. In particular, the following so-called Pauli matrices σ_x, σ_y, σ_z define the single-qubit gates:

A3

σ_{x} = [\begin{array}{l} 0 & 1 \\ 1 & 0 \end{array}], σ_{y} = [\begin{matrix} 0 & - i \\ i & 0 \end{matrix}], σ_{z} = [\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}],

where σ_x is acting as a quantum NOT circuit which swaps the components of a vector |ψ〉 (a.k.a. bit flip), σ_y flips both the components and interacts with their real and imaginary parts, and σ_z flips the sign of the second component of the vector |ψ〉 (sometimes called phase flip). The eigenvectors of σ_z form the computational basis.

A remarkable 1-qubit gate is the Hadamard gate defined as follows:

A4

H : = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) .

There is a well-known graphical representation of quantum gates that resembles the notation of logical gates in digital computing. The graphical representation of the Hadamard gate is:

The Hadamard gate realizes a change of basis {|0〉, |1〉} ↦ {|+〉, |–〉} of a 1-qubit Hilbert space where $| \pm 〉 = (| 0 〉 \pm | 1 〉) / \sqrt{2}$ .

The 1-qubit gate appending a relative phase in the input state, it is defined by:

A5

P_{ϕ} : = (\begin{matrix} 1 & 0 \\ 0 & e^{i ϕ} \end{matrix}),

where φ ∈ ℝ, and hence P_π = σ_z. The corresponding graphical representation is simply:

Two more specific 1-qubit gates S := P_π/2 and T := P_π/4 are important in defining a universal set of quantum gates.

Multiple qubit gates can also be defined, a remarkable example of a 2-qubit gate is the controlled NOT (CNOT) gate given by

U_{C N} | ψ 〉 = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}] [\begin{array}{l} α_{1} \\ α_{2} \\ α_{3} \\ α_{4} \end{array}] = [\begin{array}{l} α_{1} \\ α_{2} \\ α_{4} \\ α_{3} \end{array}] .

It may be noted that the second component is flipped only if the first component is in state 1, that is, |10〉 is changed to |11〉, whereas |11〉 becomes |10〉. The graphical representation of the CNOT is

In order to construct QC from single gates in algebraic formalism, Kronecker product is used to indicate applying parallel gates on independent qubits, while matrix multiplication corresponds to sequential application of gates. This, however, has the price of exponential dependence of the matrix size on the number of qubits, as a consequence a general quantum computation cannot be efficiently simulated by classical computing.

As such, a QC for n qubits corresponds to a unitary matrix U of size 2ⁿ that performs the necessary computation in terms of a product U|ψ〉, where |ψ〉 is the initial state of the system. As in classical computing, where a small set of logical gates such as {AND, OR, NOT}, can be used to realize any computation, in quantum computing there is a similar notion of universality. A set of quantum gates is said to be universal for quantum computation if, for all n ∈ ℕ, any QC for n qubits can be approximated to arbitrary accuracy by a composition of only those gates. One can prove that the set {H, S, T, CNOT} is universal for quantum computation [193].

Appendix B. Synthesis, Optimization, Adaptation and Decomposition of QC

QC are a universal representation of quantum computations. However, procedure of quantum computation can be described in alternative ways, for example adiabatic quantum computing (AQC) is a universal model of quantum computing as well. Moreover, to some extend, quantum computations can be also described in natural language, possibly introducing some ambiguity.

By synthesis of QC we mean a process of obtaining a (more precisely at least one) QC from a different representation of a quantum algorithm. The foundation of this topic was laid in [208] generalizing approach for constructing Toffoli gate from 5 2—bit gates proposed in [209] and thus building up n-bit operations with quantum 1 — and 2—qubit gates. Further, the QC synthesis problem is described briefly in [186], where the term synthesis is defined as a compilation of the desired operator into a QC understandable for a quantum computer. In general, the process of synthesis depends on the kind of the initial representation and on possible constraints and additional requirements on the target QC. Among the synthesis processes of QC we point out the following relevant procedures:

Optimization: a synthesis process in which the target QC is required to minimize one or more cost criteria.
Adaptation: a synthesis process which provides the target circuit modifying one or more intermediate QC that do not implement the initial representation of the considered algorithm.
Composition: a synthesis process from given elementary gates and/or circuits until the corresponding unitary matrix becomes equal (or approximately equal) to the specified matrix [99].
Decomposition: a synthesis process whose initial representation is a given unitary matrix [210] or already a QC and the target circuit is constrained to be a composition of elementary gates from a given set.

Note that the four processes described above do not exhaust the whole possible synthesis processes and a synthesis process can include more than one. Some authors adopt slightly different versions of these definition, for example reducing synthesis to decomposition.

Approximation of any unitary operator acting on n qubits with arbitrary precision ε by the so-called universal set of gates is guaranteed by Solovay–Kitaev theorem [193] using O(n²4ⁿ log^c (n²4ⁿ/ε)) gates. However, this is quite a large number of gates and thus optimization is required. The general idea of QC optimization is to obtain a QC that satisfies some requirements, e.g. hardware requirements of a real machine, the set of quantum gates used for circuit synthesis and topology [60], specific connection architecture used [28,41], depth [31] etc. As such, various optimization schemes are used, either based on the so-called search algorithms (including Monte-Carlo), or using some information about the specific system, such as undertaken by Bayesian optimization as in [169].

It should be noted that a few related problems to QC synthesis and optimization are:

the so-called QC compilation [211] or transformation [212], which is, adaptation of the general QC into a specific hardware (as well as some specific related techniques such as instantiation [60]) and turns out to be NP-hard [213,214],
the quantum tomography which attempts to reconstruct or approximate the QC on the basis of multiple output measurements for given input [215],
optimization related to the data loading into the quantum program, i.e. quantum state preparation [216, 217],
last but not least, quantum computing simulation [218] is a necessary attribute in the development of the new circuits with the help of conventional computers and supercomputing hardware.

Authors use different technique for synthesis of quantum circuits. Let us list some of them. Classical (reversible) logic based: binary decision diagram (BDD) [81,161], exclusive-sum-of-products (ESOP) [36,79,165], Toffoli network [77,106,167], node dependency matrix [150], Kronecker functional lattice diagram (KFLD) [100], heuristic and A* algorithms [25,59,99,119,171], representation as a series of cycles [7,7,31,137,171,178], Bayesian optimization [169], SAT problem on a Boolean function encoding the QC of a given depth (satisfiable if such a circuit exists) [76], synthesis with respect to LNN architecture [16,138].

The universal circuit optimization results for arbitrary unitary can be significantly improved if we know the structure of the unitary matrix. So, researchers consider improvement of quantum circuits for specific important problems. Researchers [60,104,118,139,152,159,168,169] suggested a heuristic procedure to minimize the number of gates for a noisy model in the case of QFT and QAOA and other algorithms. Circuits for specific problems with respect to NN architecture are also can be interesting: QFT [219–226], quantum hashing [200,220,221], Shor’s algorithm [223] and others.

These problems are beyond the scope of this review unless a significant part of the corresponding papers are related to circuit optimization and/or synthesis.

Appendix C. Bounds and Quality Evaluation

The circuit size of an arbitrary n-qubit operation is bounded, and some of these bounds are constructive. Those bounds may be given for an arbitrary size n, or for some specific size. Many of the constructive results are now embedded as optimization techniques in the software packages for quantum computing.

Any unitary that represents an algorithm on n qubits can be represented using 4ⁿ gates [198,199]. Later, this result was improved. The approach that uses $\frac{23}{48} 4^{n}$ CNOT gates (and about the same one qubit gates) was shown [128,227]. These results are close to the lower bound [228,229] for an arbitrary unitary transformation that is $\frac{1}{4} 4^{n}$ .

In particular, for a trapped ion technology, the number of so-called MS-gates is lower bounded by [130]

\frac{4^{n} - 3 n - 1}{2 n + 1} .

The CNOT count of a universal n-qubit circuit is lower bounded by [230]

\frac{4^{n} - 3 n - 1}{4} .

Another optimization is [136]. The CNOT cost of n-qubit Toffoli gate is at least 2n, even if ancillae are permitted [231].

The depth of an arbitrary n-qubit Clifford transformation is upper bounded by 7n – 4 over LNN architecture, and 1.5n + O(log²(n)) in all-to-all connected architecture [232].

For the arbitrary 2-qubit gate, the lower bound on CNOT count is 3 [233,234], and it is constructive (i.e., a procedure exists for constructing such a chain), used together with at most 15 rotation gates.

The practical limitations of the circuit parameters that provide quantum supremacy are summarized in [235]. A few synthesis-related metrics are summarized in [236], whereas upper bounds for various synthesis technologies are given in [237].

Mapping the specific unitary operator U into a QC and considering all the constraints will give a new operator U_G. However, the latter may be not identical to the former, and there is some tolerance for acceptable deviation. Otherwise, the deviation of U_G from U is used to construct a goal function for the optimization algorithm. Among the norms, in the literature the following are considered:

The L^p norm, i.e. the norm in an L^p space, defined in general case as
${‖ U - U_{G} ‖}_{L^{p}} = {[\sum_{i = 1}^{n} \sum_{j = 1}^{m} {| u_{i j} - u_{G i j} |}^{p}]}^{1 / p}$
including
- – L¹ norm, known as Manhattan distance (in case of vectors), [99]
  ${‖ U - U_{G} ‖}_{L^{1}} = \sum_{i = 1}^{n} \sum_{j = 1}^{m} | u_{i j} - u_{G i j} |$
- – Euclidean norm [130]
  ${‖ U - U_{G} ‖}_{E} = \sqrt{\sum_{i = 1}^{n} \sum_{j = 1}^{m} {(u_{i j} - u_{G i j})}^{2}}$
- – Maximum norm
  ${‖ U - U_{G} ‖}_{L^{\infty}} = \max_{i, j} | u_{i j} - u_{G i j} |$
Trace norm of matrix U is the sum of singular values of this matrix. The singular values are the square roots of the eigenvalues of UU*.
$‖ U ‖_{1} = Tr (\sqrt{U U^{*}}) .$
Diamond norm is the trace norm of the output of a trivial extension of a linear map, maximized over all possible inputs with trace norm at most one.
Let Φ : M_n(ℂ) → M_m(ℂ) be a linear transformation, where M_n(ℂ) denotes n × n complex matrices, let 1_n : M_n(ℂ) → M_n(ℂ) be the identity map on n × n, and X ∈ M_n2(ℂ). Then the diamond norm of Φ is given by
$‖ Φ ‖_{⋄} = \max_{X; ‖ X ‖_{1} \leq 1} {‖ (Φ \otimes 1_{n}) X ‖}_{1},$
where ∥·∥₁ denotes the trace norm.
The diamond norm induces the diamond distance, which in the particular case of completely positive, trace non-increasing maps E, F is given by
$d_{⋄} (E, F) = ‖ E - F ‖_{⋄} = \max_{ρ} {‖ (E \otimes 1_{n}) ρ - (F \otimes 1_{n}) ρ ‖}_{1},$
where the maximization is done over all density matrices ρ of dimension n².
Hilbert–Schmidt norm defined by Hilbert–Schmidt inner product [60]
${〈 U, U_{G} 〉}_{H S} = Tr (U^{*} U_{G}) .$
Based on this representation, the following distance function is suggested in [60]
$D (U, U_{G}) = 1 - 〈 U, U_{G} 〉 / 2^{n} .$
Frobenius norm [65]
$‖ U_{G}^{*} U - I ‖ = 2 - 2 Re (Tr (U_{G}^{*} U)),$
which induces a distance function [65,204]
$Δ_{F} (U_{G}, U) = 1 - \frac{| {〈 U, U_{G} 〉}_{H S} |}{d},$
where d is the state space dimension. (A similar version of this function, $\sqrt{Δ_{F}}$ , was used in [5]).

It can be mentioned that sometimes instead of the measurements on the (original and approximating) unitary matrices, the output of two circuits is compared in terms of the probability distribution of the results it generates. In such a case, the comparison is done by some other norms, such as the total variation norm [168] (defined as the half of the L₁ norm applied to the corresponding probability vectors).

To discuss the relation between the quality evaluation measures presented in this section and optimization criteria from Section 3.2, we note that usually the problem of circuit optimization is considered as (un)constrained optimization problem, where the criterion is one (or several) of the criteria defined in Section 3.2, and the constraint (if any) is given using one of the aforementioned norms. However, a dual problem can also be studied, where the distance is to be optimized, and the constraint is defined using one of the metrics from Section 3.2. The rather diverse problem statements in the literature body of this study prevent us from giving a concise mathematical description of the generic circuit optimization problem.