Quelqu'un peut-il donner un exemple simple d'algorithme informatique quantique?

Question

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?

Answer 1

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 .

Answer 2

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.

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 | $

2. 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.

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 $.

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