Quantum computers promise to exceed the capabilities of conventional computers in fields such as computational chemistry, machine learning, and cryptoanalysis, thus attracting massive research interest. Currently, we distinguish between two different quantum computing applications. The first one is related to the quantum systems that are available at the present and in the near future. Such systems are characterized by a few noisy qubits and are called

* General design flow for quantum computing*

Quantum algorithms are described in terms of quantum programs written in a quantum programming language (such as ProjectQ, Q#, Qiskit, or PyQuil). In order to run the program on a physical quantum device, the program must be translated into a sequence of elementary operations that can be run on the quantum computer. Such a sequence of quantum operations is referred to as quantum circuit. In order to cope with the complexity of a high-level quantum program, typically several levels of abstractions are required in the quantum compilation process. The choice of layers, and the choice of transformation algorithms in each layer, highly depends on whether compilation targets NISQ or fault-tolerant quantum computers. For example, NISQ quantum computers are very noisy and the decoherence time of qubits is short; therefore, it is key to find a quantum circuit that reduces 2-qubit gates, since these are more noisy than single-qubit gates. In error-corrected fault-tolerant quantum computers, the goal is to reduce the use of gates that require a large overhead in terms of error correction (e.g., the single-qubit non-Clifford T gate). Typical layers of abstractions are:

- Synthesis: The task of mapping combinational logic into high-level quantum operations. In this step the aim is to meet the qubit requirements of the targeted quantum device.
- Optimization: The task of optimizing a quantum circuit. A typical cost metric is to reduce the number of gates. Depending on the targeted quantum device, different gates may have a different cost. If the circuit is technology-dependent, optimization must guarantee not to violate constraints posed by the targeted device.
- Mapping: The task of translating a technology-independent quantum circuit into a technology-dependent quantum circuit. The resulting circuit can only use those quantum operations which are supported by the target device and must adhere to possible coupling constraints of qubit pairs.

* Example of quantum compilation flow for fault-tolerant quantum computing*

The embodiment of our research is the creation of design tools and libraries.
Built using C++17, *Tweedledum *, and its companion *Tweedledee*, are two header-only, open-source libraries in development. Tweedledee offers parsers for formats commonly used to describe quantum circuits, e.g., OpenQASM and Quil. Tweedledum provides methods for composing quantum programs at the circuit level, for optimizing them in both the number of gates and the number of qubits, for transforming them for the constraints of a particular device, etc.
The ongoing research on the development of Tweedledum loosely falls under one of the following four categories.

**Core.**

Study of different data structures and abstractions used to represent quantum circuits and gates. Internally, the library can represent circuits using netlists, DAGs, and phase polynomials. The rationale for investigating different data structures is the observation that the efficacy of some optimization routines is tightly related to the underlying data structures. Indeed, phase polynomials make the optimization of Z-axis rotation gates trivial. Furthermore, it can help optimization algorithms to escape structural bias. The use of directed acyclic graphs, on the other hand, greatly helps with rule-based optimizations and pattern matching.**Synthesis/Compilation.**

In Tweedledum, there are many techniques to generate a quantum circuit, which are lousily classified as synthesis or compilation, depending on the starting point. Indeed, the difference between these two is subtle.

We call compilation the process that transforms a higher-level representation of the circuit in a lower-level representation. For example, if we start with a classical reversible logic circuit and transform it into a quantum circuit defined over a Clifford+T gate set. Another example, starting from an OpenQASM abstract-syntax tree and generating a quantum circuit. A final example would be to decompose a circuit over a Clifford+T gate set into a circuit over the CX+U3 gate set, which is required to run a circuit in an IBM's quantum computer.

In synthesis, the starting point is some other specification. We can synthesize a quantum circuit from a Boolean function. This Boolean function can be represented as a logic network, a truth table, a sum-of-products expression, etc. There are functions to synthesize circuits out of permutation matrices, or a list of parity terms, or from diagonal unitary matrices.

The choice of which compilation method or synthesis method to use is highly dependent on the cost function used to evaluate the result. A fault-tolerant cost function, for example, aims to decrease the number of T gates, as they require a large overhead in terms of error correction. A NISQ cost function is more concerned with reducing the number of two-qubit gates.**Optimization.**

A significant part of research on quantum computing is working out how to run quantum circuits on real quantum machines. In these machines, experimental errors and decoherence introduce errors during computation. Thus, to obtain a robust implementation, it is essential to apply aggressive space (number of qubits) and time (number of gates) optimization techniques. The library already provides some basic optimization techniques.

Research is ongoing for new techniques based on sets of orthogonal transformations. Transformations range from purely structural, which rely only on the relationship between nodes (structure) of a netlist or directed acyclic graph representation, to purely functional, i.e., when they rely on the unitary matrix. There exists a significant tradeoff between the quality of results and scalability.**Mapping.**

In the quantum circuit model of computation, circuits manipulate qubits. These qubits exist as abstractions within a circuit and shall be called virtual (or logical). Mapping is the task of finding a one-to-one relation between virtual qubits and physical qubits, which denote the actual hardware units that store quantum bits, enabling the execution of all gates. In the circuit model, any pair of virtual qubits can interact, i.e., we can perform a two-qubit operation between any pair. The physical qubits in most quantum hardware, however, are not fully connected, meaning that not every pair of physical qubits can participate in the same quantum operation. These physical connectivity restrictions are known as coupling constraints. The library divides mapping into two subtasks: placement and routing. Placement tries to find a bijection between the set of virtual qubits and the set of physical qubits, such that the quantum device can execute all gates. Such perfect placement, however, may not exist. In this case, a placement algorithm might return an initial placement. When the placement is not enough, it is necessary to transform the circuit. Given an initial placement, a router uses SWAP operations to move the virtual qubits around the device topology whenever it finds an operation that acts on qubits that are physically separated. It routes the involved virtual qubits to adjacent physical qubits.

The quality of the mapped circuit is measured in the number of swap operations. A good mapper should not add more swaps than necessary. We know the different combinations of placement strategies and routing strategies greatly influence quality. Current research aims to better understand the relation among these factors: i) metric to evaluate the quality of initial placements; ii) new initial placement heuristics, iii) new routing algorithm.

