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.

In this research, we investigate the automatic state preparation of a specific subset of quantum states that are uniform superpositions over a subset of basis states, called uniform quantum states. Uniform quantum states are important because they are considered as the initial quantum state for algorithms such as Grover walk. Moreover, many important quantum states are uniform, such as the Bell state, the W state, the GHZ state, and the uniform superposition of all basis states.

We exploited the fact that such states can be represented by Boolean functions. For generating such a state given as input a Boolean function f in some representations, we assume all states are zero in the beginning, and then we search for an efficient construction that transforms a given unitary matrix QSP(f) into a circuit.

We proposed a recursive algorithm leveraging Boolean functions to generate a quantum circuit that prepares the desired quantum state. Afterwards, we investigated the symbolic implementations of the algorithm that works directly on a decision diagram, and therefore permits a compact representation for some functions. The algorithm provides a fast and scalable quantum state preparation, where state-of-the-art algorithms cannot be applied anymore due to the exponential run time. In general, the task of quantum state preparation is exponential in the number of qubits for run time and the number of elementary quantum gates. We proposed a solution to reduce the run time using decision diagrams. The basic algorithm iteratively prepares a target qubit depending on previously prepared qubits, which are used as control qubits. In another work, we focused on improving the recursive algorithm using functional dependencies, a concept borrowed from logic synthesis. Functional dependencies can be utilized in two ways: (1) to reduce the number of control qubits if the target qubit depends only on a subset of previously prepared qubits and (2) to reduce the number of quantum gates if the functional dependency can be well expressed with the library of hardware supported quantum gates. For instance, XOR-based functional dependencies can be realized using only CNOTs. We additionally utilized variable reordering techniques to maximize the number of extracted functional dependencies. As an example, the proposed method prepares the n-qubit GHZ state by using n CNOTs because the preparation of each qubit is functionally dependent on the first qubit.

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

Main Publications

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

Access all publications from here.