Modèles de calcul quantique

Le calcul quantique remplace les bits classiques par des états quantiques qui peuvent être superposés et intriqués, définissant des modèles tels que le circuit quantique et la classe de complexité BQP qui semblent résoudre certains problèmes plus rapidement que toute méthode classique.

Definition

Un modèle de calcul quantique traite l'information stockée dans des qubits dont les états sont des vecteurs unitaires dans un espace complexe ; le calcul applique des portes quantiques réversibles pour créer la superposition et l'intrication, et une mesure finale produit un résultat classique avec des probabilités définies par l'état quantique.

Scope

Ce sujet aborde les qubits et les portes quantiques, le modèle du circuit quantique et son équivalence avec la machine de Turing quantique, la classe de complexité BQP du calcul quantique efficace et sa relation avec les classes classiques, les algorithmes fondamentaux tels que la factorisation de Shor et la recherche de Grover, ainsi que le rôle de la mesure et de la décohérence dans la définition du modèle.

Core questions

• Comment la superposition et l'intrication modifient-elles les capacités d'un calcul ?
• Quelle est la relation entre la classe quantique efficace BQP et les classes classiques ?
• Pour quels problèmes les algorithmes quantiques offrent-ils une accélération prouvable ou apparente ?
• Comment la mesure et le principe de non-clonage contraignent-ils le calcul quantique ?

Key theories

Modèle du circuit quantique et BQP

Le calcul quantique efficace est caractérisé par des circuits quantiques de taille polynomiale sur un ensemble de portes universel, définissant la classe BQP, qui contient P et est censée l'étendre tout en restant dans PSPACE.

Accélérations quantiques

L'algorithme de Shor factorise les entiers en temps polynomial et l'algorithme de Grover recherche un espace non structuré avec une accélération quadratique, démontrant des avantages concrets du modèle quantique pour des tâches spécifiques.

Clinical relevance

Les modèles quantiques guident la conception du matériel et des algorithmes quantiques ; l'algorithme de factorisation de Shor menace les cryptosystèmes à clé publique dont la sécurité repose sur la difficulté de la factorisation, motivant le développement de la cryptographie post-quantique, tandis que la simulation quantique promet des avancées en chimie et en science des matériaux.

History

Feynman a proposé d'utiliser des systèmes quantiques pour simuler la physique en 1982, et Deutsch a formalisé la machine de Turing quantique en 1985. L'algorithme de factorisation de Shor en 1994 et l'algorithme de recherche de Grover en 1996 ont montré des accélérations concrètes, transformant le calcul quantique en une branche majeure de la théorie de la complexité et un moteur d'efforts expérimentaux.

Debates

Quelle est l'ampleur de l'avantage quantique, et est-il physiquement réalisable à grande échelle ?

Les ordinateurs quantiques calculent les mêmes fonctions que les ordinateurs classiques ; la question est donc celle de l'efficacité. La relation précise entre BQP et les classes classiques n'est pas résolue, et la question de savoir si de grands ordinateurs quantiques tolérants aux pannes peuvent être construits malgré la décohérence reste une question scientifique et d'ingénierie ouverte.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

Les ordinateurs quantiques calculent-ils des choses que les ordinateurs classiques ne peuvent pas ?

Non. Les ordinateurs quantiques résolvent exactement la même classe de problèmes que les ordinateurs classiques ; la différence réside dans la vitesse. Pour certains problèmes, comme la factorisation de grands nombres, le modèle quantique semble être considérablement plus rapide, mais il n'étend pas la limite de ce qui est calculable en principe.

Pourquoi le calcul quantique est-il important pour la cryptographie ?

L'algorithme de Shor permettrait à un grand ordinateur quantique de factoriser efficacement de grands entiers et de calculer des logarithmes discrets, brisant les systèmes à clé publique qui sécurisent une grande partie des communications actuelles. Cette perspective a stimulé la recherche de schémas post-quantiques basés sur des problèmes considérés comme difficiles même pour les machines quantiques.