Qu'est-ce que le modèle de calcul quantique?

J'ai parfois entendu des gens parler d'algorithmes quantiques et d'états et de la possibilité d'envisager plusieurs possibilités à la fois, mais je n'ai jamais réussi à demander à quelqu'un d'expliquer le modèle de calcul derrière cela. Pour être clair, je ne demande pas comment les ordinateurs quantiques sont construits physiquement, mais plutôt comment les voir d'un point de vue informatique.

Je ferai écho à la recommandation de Martin Schwartz de Nielsen & Chaung comme référence standard; il y en a bien d'autres aussi.

La recherche dans le domaine préfère considérer des familles uniformes de circuits quantiques, qui (ironiquement) sont des réseaux acycliques dirigés décrivant comment l'état d'un ou plusieurs registres se transforme avec le temps, d'une manière similaire aux circuits booléens classiques. Si vous souhaitez en savoir plus, je vous recommande d'apprendre en fonction de ce modèle.

Je voudrais donner quelques réponses qualitatives pour compléter la réponse de Martin.

1. Le calcul quantique ne considère pas réellement "plusieurs possibilités à la fois" --- ou plus précisément, que vous les considériez ou non considérer plusieurs possibilités à la fois est une question de votre choix d' interprétation de la mécanique quantique , c'est-à-dire un choix philosophique qui n'a pas portant sur la capacité ou les prévisions du modèle de calcul. («Envisager plusieurs possibilités à la fois» correspond à «l'interprétation de plusieurs mondes» de QM.)
   
   À tout le moins, on peut dire qu'un ordinateur quantique ne considère plusieurs possibilités en même temps que dans la mesure où un calcul aléatoire utilisant des pièces de monnaie flips considère plusieurs possibilités en même temps. Ceci est dû au fait:

2. Les états quantiques sont des généralisations des distributions de probabilité "habituelles" --- avec quelques différences simples mais importantes. Une distribution de probabilité peut être représentée comme un vecteur réel non négatif dont les entrées totalisent 1: c'est-à-dire un vecteur unitaire dans la norme ℓ ¹ . Les calculs probabilistes doivent mapper des vecteurs à ¹ unité à d'autres vecteurs de ce type, et ils sont donc décrits par des cartes stochastiques. On peut décrire le calcul quantique de manière similaire, sauf en utilisant des vecteurs à ℓ ² unités sur ℂ (non limité à être réel ou non négatif); les transformations sont effectuées par les cartes qui préservent la norme ℓ ² , c'est-à-dire les opérations unitaires.
   
   Cette différence n'est pas trivial, bien sûr, ni expliquer encore ce que les coefficients des vecteurs d'état quantique signifient . Mais cela peut aider à expliquer ce qui se passe avec les espaces de Hilbert et les produits tenseurs dans le calcul quantique: à savoir, exactement les mêmes choses que celles qui se produisent dans le calcul probabiliste. L'espace de configuration d'un bit aléatoire est un vecteur en ℝ ₊ ² (où ℝ ₊ sont les réels non négatifs); mais comme les bits aléatoires peuvent être corrélés, nous combinons les espaces de configuration d'un ou plusieurs bits aléatoires en prenant le produit tensoriel. L'espace de configuration de deux bits aléatoires est donc ℝ ₊ ²  ⊗ ℝ ₊ ²  ≅ ℝ ₊ ⁴ , ou l'espace entièrement général des distributions de probabilité sur les quatre chaînes distinctes de deux bits. Une opération A sur le premier de ces bits aléatoires qui n'agit pas sur le second est représentée par l'opérateur A  ⊗  I ₂  . Etc. Les mêmes constructions s'appliquent aux bits quantiques; et nous pouvons considérer les registres quantiques sur des ensembles d'éléments distinguables de la même manière que nous considérons les distributions de probabilité sur ces ensembles, en utilisant à nouveau des vecteurs normaux ℓ ² sur ℂ.
   
   Cette description décrit en fait les états quantiques "purs" --- ceux pour lesquels vous pouvez en principe transformer de manière préservant les informations en une distribution delta sur la chaîne de bits 00 ... 0 (ou plus précisément, en un état arbitrairement proche de celui-ci dans la norme ℓ ² ). En plus de l'aléatoire quantique (dont je n'ai encore rien mentionné d'explicite), vous pouvez considérer l'aléatoire vanille-convexité correspondant à des mélanges probabilistes d'états quantiques: ceux-ci sont représentés par des opérateurs de densité , qui peuvent être représentés par des matrices définies positives avec trace 1 (généralisant à nouveau les distributions de probabilité "classiques", qui peuvent être représentées par le cas particulier des matrices diagonales positives avec trace 1).
   
   Ce qui est important à ce sujet, c'est que, si les états quantiques sont souvent décrits comme étant «exponentiellement grands», c'est parce qu'ils sont généralement décrits en utilisant les mêmes structures mathématiques que les distributions de probabilité; pourquoi les distributions de probabilités ne sont pas décrites comme "exponentiellement grandes" de la même manière n'est pas claire (mais finalement sans importance). La difficulté de simuler des états quantiques vient de ce fait, ainsi que du fait que les coefficients complexes de ces distributions ℓ ² (ou les termes complexes hors diagonale des opérateurs de densité, si vous préférez) peuvent s'annuler d'une manière que les probabilités ne peuvent pas , ce qui rend leur estimation plus difficile.