**Compilation of combinational logic.**

We focus on providing automatic tools to compile complex logic designs, required by various quantum algorithms, e.g., Grover’s, into quantum operations. The cost of the resulting quantum network can account for a large portion of the overall cost of the quantum algorithm. Hence, optimizing the synthesis outcome can have a strong impact on the overall algorithm complexity. Implementations for all the developed synthesis methods can be found in*caterpillar*, an open-source C++ library for quantum compilation, which is part of the EPFL synthesis libraries. Caterpillar enables a two-step approach to quantum compilation. The first step consists of building a reversible network for the given combinational design, specified as a multi-level logic network. The library supports many different types of logic networks, e.g.,*Xor-And-inverted Graphs*(XAG),*And-Inverter Graphs*(AIG),*Look-Up Table*(LUT) networks. Many different strategies can be selected to perform this step, all exploring a different balance between qubits and gates. The second step consists of transforming each reversible gate in a quantum circuit, using manually-optimized decompositions from the literature.

**Quantum memory management.**

Quantum memory management is becoming a pressing problem, especially given the recent research effort to compile new and complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. We show how this problem exactly matches the reversible pebbling game problem. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed techniques, embedded in Caterpillar, empower the designer with the flexibility to explore the trade-off between memory resources and number of operations.

**The STG (Single-Target Gate) Benchmark.**

The benchmark suite contains quantum circuits implementing small Boolean functions and expressed in the Q# quantum programming language. The circuits are optimized according to the requirements of fault-tolerant quantum computing. For each representative of a spectral-equivalent class of Boolean functions with 4 and 5 inputs, the benchmark contains three different implementations: optimized for T-count, T-depth or number of qubits. The benchmark can be used to test new optimization algorithms or in combination with hierarchical methods.

The preparation of quantum states is performed by a quantum circuit consisting of Controlled-NOT (CNOT) and single-qubit gates. Known algorithms to prepare arbitrary n-qubit quantum states create quantum circuits in O(2^{n}) runtime and use O(2^{n}) CNOTs, which are more expensive than single-qubit gates in NISQ architectures or use ancilla qubits. To reduce runtime and the number of CNOTs without using ancilla qubits, we simplify the problem by considering important families of quantum states such as *Uniform Quantum States* (UQS) and *Cyclic Quantum States* (CQS).

