Quantum compilation

Giulia Meuli, Fereshte Mozafari, Bruno Schmitt, Heinz Riener, Mathias Soeken, Giovanni De Micheli

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 Noisy Intermediate-Scale Quantum (NISQ) systems. The second application, called fault-tolerant quantum computing, will allow us to run complex algorithms, such as Shor's algorithm for factorization, relying on error-correcting codes. Many of these algorithms require some classical arithmetic operations, e.g., exponential, reciprocal, square root, multiplication, squaring. The corresponding Boolean functions have to be mapped into a universal set of quantum gates, to be performed on an actual quantum computer. This mapping is part of the so-called quantum compilation process. The output of the process is a quantum circuit, which can be evaluated in terms of the resources it requires (gates and qubits).

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:


Example of quantum compilation flow for fault-tolerant quantum computing

Synthesis of quantum computing structures

The ultimate goal of quantum compilation is to bridge the gap between abstract quantum algorithms and their concrete implementation. The research focuses on using the quantum circuit model of computation. Therefore we study all the steps necessary to transform a high-level quantum algorithm, often mathematically described, into a sequence of elementary operations that can be executed by a quantum computer.

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.

Resource estimation of quantum algorithms

This research focuses on estimating the resources required to perform quantum algorithms on a fault-tolerant quantum computer. To this purpose, we develop optimization and synthesis algorithms that are technology-agnostic, hence apply to any quantum computing system.

Quantum state preparation

In general, the initial quantum state is the classical basis state in which all bits are 0. Some quantum algorithms require a specific quantum state in a superposition of basis states at the beginning of the desired application-specific computation. Hence, in addition to the quantum circuit that performs the quantum algorithm, a specific quantum circuit is required that prepares the desired initial quantum state. Moreover, some quantum computing applications (e.g., quantum machine learning, and quantum chemistry) require to efficiently load large sets of classical data into quantum states. As a result, an efficient quantum state preparation is an important task in the quantum compilation.

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(2n) runtime and use O(2n) 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.

Main Publications

  1. 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
  2. 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.
  3. 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.
  4. 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
  5. 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.
  6. G. Meuli, M. Soeken, M. Roetteler, N. Bjorner, G. De Micheli, Reversible Pebbling Game for Quantum Memory Management, DATE 2019, Firenze, Italy, March 2019.
  7. 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.
  8. 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.
  9. 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.
  10. F. Mozafari, M. Soeken, G. De Micheli, Automatic Preparation of Uniform Quantum States Utilizing Boolean Functions, IWLS, Lausanne, Switzerland, June 24-25, 2019.
  11. 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. .
  12. 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.
  13. 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.
  14. 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.

Access all publications from here.