Question:
Quelqu'un peut-il donner un exemple simple d'algorithme informatique quantique?
Humble
2011-01-20 08:26:19 UTC
view on stackexchange narkive permalink

Quelqu'un donne-t-il une bonne description d'un algorithme informatique quantique et en quoi il est différent d'un algorithme ordinaire?

Plus important encore, j'aimerais voir un exemple d'algorithme ** utile ** et une accélération ** exponentielle ** (** en dehors ** de la théorie des nombres / cryptographie), par ex.en optimisation.Grover, Deutsch et Shor ne sont pas assez excitants pour moi.Je regarderais aussi des listes comme: https://quantumalgorithmzoo.org/ (problème clair | accélération et [communauté maintenue] (https://github.com/stephenjordan/stephenjordan.github.io), yay!)
Deux réponses:
#1
+49
wsc
2011-01-20 11:01:27 UTC
view on stackexchange narkive permalink

J'éviterai de parler de l'algorithme de Shor et je vous laisserai le soin de le lire seul - L'algorithme de Shor est l'algorithme quantique , et c'est la raison pour laquelle l'informatique quantique est devenue un sujet d'actualité et n'est pas seulement une lecture incontournable, mais Scott Aaronson a fourni une meilleure introduction que je ne pourrais jamais réussir, http://www.scottaaronson.com/blog/?p=208

Au lieu de cela, je vais vous guider à travers l'algorithme de Deutsch, qui résout un problème incroyablement inutile exponentiellement plus rapidement que n'importe quel algorithme classique:


Imaginez que j'ai une fonction $ f $ sur une configuration de $ n $ bits, $ C = \ {0,1 \} ^ n $ qui prend chaque configuration sur un seul bit. Je vous promets à l'avance que cette fonction est soit:

  1. Constante - toutes les configurations sont mappées à la même valeur.
  2. Équilibré - exactement la moitié des configurations correspondent à $ 1 $, l'autre moitié à $ 0 $.

Donc classiquement, dans le pire des cas vous devez évaluer la fonction pour $ 2 ^ {n-1} + 1 $ configurations ( $ O (2 ^ n) $) pour vérifier dans quelle catégorie $ f $ appartient.


Maintenant, un ordinateur quantique n'est pas qu'un processeur parallèle, où vous pouvez lui donner une superposition des configurations et récupérer $ f $ évalué sur chacune d'elles. À la fin de la journée, vous devez effectuer une mesure qui détruit notre superposition soigneusement conçue - nous devons donc être intelligents! La caractéristique fondamentale d'un algorithme quantique est que nous utilisons des opérations unitaires pour transformer notre état et utiliser des interférences entre états de sorte que lorsque nous mesurons l'état à la fin, cela nous indique quelque chose de sans ambiguïté.

Donc, sans plus tarder, l'algorithme Deutsch pour $ n = 2 $ qubits (vous pouvez le faire pour beaucoup plus de qubits, bien sûr, mais vous vouliez un exemple simple ). La "version quantique" de notre fonction est une opération unitaire (une "porte quantique") qui me fait passer de $ | a \ rangle | b \ rangle $ à $ | a \ rangle | b + f (a) \ rangle $ ( où l'addition est modulo 2). Je dispose également d'une porte qui prend n'importe quel bit et le met dans une superposition particulière:

$$ | 1 \ rangle \ rightarrow (| 0 \ rangle- | 1 \ rangle) / \ sqrt { 2} $$

$$ | 0 \ rangle \ rightarrow (| 0 \ rangle + | 1 \ rangle) / \ sqrt {2} $$

La première étape de l'algorithme est de préparer mes deux qubits comme $ | 0 \ rangle | 1 \ rangle $ puis d'appliquer cette transformation en me donnant l'état $ (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle- | 1 \ rangle) / 2 $. Maintenant, j'évalue la fonction en appliquant la porte que j'ai décrite précédemment, en prenant mon état à

$$ [| 0 \ rangle (| 0 + f (0) \ rangle- | 1 + f (0) \ rangle) + | 1 \ rangle (| 0 + f (1) \ rangle- | 1 + f (1) \ rangle)] / 2 $$

Si nous regardons cela attentivement, et réfléchissons arithmétique mod 2, on voit que si $ f (0) = 1 $ le premier terme prend un signe moins par rapport à son état avant, et si $ f (0) = 0 $ rien ne se passe. Nous pouvons donc réécrire l'état comme

$$ [(- 1) ^ {f (0)} | 0 \ rangle (| 0 \ rangle- | 1 \ rangle) + (- 1) ^ { f (1)} | 1 \ rangle (| 0 \ rangle- | 1 \ rangle)] / 2 $$

