La principale contribution de cette thèse est d'étudier expérimentalement le comportement des ordinateurs quantiques analogiques tels que ceux commercialisés par D-Wave lorsqu'ils sont confrontés à des cas de problèmes de couplage biparti de cardinalité maximale spécifiquement conçus pour être difficiles à résoudre au moyen d'un recuit simulé. Nous comparons un "Washington" (2X) de D-Wave avec 1098 qubits utilisables sur différentes tailles d'instances et nous observons que pour tous ces cas, sauf les plus triviaux, la machine ne parvient pas à obtenir une solution optimale. Ainsi, nos résultats suggèrent que le recuit quantique, du moins tel qu'il est mis en œuvre dans un dispositif D-Wave, tombe dans les mêmes pièges que le recuit simulé et fournit donc des preuves supplémentaires suggérant qu'il existe des problèmes polynomiaux qu'une telle machine ne peut pas résoudre efficacement pour atteindre l'optimalité. En outre, nous étudions dans quelle mesure les topologies d'interconnexion des qubits expliquent ces derniers résultats expérimentaux.
La principale contribution de cette thèse est d'étudier expérimentalement le comportement des ordinateurs quantiques analogiques tels que ceux commercialisés par D-Wave lorsqu'ils sont confrontés à des cas de problèmes de couplage biparti de cardinalité maximale spécifiquement conçus pour être difficiles à résoudre au moyen d'un recuit simulé. Nous comparons un "Washington" (2X) de D-Wave avec 1098 qubits utilisables sur différentes tailles d'instances et nous observons que pour tous ces cas, sauf les plus triviaux, la machine ne parvient pas à obtenir une solution optimale. Ainsi, nos résultats suggèrent que le recuit quantique, du moins tel qu'il est mis en œuvre dans un dispositif D-Wave, tombe dans les mêmes pièges que le recuit simulé et fournit donc des preuves supplémentaires suggérant qu'il existe des problèmes polynomiaux qu'une telle machine ne peut pas résoudre efficacement pour atteindre l'optimalité. En outre, nous étudions dans quelle mesure les topologies d'interconnexion des qubits expliquent ces derniers résultats expérimentaux.
La principale contribution de cette thèse est d'étudier expérimentalement le comportement des ordinateurs quantiques analogiques tels que ceux commercialisés par D-Wave lorsqu'ils sont confrontés à des cas de problèmes de couplage biparti de cardinalité maximale spécifiquement conçus pour être difficiles à résoudre au moyen d'un recuit simulé. Nous comparons un "Washington" (2X) de D-Wave avec 1098 qubits utilisables sur différentes tailles d'instances et nous observons que pour tous ces cas, sauf les plus triviaux, la machine ne parvient pas à obtenir une solution optimale. Ainsi, nos résultats suggèrent que le recuit quantique, du moins tel qu'il est mis en œuvre dans un dispositif D-Wave, tombe dans les mêmes pièges que le recuit simulé et fournit donc des preuves supplémentaires suggérant qu'il existe des problèmes polynomiaux qu'une telle machine ne peut pas résoudre efficacement pour atteindre l'optimalité. En outre, nous étudions dans quelle mesure les topologies d'interconnexion des qubits expliquent ces derniers résultats expérimentaux.
L'objectif est d'étudier expérimentalement le comportement des ordinateurs quantiques analogiques tels que ceux commercialisés par D-Wave lorsqu'ils sont confrontés à des cas de problèmes de couplage biparti de cardinalité maximale spécifiquement conçus pour être difficiles à résoudre au moyen d'un recuit simulé. Nous comparons un "Washington" (2X) de D-Wave avec 1098 qubits utilisables sur différentes tailles d'instances. En outre, nous analysons dans quelle mesure les topologies d'interconnexion des qubits expliquent ces derniers résultats expérimentaux obtenus.
Les ordinateurs quantiques actuels sont encore loin de ressembler à l'image idéalisée que pouvaient se faire les pionniers de l'algorithmie quantique : ils sont de taille limitée (ayant au mieux quelques centaines de qubits) et ont un mauvais rapport signal/bruit. Ces ordinateurs sont appelés ordinateurs quantiques bruités de taille intermédiaire (NISQ). Cela ne signifie pas pour autant qu'ils sont seulement des prototypes sans utilité pratique. Les ordinateurs NISQ resteront majoritaires jusqu'au développement de machines employant des méthodes de correction d'erreurs (FTQC). De ce fait, il serait de première importance de faire des investigations sur le type de calcul et d'algorithme qu'il est possible de mettre en oeuvre sur ces machines, en particulier dans le cadre des problèmes d'optimisation basés sur des algorithmes hybrides où l'ordinateur NISQ pourrait être utilisé comme accélérateur de calcul et intégré à un processus classique plus large. L'implémentation d'algorithmes NISQ nécessite des optimisations proches du matériel afin de tirer le meilleur parti de ces nouvelles technologies. Cela inclut de potentielles optimisations à différents niveaux de la pile logicielle quantique allant de la formulation du problème d'optimisation au raffinement des solutions retournées par l'ordinateur quantique, en passant par l'amélioration de la compilation dédiée en fonction de la puce utilisée. Dans cette thèse, nous proposons d'évaluer les limites des annealers quantiques (QA) tels que ceux commercialisés par l'entreprise D-Wave. Cette technologie exploite l'effet tunnel durant son processus d'annealing mais rencontre des difficultés pour trouver des solutions de bonne qualité pour des problèmes d'optimisation binaires quadratiques non contraints (QUBO). Un problème contraint peut être formulé en QUBO en traduisant les contraintes sous forme de pénalités ajoutées à la fonction de coût. Dans le cas du problème de partitionnement de graphe équilibré, la contrainte d'équilibrage est transformée sous forme de pénalités et tend à densifier le problème QUBO. Il est alors difficile de trouver une représentation de ce problème sur les puces quantiques faiblement connectées. C'est ici que la compilation joue un rôle clef mais reste difficile à réaliser. Nous avons développé un cadriciel afin d'évaluer la performance des annealers quantiques basés sur un ensemble d'instances dont la représentation sur puce quantique est optimale. Malgré la bonne qualité de cette représentation, l'annealer quantique est peu compétitif dans la résolution de problèmes d'optimisation par rapport à des méthodes de résolution classiques de l'état de l'art. Nous présentons également un second outil permettant de faciliter la comparaison d'études de performances basées sur des problèmes d'optimisation. Cet outil permet d'évaluer la diversité des propriétés des instances utilisées dans le cadre d'une évaluation de performance. Il permet ainsi d'évaluer le niveau de confiance pouvant être accordé à une étude de performance. Enfin, l'étape de compilation des annealers quantiques permet d'associer un qubit logique à un ensemble de qubits physiques fortement liés. Le bon paramétrage de la force de couplage entre ces qubits physiques permet d'accroître considérablement la performance de l'annealer quantique. Nous introduisons une méthode de recherche dichotomique afin de paramétrer efficacement cette force de couplage.
Circuits quantiques bruités pour l'optimisation combinatoire Alors que les ordinateurs quantiques croissent en taille tout en restant affectés par le bruit, un défi clé consiste à déterminer quand et comment ils peuvent surpasser les meilleurs algorithmes classiques sur des tâches pratiques. Cela nécessite le développement d'algorithmes de simulation de circuits quantiques hautement efficaces. Les algorithmes de rétropropagation de Pauli font partie des plus prometteurs, ayant montré leur efficacité dans la simulation de certaines classes de circuits quantiques paramétrés, candidats sérieux pour l'avantage quantique à court terme, sous des hypothèses de circuits aléatoires et de bruit de dépolarisation. Cependant, leur efficacité n'avait pas été démontrée pour des modèles de bruit nonunital plus réalistes, tels que l'amortissement d'amplitude, qui capturent mieux le comportement des ordinateurs quantiques actuels. Nous comblons cette lacune en adaptant la rétropropagation de Pauli à la plupart des canaux de bruit à un qubit, incluant le bruit nonunital, et en prouvant qu'elle reste efficace sous ces conditions. Notre algorithme est parallélisable, économe en mémoire, et ne requiert aucune hypothèse sur la localité de l'observable, la géométrie de la puce quantique, ou la profondeur du circuit. Bien que le bruit des ordinateurs quantiques puisse fortement affecter la puissance de calcul dans des circuits hautement structurés et tolérants aux erreurs, nos résultats indiquent peu de différence pour la plupart des architectures variationnelles. Ceci établit la rétropropagation de Pauli comme une méthode efficace pour simuler les dispositifs quantiques bruités sous des hypothèses de bruit réalistes. Bien que ces avancées améliorent notre capacité à simuler des observables bruités, de nombreuses applications pratiques, incluant l'optimisation combinatoire, nécessitent un accès direct aux chaînes de bits produites par les circuits quantiques, car celles-ci encodent les solutions souhaitées. La réplication classique de tels échantillons bruités a jusqu'à présent été limitée au-delà du cadre des circuits aléatoires. Pour combler cette lacune, nous nous concentrons d'abord sur les problèmes dont les fonctions objectif ne dépendent que des corrélations sur deux sites, tel que Max-Cut, et appliquons des techniques d'arrondissement aléatoire gaussien aux marginales à deux qubits du circuit. Ceci produit des échantillons classiques dont le coût espéré est prouvablement proche de celui du dispositif quantique bruité. Des simulations à grande échelle et des expériences sur les ordinateurs quantiques d'IBM confirment que les échantillons arrondis reproduisent la distribution d'énergie complète, avec un comportement similaire sous divers modèles de bruit. Couplé avec la rétropropagation de Pauli pour estimer efficacement les marginales bruitées, cela donne un échantillonneur classique de bout en bout opérant en temps polynomial pour une large classe de circuits variationnels bruités. Nos résultats montrent donc que des circuits quantiques suffisamment bruités pour l'optimisation combinatoire peuvent être échantillonnés classiquement, clarifiant où les ordinateurs quantiques à court terme peuvent ou ne peuvent pas surpasser les algorithmes classiques.Enfin, nous allons au-delà des marginales sur un et deux sites et présentons un algorithme qui échantillonne des chaînes de bits valides directement depuis une distribution d'entropie maximale avec des moments correspondant à ceux du circuit quantique. Cette méthode ne repose pas sur la localité ou la parcimonie de l'Hamiltonien du problème et fonctionne bien sur une variété de circuits quantiques, incluant des circuits profonds sur de nombreux qubits. Lorsqu'elle est combinée avec la propagation de Pauli ou la mitigation d'erreur, elle fournit un pipeline pratique pour obtenir des échantillons de circuits quantiques à court terme, où la correction d'erreur pourrait ne pas encore être disponible.
Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.
La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.