Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

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

Ph.D. dissertations & Faculty habilitations


The topic of this habilitation is the study of very small data visualizations, micro visualizations, in display contexts that can only dedicate minimal rendering space for data representations. For several years, together with my collaborators, I have been studying human perception, interaction, and analysis with micro visualizations in multiple contexts. In this document I bring together three of my research streams related to micro visualizations: data glyphs, where my joint research focused on studying the perception of small-multiple micro visualizations, word-scale visualizations, where my joint research focused on small visualizations embedded in text-documents, and small mobile data visualizations for smartwatches or fitness trackers. I consider these types of small visualizations together under the umbrella term ``micro visualizations.'' Micro visualizations are useful in multiple visualization contexts and I have been working towards a better understanding of the complexities involved in designing and using micro visualizations. Here, I define the term micro visualization, summarize my own and other past research and design guidelines and outline several design spaces for different types of micro visualizations based on some of the work I was involved in since my PhD.