3. L'intrication n'est qu'une autre forme de corrélation. Pour le calcul probabiliste, par exemple sur des chaînes booléennes, les seuls états "purs" (qui peuvent être mappés par des transformations préservant les informations vers une distribution à pic delta sur 000 ... 0) sont la "base standard" des distributions à pic delta sur le différentes chaînes booléennes. Ainsi, cette base de ℝ ₊ ^{2 n}se distingue. Mais il n'y a pas de base aussi distinguée en mécanique quantique, pour autant que nous puissions le dire - c'est le plus clair pour les bits quantiques (recherchez les particules de spin 1/2, si vous voulez savoir pourquoi). En conséquence, il y a plus de transformations préservant l'information que les permutations: un groupe continu d'entre elles, en fait. Cela permet aux ordinateurs quantiques potentiels de transformer les états d'une manière qui n'est pas possible pour les ordinateurs probabilistes, obtenant éventuellement un avantage asymptotique sur eux.
   
   Mais qu'en est-il de l'enchevêtrement, que beaucoup de gens trouvent mystérieux, et prétendent être la cause de l'accélération des ordinateurs quantiques par rapport au classique? L '«enchevêtrement» n'est ici qu'une forme de corrélation: tout comme deux variables aléatoires sont corrélées si leur distribution est une combinaison convexe de plusieurs distributions de produits (avec des marginaux différents sur chaque variable), deux «variables quantiques» sont enchevêtrées si leur la distribution est une combinaison linéaire (avec l'unité ℓ ²-norm) de deux distributions de produits valides; c'est le même concept sous une norme différente, et joue un rôle similaire dans les tâches de communication. (Par exemple: la "téléportation quantique" dans une communication quantique correspond au codage et au décodage d'un message utilisant un pavé à usage unique de façon classique.) Il s'agit d'une forme de corrélation qui est plus générale que les seuls bits corrélés de façon classique; mais la seule façon de le montrer est que les corrélations codées à l'état intriqué s'appliquent à plus d'une base privilégiée . D'une certaine manière, l'intrication est une conséquence de l'absence de base privilégiée.
   
   Les gens aiment invoquer l'intrication comme élément clé du calcul quantique, mais cela ne semble tout simplement pas tenir le coup: des résultats ont montré quel'intrication n'est pas quantitativement importante pour l'algorithme de Shor pour factoriser de grands nombres entiers, et qu'en effet un système quantique peut avoir trop d'intrication pour être utile pour un calcul. En fait, partout où je suis conscient que l'intrication joue un rôle important dans un protocole quantique, c'est essentiellement une question de communication (où les corrélations devraient jouer un rôle important pour un protocole classique).

À ce stade, je commence à patauger dans le domaine de l'opinion personnelle, alors je m'arrête ici. Mais j'espère que ces remarques pourraient démystifier une partie de ce qui est obscur au sujet du calcul quantique et de la façon dont il est décrit.

Lance Fortnow a écrit un article qui explique l'informatique quantique sans utiliser la mécanique quantique. Il le présente essentiellement de la même manière que l'on présenterait l'informatique probabiliste. Je soupçonne que cela peut être un point de départ plus rapide que quelque chose comme Nielson et Chuang (bien que je convienne que si vous voulez vraiment y aller, Nielson et Chung devraient certainement être sur votre liste de lecture).

L. Fortnow. Vue d'un théoricien de la complexité de l'informatique quantique. Informatique théorique, 292 (3): 597-610, 2003. Numéro spécial d'articles présentés au deuxième atelier sur les algorithmes dans le traitement de l'information quantique.

Eh bien, le texte standard utilisé est le calcul quantique et l'information quantique par Nielsen et Chuang. Il couvre un large éventail d'aspects différents à un niveau raisonnable. Presque tous ceux qui travaillent sur le terrain en ont une copie sur leur étagère. Le livre de Kaye, Laflamme et Mosca est également bon, mais couvre moins (bien qu'il y ait un peu plus d'attention sur les algorithmes).

Bien qu'il soit tout à fait possible d'expliquer l'informatique quantique sans entrer dans beaucoup de mécanique quantique, je ne pense pas que ce soit nécessairement une bonne façon d'aborder l'apprentissage du calcul quantique. Il y a beaucoup d'intuition à acquérir en ayant une idée de la théorie physique, car bon nombre des modèles les plus récents de calcul quantique (c'est-à-dire les modèles adiabatiques, topologiques et basés sur des mesures) sont plus motivés physiquement que la machine de Turing quantique ou le modèle de circuit.

Cela dit, la mécanique quantique requise pour comprendre le calcul quantique est assez simple et est assez bien couverte dans Nielsen et Chuang. Vraiment, vous pouvez vous en rendre compte en lisant le chapitre correspondant et en essayant les exercices. C'est le genre de chose que vous pouvez comprendre avec quelques jours de travail. Mon conseil, cependant, est de ne pas opter pour un texte d'introduction standard à la mécanique quantique. L'approche adoptée pour modéliser les atomes, les molécules et les matériaux utilise des systèmes de dimension infinie, et demande beaucoup plus d'efforts pour y arriver. Pour les informations quantiques, il est préférable de commencer à regarder les systèmes de dimension finie. De plus, traditionnellement, les problèmes étudiés par les physiciens ont tendance à tourner autour de la recherche d'états fondamentaux et de comportements à l'état stationnaire, et c'est ce que couvriront la plupart des textes d'introduction (à commencer par l'équation d'onde de Schroedinger indépendante du temps). Pour l'informatique quantique, nous avons tendance à nous intéresser davantage à l'évolution temporelle des systèmes, et cela est traité de manière beaucoup plus succincte dans les textes d'informatique quantique que dans les textes d'introduction à la mécanique quantique générale (qui sont par définition plus généraux).

$BQP$

$|\phi\rangle$$\cal{H_2}$$\cal{H_2} \otimes ... \otimes \cal{H_2}$$|\psi\rangle$$U$$square$

Pour une introduction plus approfondie, veuillez consulter le manuel standard Nielsen et Chuang.

Tout d'abord, vous devrez comprendre la physique quantique.

Quelques recommandations:

1. " L'informatique quantique pour les informaticiens " par Noson S. Yanofsky et Mirco A. Mannucci
2. "Une introduction à l'informatique quantique" par Phillip Kaye, Raymond Laflamme et Michele Mosca

Et du côté le plus divertissant, "Un raccourci dans le temps: le chemin vers l'ordinateur quantique" de George Johnson.

Vous pouvez avoir une belle introduction dans l'article "Une introduction à l'informatique quantique pour les non-physiciens" par Eleanor Rieffel et Wolfgang Polak. Il est peut-être un peu ancien, mais il s'agit toujours d'une bonne introduction courte et autonome au sujet: http://arxiv.org/abs/quant-ph/9809016

Un autre article, beaucoup plus résumé, est le "calcul quantique expliqué par Pablo Arrighi à ma mère" sur http://arxiv.org/abs/quant-ph/0305045

Vous le savez probablement déjà, mais sur son blog , Scott Aaronson a des liens vers un certain nombre de ses cours sur l'informatique quantique, ainsi que des liens vers des amorces QC par d'autres (faites simplement défiler la barre latérale droite pour les trouver) .

Si vous souhaitez une introduction d'un livre, mais quelque chose de plus doux qu'un texte comme Nielsen et Chuang, je recommanderais l' informatique quantique pour les informaticiens de Yanofsky et Mannucci. Ils passent beaucoup de temps à passer en revue les prérequis mathématiques avant de plonger dans le QC lui-même. Si vous avez une solide formation en mathématiques, ce livre peut sembler trop basique, mais je l'ai trouvé très utile.

En général, j'appuierais le conseil de Joe. Mais pour une introduction rapide, je mettrais les textes de Lance Fortnow et Stephen Fenner sur la liste de lecture des informaticiens qui vont quantiques.

Si vous êtes assez avancé, vous pourriez commencer par l' enquête de Wolf-Drucker sur les méthodes quantiques pour les problèmes classiques. C'est un bon moyen de comprendre les techniques quantiques avant d'aborder les problèmes quantiques .

Je ne pense pas que vous ayez besoin d'apprendre la mécanique quantique. Cependant, cela dépend du domaine dans lequel vous souhaitez travailler. Il y a des domaines du domaine qui ont vraiment besoin de connaissances sur la mécanique quantique, mais comme par exemple le domaine sur lequel je travaille, la théorie des types et le calcul lambda, je n'en ai pas besoin, je peux le faire simplement en connaissant certains des modèles de calcul pour cela.

Outre son texte standard avec Chuang, Michael Nielsen a une série de conférences vidéo sur Youtube intitulée Quantum Computing for the Determined qui donne jusqu'à présent un aperçu du modèle de calcul. Les vidéos sont très accessibles à tous ceux qui ont une petite compréhension de l'informatique et de l'algèbre linéaire.