Contacts:
Bruno Schmitt, PhD student, EPFL-IC-LSI
Mathias Soeken, Post-doc, EPFL-IC-LSI
Giovanni De Micheli, Professor, EPFL-IC-LSI
Presentation:
The ultimate goal 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.
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
Quantum computers are supposedly great at simulating Hamiltonian dynamics. Indeed, this is considered one of its killer application. The fact is, however, that to simulate a Hamiltonian, you first need to represent it efficiently. Most research on this area employs the use of oracles to access the elements of the Hamiltonian, which are often given as classical Boolean functions, or expected to be given as such.
Tweedledum provides different techniques to synthesize oracles. The starting point can be a classical logic network, a truth table, a sum-of-product expression, a permutation matrix, etc. The synthesis method can use a fault-tolerant cost function, hence minimizing the number of T gates when using a Clifford+T gate set. It can also use a NISQ cost function which will try to minimize the number of qubits, and 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
Most near-term quantum devices impose restrictions on qubit interactions, known as the coupling constraints. Hence it might be necessary to modify a platform-agnostic circuit, in which all qubits are allowed to interact, to a platform-specific one. Tweedledum distinguishes those two types of quantum circuits. From a structural perspective, both are a sequence of gates acting on qubits. They differ in that the qubits used in an idealized circuit refer to logic qubits, whereas, in a mapped circuit, they refer to physical qubits defined by a real device specification. The library implements several mapping algorithms.