Automated Optimization of Quantum Circuits
Bruno Schmitt, PhD student, EPFL-IC-LSI
Mathias Soeken, Post-doc, EPFL-IC-LSI
Giovanni De Micheli, Professor, EPFL-IC-LSI
The idea of using quantum phenomena for computation is not new, decades have passed since great minds of physics, such as Richard Feynman  and David Deutsch , suggested the possibility of a quantum computer being superior to a classical (non-quantum) computer in certain tasks. In the past few years, technology advances have motivated a wave of investment in quantum research. Still, we are just beginning to reach the stage where quantum devices will be able to provide useful solutions to hard problems .
We are entering an important era in quantum technology: The Noise Intermediate-Scale Quantum (NISQ, ) era, which is characterized by the appearance of quantum computers with sizes ranging from fifty to a few hundred qubits—Google and IBM recently announced 72-qubit  and 50-qubit  devices, respectively.
In this era, the development of robust quantum programming toolchains will be crucial to close the gap between the size and reliability requirements of quantum computing algorithms and the current resources available in physical machines. Hence, the focus of my work will be the research of thorough and rigorous methodologies for translating and optimizing quantum algorithms.
The most commonly used notation for representing quantum algorithms is the quantum circuit model introduced by Deutsch, which describes the computation as a sequence of elementary quantum logic gates acting on a collection of qubits. While such representation has the advantage of simplicity, it lacks canonicity, i.e. there are many different ways of representing a given computation with an available set of universal elementary operations. Finding an implementation that uses the fewest resources is not only advantageous, but imperative given the stringent resource constraints in quantum hardware.
The problem of globally optimizing an arbitrary quantum circuits is known to be in-tractable (to be precise, the optimization of quantum circuits is QMA-hard—QMA stands for Quantum Merlin Arthur and is the natural extension of the classical class NP to the quantum computing world). Consequentially, heuristic optimization approaches are needed. Inspired by combinational logic optimization and compiler optimization, I propose to use a collection of dedicated heuristic algorithms.
The algorithms apply orthogonal transformations to aggressively minimize space and time, which not only minimizes qubit usage but also lessen the load on quantum code corrections. Ideally these transformations are independent and can be applied in any order (leaving us with the job to find and form good sequences of transformations); they can be purely structural, that is relying only on the relation between nodes (structure) of a netlist or directed acyclic graph representation of the quantum circuit, or functional, i.e., when it relies on the 2n × 2n unitary matrix representation which fully and uniquely describes the computation performed by a set of quantum gates—having the advantage of eliminating structural bias of the circuit, but the disadvantage of poor scalability.
The goal is the development of a systematic methodology to optimize quantum circuits. The results of my research are a collection of dedicated and effective algorithms that enable to bridge the gap between the resource requirements of quantum algorithms and the capabilities of the near-term quantum hardware.
- R. P. Feynman, “Simulating physics with computers,” International journal of theoretical physics, vol. 21, no. 6-7, pp. 467–488, 1982.
- D. Deutsch, “Quantum theory, the Church–Turing principle and the universal quantum computer,” Proc. R. Soc. Lond. A, vol. 400, no. 1818, pp. 97–117, 1985
- J. Preskill, “Quantum computing in the NISQ era and beyond,” arXiv preprint arXiv:1801.00862, 2018.
- “A preview of Bristlecone, Google’s new quantum processor,” Retrieved August 21, 2018, URL: https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html.
- “The future is quantum,” Retrieved August 21, 2018, URL: https://www.ibm.com/blogs/research/2017/11/the-future-is-quantum/.