UQSs are superpositions of basis states, where all amplitudes are either zero or have the same value. We map UQSs to Boolean functions and propose a *UQS Preparation* (UQSP) method. For generating such a state given as input a Boolean function f, we assume all states are zero in the beginning, and then we search for an efficient construction that transforms a given unitary matrix UQSP(f) into a circuit.

Preparing UQSs using Boolean functions allows us to utilize different representations of Boolean functions. We utilize decision diagrams to reduce runtime and enable preparation for a larger number of qubits where the state-of-the-art methods are not applicable. To further reduce the number of CNOTs, we utilize variable reordering and functional dependencies among the variables. Our state preparation method requires an exponential number of CNOTs in the worst case but it reduces CNOTs significantly for practical benchmarks. Moreover, our method generates an exact representation of quantum states without using ancilla qubits.

In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In another work, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states, with gate complexity O(n), without requiring any ancillary qubit. The idea is based on creating cyclic permutations step-by-step. We design our algorithm such that creating each permutation requires only a constant number of 2-qubit and 3-qubit gates regardless of the total number of qubits n.

This research provides an open-source C++-17 library for quantum state preparation, called angel, which is part of the EPFL synthesis libraries.

- G. Meuli, M. Soeken and G, De Micheli, XOR-AND-Inverter Graphs for Quantum Compilation, Nature partner journal on Quantum Information 8, 7, January 2022
- F. Mozafari, Y. Yang, and G. De Micheli, Efficient Preparation of Cyclic Quantum States, In 27th Asia and South Pacific Design Automation Conference (ASP-DAC), 2022.
- F. Mozafari, H. Riener, M. Soeken, and G. De Micheli, Efficient Boolean Methods for Preparing Uniform Quantum States, In IEEE Transactions on Quantum Engineering, vol. 2, pp. 1-12, 2021.
- F. Mozafari, M. Soeken, H. Riener, and G. De Micheli, Automatic Uniform Quantum State Preparation Using Decision Diagrams, In 2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL), pp. 170-175. IEEE, 2020
- M.Soeken, G. Meuli, B.Schmitt, F.Mozafari, H.Riener and Giovanni De Micheli, Boolean Satisfiability in quantum compilation, Philosophical Transactions of the Royal Society A, vol 378, Issue 2164, 2019.
- G. Meuli, M. Soeken, M. Roetteler, N. Bjorner, G. De Micheli, Reversible Pebbling Game for Quantum Memory Management, DATE 2019, Firenze, Italy, March 2019.
- G. Meuli, M. Soeken, M. Roetteler, G. De Micheli, Resource constrained oracle synthesis for quantum computers, Quantum Physics and Logic (QPL), Orange CA, USA, June 10â€“14, 2019.
- J K. Smith, M. Soeken, B. Schmitt, G. De Micheli, M. Thornton, Using ZDDs in the mapping of quantum circuits, Quantum Physics and Logic (QPL), Orange CA, USA, June 10â€“14, 2019.
- G. Meuli, B. Schmitt, R. Ehlers, H. Riener, G. De Micheli, Evaluating ESOP Optimization Methods in Quantum Compilation Flows, Reversible Computing (RC), Lausanne, Switzerland, June 24-25, 2019.
- F. Mozafari, M. Soeken, G. De Micheli, Automatic Preparation of Uniform Quantum States Utilizing Boolean Functions, IWLS, Lausanne, Switzerland, June 24-25, 2019.
- G. Meuli, M. Soeken, M. Roetteler, N. Wiebe and G. De Micheli. A best-fit mapping algorithm to facilitate ESOP-decomposition in Clifford+T quantum network synthesis, 23rd Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 664-669, Jeju Island, Korea, 2018. .
- G. Meuli, M. Soeken, G. De Micheli, SAT-based CNOT, T Quantum Circuit Synthesis'', International Conference on Reversible Computation, Reversibile Computation, pp. 175-188, Leicester, UK. August 2018.
- M. Soeken, M. Roetteler, N. Wiebe and G. De Micheli. Hierarchical Reversible Logic Synthesis Using LUTs. 54th ACM/IEEE Design Automation Conference (DAC), Austin, Texsas, USA, 2017.
- F. Mozafari, H. Riener, and G. De Micheli, Uniform Quantum State Preparation: A Boolean Approach for Preparing Uniform Quantum States Efficiently and Precisely, In International Workshop on Quantum Compilation (IWQC), Cambridge, UK, September 2020.