Ph.D
Group : Parallel Systems
Methods for optimizing the synthesis of quantum circuits
Starts on 01/09/2017
Advisor : BABOULIN, Marc
[VALIRON Benoit]
Funding : Convention industrielle de formation par la recherche
Affiliation : Université Paris-Saclay
Laboratory : LRI - ParSys et Atos
Defended on 22/10/2020, committee :
Directeur de thèse :
- M. Marc Baboulin, Professeur, LRI, Université Paris-Saclay
Co-encadrant :
- M. Benoît Valiron, Maître de conférences, LRI, CentraleSupélec
Rapporteurs :
- M. Michele Mosca, Professeur, IQC, University of Waterloo, Canada
- M. Mark Asch, Professeur, LAMFA, Université de Picardie Jules Verne
Examinateurs :
- Mme. Elham Kashefi, Directrice de Recherche, LIP6, Sorbonne Université
- Mme. Cécilia Lancien, Chargée de Recherche, IMT, Université Toulouse 1 Capitole
- Mme. Pascale Senellart, Directrice de Recherche, C2N, Université Paris-Saclay
Membre invité :
- M. Cyril Allouche, Responsable Quantum R&D, ATOS
Research activities :
Abstract :
We study the optimization of classical and quantum resources during the synthesis of quantum circuits. Quantum circuits synthesis consists in transforming the high-level specification of an algorithm into a sequence of elementary instructions that can be executed directly by the quantum computer: a quantum circuit. This step is part of the more general problem of the compilation of quantum algorithms. It is an essential issue given that the ability to generate an optimized circuit for an algorithm can guarantee its proper execution on a quantum machine whose resources are currently very limited. The problem of synthesizing quantum circuits can be broken down into several sub-problems, each linked to a different abstract representation of the operators to be synthesized: unitary matrix, Boolean formula, etc. The structure of this thesis follows this decomposition into sub-problems, each part focusing on a precise abstract representation.
The first part of this thesis focuses on the synthesis of quantum operators represented by unitary matrices. Although the literature has mainly been interested in optimizing the size of the final quantum circuit, we study the trade-off between quantum resources --- the size of the generated quantum circuit --- and classical resources --- the amount of classical computation necessary to generate the said quantum circuit. We propose two methods which improve the state of the art at the two extremes of this trade-off.
First, we develop a method requiring few classical resources, efficiently parallelizable on multi-core or GPU architectures, while generating circuits only twice as large as those provided by the best state-of-the-art algorithm. On the other hand, our method is able to synthesize operators on sizes of problems inaccessible with other existing methods. Secondly, we explore the use of numerical optimization algorithms for an optimal synthesis. We show that it is possible to synthesize operators on a small number of qubits with an optimal circuit size given by a theoretical lower bound.
Finally, our two methods complement each other with the best algorithm of the state of the art, each method being the most efficient for a given range of operator sizes.
The second part of this thesis focuses on the synthesis of a class of specific operators: the so-called linear reversible operators. In this part we are interested exclusively in the optimization of the quantum resources and we consider two metrics: the size of the circuit, a metric already used during the first half of this thesis and here given by the number of CNOTs in the circuit, but also the circuit depth which is closely related to the execution time of the quantum circuit. We propose new methods with various techniques optimizing these two metrics: variant of Gaussian elimination, divide and conquer algorithm, reduction to a cryptography problem. Each of our methods surpasses the state of the art in a large majority of cases and overall our methods, when they optimize the same metric, are complementary depending on the size and complexity of the operator to be synthesized. We also apply our methods for the compilation of a library of reversible functions. We manage to drastically reduce the number of CNOTs and the total depth of the circuit while keeping other metrics of interest (the T-depth for example) as low as possible
