Quantum computers facing chaos. Quantum parallelism allows to perform computation in a radically new manner. A quantum computer based on these new principles may resolve certain problems exponentially faster than a classical computer. We discuss how quantum computers can simulate complex dynamics, in particularly the dynamics of chaotic systems, where the errors of classical computation grow exponentially fast. ----- Le parallelisme autorise par la mecanique quantique permet d'effectuer des calculs d'une maniere radicalement nouvelle. Un ordinateur quantique fonde sur ces principes pourrait resoudre certains problemes exponentiellement plus vite qu'un ordinateur classique. Nous discutons comment un ordinateur quantique realiste peut simuler une dynamique complexe, en particulier les systemes chaotiques ou les fautes de l'ordinateur classique croissent exponentiellement vite.
Quantum computers facing chaos. Quantum parallelism allows to perform computation in a radically new manner. A quantum computer based on these new principles may resolve certain problems exponentially faster than a classical computer. We discuss how quantum computers can simulate complex dynamics, in particularly the dynamics of chaotic systems, where the errors of classical computation grow exponentially fast. ----- Le parallelisme autorise par la mecanique quantique permet d'effectuer des calculs d'une maniere radicalement nouvelle. Un ordinateur quantique fonde sur ces principes pourrait resoudre certains problemes exponentiellement plus vite qu'un ordinateur classique. Nous discutons comment un ordinateur quantique realiste peut simuler une dynamique complexe, en particulier les systemes chaotiques ou les fautes de l'ordinateur classique croissent exponentiellement vite.
L'ordinateur quantique (9) est un modele de calcul physiquement realisable (selon les regles de la mecanique quantique) utilisant les superpositions d'etats quantiques pour se donner acces a un parallelisme exponentiellement grand sur une quantite finie de matiere. En contrepartie a cette fantastique capacite de parallelisation, la theorie de la mecanique quantique limite tres severement la quantite et le type d'information qu'il est possible d'extraire de ces calculs fait en parallele par superposition quantique. Malgre ces contraintes, Deutsch donne un probleme specifique dont la solution demande un temps lineaire a toute machine de Turing (deterministe ou probabiliste) et seulement un temps logarithmique pour l'ordinateur quantique. Cet ecart exponentiel entre les deux modeles de calcul se limite-t-il a ce seul probleme ou bien est-ce que la hierarchie de complexite quantique est fondamentalement differente de la hierarchie de la hierarchie classique? La presente these explore les possibilites qu'offre le modele quantique.
La classe de complexite EQP est la classe des problemes decidables en temps polynomial exact sur un ordinateur quantique. Le premiere partie de cette these explore la position de EQP dans la hierarchie de complexite relativisee. Nous demontrons entre autre qu'il existe des oracles X, Y et Z relativement auxquels on a les inclusions suivantes: ${\bf P}\sp{X}\subseteq {\bf EQP}\sp{X}, {\bf EQP}\sp{Y}\not\subseteq {\bf NP}\sp{Y}\cup{\bf co}$-NP$\sp{Y}, {\bf EQP}\sp{Z}\not\subseteq {\bf ZPP}\sp{Z}, {\bf EQP}\sp{Z} \not\subseteq {\bf RP}\sp{Z} \cup {\bf co}$-${\bf RP}\sp{Z}$. Ces inclusions relativisees permettent de croire que l'ordinateur quantique est effectivement plus puissant qu'une machine de Turing.
Le modele quantique etant physiquement realisable et reellement plus puissant qu'une machine de Turing, on a toutes les raisons du monde de la construire. Malheureusement, les obstacles technologiques sont de taille. L'un de ces problemes (et non le moindre) est de maintenir un etat quantique stable pendant un certain temps. Peu importe les soins que nous mettons a l'isoler, un systeme quantique subit toujours de legeres perturbations causant des erreurs de calcul. Les techniques classiques pour reduire la propagation de ces erreurs (redondance et vote majoritaire, par exemple) ne sont pas applicables dans le cas quantique car elles detruiraient les superpositions. Deutsch propose donc une methode quantique de stabilisation des calculs. La seconde partie de cette these s'interroge sur l'efficacite de cette methode. La premiere constatation est que le comportement de la methode de stabilisation de Deutsch varie enormement en fonction du type de perturbations subi par l'ordinateur quantique. Nous avons donc choisi un modele d'erreur tres simple ayant le double avantage de permettre une analyse complete et detaillee de l'efficacite de la methode de stabilisation des calculs tout en etant suffisamment complexe pour etudier les diverses possibilites de celle-ci. Nous concluons que sous ce modele d'erreur, la methode de stabilisation des calculs proposee par Deustch est tres efficace et donne ainsi espoir que cette conclusion tient aussi sons un modele d'erreur plus realiste.
The evolution of a classically chaotic Hamiltonian system is characterised by a computational complexity that increases exponentially with the time elapsed. Quantum systems do not exhibit such behaviour. It is therefore tempting to solve a classical problem by quantising it and following the motion of a small wavepacket. This paper shows that nothing can be gained by this subterfuge: an adequate quantum simulation requires a Hilbert space whose dimension increases exponentially with the planned duration of the simulation.
Le calcul quantique est nouveau paradigme qui sera peut-être en capacité de résoudre certains problèmes intéressants et très spécifiques plus vite qu'un ordinateur classique. Mais pour atteindre le régime dans lequel les ordinateurs quantiques seront plus efficaces que leurs équivalents classiques, plusieurs étapes cruciales doivent être atteintes. Les taux d'erreur des puces quantiques actuelles doivent être drastiquement améliorés, tout comme leur nombre de qubits, les algorithmes doivent évoluer pour prendre en compte le taux d'erreur élevé des puces, les compilateurs et implémentations doivent être adaptés à la puce quantique qui sera utilisée pour l'exécution et les façons d'analyser des états ou programmes quantiques nécessitent des améliorations.Dans cette thèse, nous nous concentrons sur certaines de ces étapes et améliorons l'état de l'art en essayant de se rapprocher le plus possible du régime où les ordinateurs quantiques auront un avantage sur les ordinateurs classiques. Nous commençons par montrer comment nous avons implémenté un algorithme quantique non trivial et analysé son comportement ainsi que les ressources nécessaires à son exécution.Cette analyse a confirmé que les puces quantiques actuelles étaient incapables d'exécuter ce genre d'implémentation, même après avoir pris en compte les subtilités dues au matériel et optimisé grandement le programme. Cet effort d'optimisation a donné lieu à l'implémentation de l'outil qprof, un profileur de programme quantique capable d'analyser des implémentations et de générer un rapport textuel et lisible résumant la hiérarchie des appels et leur coût approximatif.Nous présentons aussi un algorithme classique pour résoudre le problème du routage de qubit, une des étapes les plus coûteuse en terme de porte quantique additionnelle dans les compilateurs de programme quantiques. Cet algorithme permet de prendre en compte les calibrations les plus récentes de la puce quantique visée afin d'adapter le programme quantique compilé aux différents taux d'erreurs de la puce. Nous décrivons comment l'algorithme fonctionne et montrons qu'il apporte une amélioration substantielle de la fidélité de l'état quantique créé par le programme compilé par rapport à l'état de l'art.Nous avons aussi implémenté un algorithme variationnel permettant de résoudre des systèmes linéaires et analysé son comportement sur des puces quantiques actuelles ainsi que les besoins en ressources quantiques afin d'exécuter cet algorithme avec différents systèmes linéaires. Finalement, nous avons effectué une étude sur les erreurs présentes sur des qubits isolés et introduit une nouvelle visualisation permettant de mettre en avant des erreurs systématiques et non mitigées par les calibrations automatiques réalisées à intervalles réguliers sur les puces quantiques.
Le calcul quantique est nouveau paradigme qui sera peut-être en capacité de résoudre certains problèmes intéressants et très spécifiques plus vite qu'un ordinateur classique. Mais pour atteindre le régime dans lequel les ordinateurs quantiques seront plus efficaces que leurs équivalents classiques, plusieurs étapes cruciales doivent être atteintes. Les taux d'erreur des puces quantiques actuelles doivent être drastiquement améliorés, tout comme leur nombre de qubits, les algorithmes doivent évoluer pour prendre en compte le taux d'erreur élevé des puces, les compilateurs et implémentations doivent être adaptés à la puce quantique qui sera utilisée pour l'exécution et les façons d'analyser des états ou programmes quantiques nécessitent des améliorations.Dans cette thèse, nous nous concentrons sur certaines de ces étapes et améliorons l'état de l'art en essayant de se rapprocher le plus possible du régime où les ordinateurs quantiques auront un avantage sur les ordinateurs classiques. Nous commençons par montrer comment nous avons implémenté un algorithme quantique non trivial et analysé son comportement ainsi que les ressources nécessaires à son exécution.Cette analyse a confirmé que les puces quantiques actuelles étaient incapables d'exécuter ce genre d'implémentation, même après avoir pris en compte les subtilités dues au matériel et optimisé grandement le programme. Cet effort d'optimisation a donné lieu à l'implémentation de l'outil qprof, un profileur de programme quantique capable d'analyser des implémentations et de générer un rapport textuel et lisible résumant la hiérarchie des appels et leur coût approximatif.Nous présentons aussi un algorithme classique pour résoudre le problème du routage de qubit, une des étapes les plus coûteuse en terme de porte quantique additionnelle dans les compilateurs de programme quantiques. Cet algorithme permet de prendre en compte les calibrations les plus récentes de la puce quantique visée afin d'adapter le programme quantique compilé aux différents taux d'erreurs de la puce. Nous décrivons comment l'algorithme fonctionne et montrons qu'il apporte une amélioration substantielle de la fidélité de l'état quantique créé par le programme compilé par rapport à l'état de l'art.Nous avons aussi implémenté un algorithme variationnel permettant de résoudre des systèmes linéaires et analysé son comportement sur des puces quantiques actuelles ainsi que les besoins en ressources quantiques afin d'exécuter cet algorithme avec différents systèmes linéaires. Finalement, nous avons effectué une étude sur les erreurs présentes sur des qubits isolés et introduit une nouvelle visualisation permettant de mettre en avant des erreurs systématiques et non mitigées par les calibrations automatiques réalisées à intervalles réguliers sur les puces quantiques.
This paper reviews recent work related to the interplay between quantum information and computation on the one hand and classical and quantum chaos on the other. First, we present several models of quantum chaos that can be simulated efficiently on a quantum computer. Then a discussion of information extraction shows that such models can give rise to complete algorithms including measurements that can achieve an increase in speed compared with classical computation. It is also shown that models of classical chaos can be simulated efficiently on a quantum computer, and again information can be extracted efficiently from the final wave function. The total gain can be exponential or polynomial, depending on the model chosen and the observable measured. The simulation of such systems is also economical in the number of qubits, allowing implementation on present-day quantum computers, some of these algorithms having been already experimentally implemented. The second topic considered concerns the analysis of errors on quantum computers. It is shown that quantum chaos algorithms can be used to explore the effect of errors on quantum algorithms, such as random unitary errors or dissipative errors. Furthermore, the tools of quantum chaos allows a direct analysis of the effects of static errors on quantum computers. Finally, we consider the different resources used by quantum information, and show that quantum chaos has some precise consequences on entanglement generation, which becomes close to maximal. For another resource, interference, a proposal is presented for quantifying it, enabling a discussion on entanglement and interference generation in quantum algorithms.
This paper explores the potential of quantum computing for simulating chaotic systems. Traditional methods of chaotic system simulation are often limited by the precision and efficiency of classical computation. This research proposes leveraging the unique capabilities of quantum computing, specifically quantum chaos algorithms, to overcome these limitations. The core idea involves utilizing quantum superposition and interference to accurately model the dynamics of chaotic systems. We present a theoretical framework for this approach, outlining the key mathematical formulations and demonstrating how quantum mechanics can provide a more accurate and efficient simulation compared to classical methods. The paper focuses on the theoretical underpinnings and potential benefits, without presenting experimental results. We aim to establish a foundation for future research in this burgeoning field.