ou regroupement

$$ (| 0 \ rangle + (- 1) ^ {f (0) + f (1)} | 1 \ rangle) (| 0 \ rangle- | 1 \ rangle) / 2 $$

Maintenant, nous perdons le deuxième qubit (nous ne J'en ai plus besoin, et ce n'est pas enchevêtré avec le premier bit), et appliquer à nouveau la deuxième transformation que j'ai listée (et en regroupant, l'algèbre est simple mais fastidieuse) - enfin, notre état final est

$$ [(1 + (- 1) ^ {f (0) + f (1)}) | 0 \ rangle + ((1 - (- 1) ^ {f (0) + f (1)}) | 1 \ rangle] / 2 $$

Et enfin, on mesure! Il devrait être clair d'après l'état ci-dessus que nous avons résolu le problème ... Si $ f $ est constant, alors $ f (0) = f (1) $ et nous mesurerons toujours $ | 0 \ rangle $, et si $ f $ est équilibré alors $ f (0) \ neq f (1) $ et nous mesurons toujours $ | 1 \ rangle $.

Quelques derniers commentaires: j'espère que cela vous donne un peu de goût pour la structure d'un algorithme quantique, même si cela semble être une chose inutile - je vous recommande fortement d'aller lire l'article auquel j'ai lié au début de cette réponse .

beau travail. + 1. Il est bon de voir le nombre croissant de questions et réponses bien formées sur ce site!
"Désormais, un ordinateur quantique n'est pas seulement un processeur parallèle, où vous pouvez lui donner une superposition des configurations et obtenir une évaluation sur chacune d'elles." En fait, ce n'est même pas un processeur parallèle. Le parallélisme quantique n'est pas la même chose que d'avoir un ordinateur classique exponentiellement parallèle, bien qu'un ordinateur classique exponentiellement parallèle puisse simuler efficacement un ordinateur quantique.
Merci Joe, c'est vraiment ce que je voulais souligner, même si mon choix de mots était plutôt médiocre.
Je pense que le lien est mort
Quelle est la formule juste après «nous avons perdu le deuxième qubit»?Pourquoi est-ce permis?
#2
+32
Joe Fitzsimons
2011-01-20 15:29:21 UTC
view on stackexchange narkive permalink

Ok, puisque wsc vous a donné une explication de l'algorithme de Deutsch, laissez-moi vous parler d'un autre algorithme, plus utile: l'algorithme de recherche de Grover. Il s'agit d'un algorithme de recherche pour une base de données non triée, ou pour rechercher une boîte noire pour l'entrée qui aboutit à une sortie spécifique (une primitive très utile dans les algorithmes). Pour un ensemble d'entrées $ N $, en supposant qu'il n'y a qu'une entrée satisfaisant la requête de recherche, l'algorithme ne prend que les requêtes $ O (\ sqrt {N}) $, alors que le meilleur algorithme classique possible prend les requêtes $ O (N) $ de la base de données. De plus, l'algorithme de Grover (avec une petite modification que je n'entrerai pas ici) est prouvé optimal. Alors, comment ça marche?

Supposons qu'il existe une base de données de $ 2 ^ n $ entrées. Nous préparons d'abord une superposition d'états classiques $ 2 ^ n $ à phase positive: $ \ mid S \ rangle = 2 ^ {- \ frac {n} {2}} \ sum_ {x = 1} ^ {2 ^ n} | x \ rangle $. Ceci peut être fait simplement en appliquant une seule porte quantique (dans ce cas une porte Hadamard) à chacun des $ n $ qubits initialement préparés à l'état zéro. Je vais représenter les états rencontrés par un diagramme, où la longueur de chaque ligne représente son amplitude dans la superposition, et s'il s'agit d'une direction à partir de la ligne centrale pour indiquer sa phase (dans ce cas, elle sera toujours positive ou négative) . L'état que nous obtenons après cette étape d'initialisation est alors décrit comme ci-dessous.

alt text

L'algorithme lui-même se compose de $ r $ tours qui se composent chacun de deux étapes:

  1. La phase d'un état classique dans la superposition est inversée si (et seulement si) l'entrée de la base de données à cet emplacement correspond à la requête de recherche, comme illustré ci-dessous. Ici, nous supposons que l'entrée $ m $ est l'entrée correspondant à la requête de recherche. Notez qu'il ne s'agit que d'une seule requête à la base de données, qui a des effets différents dans chaque branche de la fonction wave. Ceci est réalisé en appliquant un opérateur $ U_m = I - 2 | m \ rangle \ langle m | $

alt text

  1. L'opérateur «inversion sur la moyenne» est appliqué. Il s'agit simplement d'un opérateur unitaire donné par $ U_S = 2 | S \ rangle \ langle S | - I $, où comme avant $ | S \ rangle = 2 ^ {- \ frac {n} {2}} \ sum_ {x = 1} ^ {2 ^ n} | x \ rangle $. L'effet de cet opérateur est très simple: l'amplitude $ A_i $ de chaque entrée $ i $ est portée à $ 2 \ mu - A_i $, où $ mu $ est l'amplitude moyenne. Cela équivaut à inverser la distance au-dessus ou au-dessous de la moyenne. Le premier diagramme ci-dessous illustre où se trouve la moyenne, tandis que le second montre l'effet de l'application de cet opérateur.

alt text

alt text

Il est clair que cette opération a pour effet d'amplifier l'amplitude de l'entrée correspondant à la requête de recherche, et cela continuera jusqu'à ce que la moyenne se trouve en dessous de la ligne zéro (après $ r $ arrondis). Cela se produit après les requêtes $ O (\ sqrt {N}) $. Pour voir cela, nous notons d'abord que l'état du système après chaque tour $ i $ peut toujours être écrit sous la forme $ | \ psi_i \ rangle = \ cos \ theta_i | s \ rangle + \ sin \ theta_i | m \ mid $, où $ | s \ rangle = (2 ^ n - 1) ^ {- \ frac {1} {2}} \ sum_ {x \ neq m} | x \ rangle $. Clairement $ | s \ rangle $ et $ | m \ rangle $ sont orthogonaux, nous pouvons donc représenter n'importe quel état rencontré comme vecteur unitaire dans le plan 2D couvert par $ | s \ rangle $ et $ | m \ rangle $.

alt text

Considérons l'effet d'un seul tour. Tout d'abord $ U_m $ est appliqué, puis $ U_S $ est appliqué. Notez que $ U_S = 2 | S \ rangle \ langle S | - I = (\ frac {2 (2 ^ n - 1)} {2 ^ n} -1) | s \ rangle \ langle s | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | s \ rangle \ langle m | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | m \ rangle \ langle s | + (\ frac {2} {2 ^ n} - 1) | m \ rangle \ langle m | $. Lorsque nous multiplions cela par $ U_m $ pour obtenir l'opération totale appliquée dans un tour $ U_S U_m = (\ frac {2 (2 ^ n - 1)} {2 ^ n} -1) | s \ rangle \ langle s | - \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | s \ rangle \ langle m | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | m \ rangle \ langle s | + (\ frac {2 (2 ^ n - 1)} {2 ^ n}) | m \ rangle \ langle m | $. Il s'agit simplement d'une rotation d'un angle constant $ \ phi = \ sin ^ {- 1} (\ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n}) \ approx \ frac {2} {\ sqrt {2 ^ n}} $ pour gros $ n $. Puisque nous commençons initialement très près de l'état $ | s \ rangle $, nous avons donc besoin de $ r \ approx \ frac {2} {\ sqrt {2 ^ n}} $, ce qui signifie que nous atteignons l'amplitude maximale pour $ | m \ rangle $ en seulement ~ $ 2 \ sqrt {N} $ requêtes de la base de données.

Il est facile de voir que cela est impossible classiquement, car si vous faites des requêtes $ m $ dans la base de données, il y a toujours des entrées $ Nm $ qui n'ont pas été vérifiées qui peuvent éventuellement correspondre au terme de recherche, ce qui signifie qu'un nombre linéaire d'entrées doit être vérifié pour assurer même une probabilité constante de trouver la bonne entrée.

est utile

C'est vraiment difficile quand on est obligé de choisir une bonne réponse plutôt qu'une autre +1
Explication la plus claire de Grover que j'ai jamais vue.Merci!
5 années !Une bonne réponse en quelques lignes ... Seulement sur la conclusion: le réglage est-il à nouveau utilisable?pour préparer les états, cet algo doit lire toutes les entrées.Cela fonctionne-t-il à chaque fois ou une fois?Au contraire, les algos classiques peuvent ordonner la liste une fois et après, obtenir n'importe quelle valeur après que Log N essaie.
@igael: Il ne trie pas la liste, trouve simplement l'élément marqué.
Grover est potentiellement super utile en pratique, mais j'aimerais qu'il y ait un exemple de quelque chose qui soit utile avec une accélération exponentielle (en dehors de la théorie des nombres / cryptographie).


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 2.0 sous laquelle il est distribué.
Loading...