Algorithme de Grover

[invite6c250b59]

Bonjour,

Page 269 du Nielsen et Chuang, il y a une image pour expliquer comment mettre une suite d'info classiques dans un état quantique, et ça me bug.
fig 6-9.bmp

légende traduite à l'arrache: "chaque cercle represente un switch, quand [x2> vaut [0>, le qubit va en bas; quand il vaut [1>, il va en haut; quand c'est un état 1/sqrt(2)*([0>+[1>), une superposition des deux routes est prise"

=> je comprend donc qu'il s'agit de polarized beam splitter. q1: correct? q2: au fait, est-ce qu'il y a une traduction jolie pour PBS et BS en français?

suite de la légende au pied de biche: "donc on met 4 qubits dans un état "steered using non linear interferometers" ("intriqués" j'imagine. q3: c'est bien ça que ça veut dire?) à la colonne x2 à gauche¹, avec des d1, d2, d3, d4 qui au choix laissent passer chaque photon tel quel ou le polarise de 90°. Par reconstruction on va obtenir à la colonne x2 à droite des qubits contenant l'information codée par le caractère tourne/tourne pas des d1, d2, d3, d4"

Ce qui me bug vraiment, c'est qu'une fois passé un PBS, la polarisation devrait être obligatoire ou j'ai rien compris. Autrement dit, si un photon passe en bas de x2 à x1, alors il devrait par la suite toujours prendre la route du bas. De même un photon passant en haut à une polarisation définie, donc devrait par la suite toujours aller en haut. Donc dans le schéma ci-dessous seules les routes en gris devraient être possible.
fig 6-9-prime.bmp

question 4: Non? Pourquoi non?

question 5: comme je comprend ça, si on remplace les PBS des colonnes x2 et x1 par des beam splitters non polarisant, alors ok là ça devrait marcher tel qu'annoncé. Oui?

question 6: comment on exprime l'état quantique final connaissant la nature des d1, d2, d3, d4 (laissent passer le photon ou le polarise de 90°)?

D'avance merci!


¹voir chapitre 7 pour comprendre pour quoi on peut pas en fait
-----

[invite6c250b59]

PS: la base de mesure c'est :
[0> "il est là"
[1> "il est pas là"
1/sqrt(2)*([0>+[1>) "pt'être ben que oui, pt'être ben que non"

[invite6c250b59]

q2: au fait, est-ce qu'il y a une traduction jolie pour PBS et BS en français?

-"Polariseur" et "Lame séparatrice" semblent pas mal.

-oh merci Jiav!

-de rien mon petit

[invite0bbfd30c]

au fait, est-ce qu'il y a une traduction jolie pour PBS et BS en français?

PBS (polarizing beam splitter) : séparateur de polarisations, BS (beam splitter) : séparatrice. Mais ce n'est pas une correspondance parfaite, car quant on dit séparatrice, on sous-entend assez fortement "lame séparatrice", alors qu'en réalité il peut s'agir d'un cube. Bref...

je comprend donc qu'il s'agit de polarized beam splitter

Non. Bien que la réalisation physique du dispositif ("switch") n'est pas explicite, ce ne sont certainement pas des PBS. Ces commutateurs sont des dispositifs pouvant diriger un photon incident selon deux sorties possibles, non pas en fonction de la polarisation du photon incident, mais en fonction d'un qubit de contrôle. Si le qubit de contrôle (d'un tel commutateur) est un photon, la réalisation physique envisagée par les auteurs fait appel à un milieu non linéaire (pour obtenir une interaction photon-photon).

suite de la légende au pied de biche: "donc on met 4 qubits dans un état "steered using non linear interferometers" ("intriqués" j'imagine. q3: c'est bien ça que ça veut dire?

Non, ça veut juste dire qu'ils ont été dirigés selon les états des commutateurs (switches). Ils sont donc, en général, dans un état superposé (et bien entendu intriqués avec les états des qubits de contrôle agissant sur les commutateurs).

[A voir en vidéo sur Futura]

[invite6c250b59]

Bref...

Bref merci

Bien que la réalisation physique du dispositif ("switch") n'est pas explicite, ce ne sont certainement pas des PBS.

Oui, je me rend compte que j'avais (mal) supposé au départ que [0> et [1> faisaient référence à la polarisation. C'est pas le cas donc c'est pas des PBS mais plutôt des BS. Sauf que... si c'était si simple pourquoi parleraient-ils de "switch" plutôt que de BS? Cela doit pas être ça non plus!

Ces commutateurs sont des dispositifs pouvant diriger un photon incident selon deux sorties possibles, non pas en fonction de la polarisation du photon incident, mais en fonction d'un qubit de contrôle. Si le qubit de contrôle (d'un tel commutateur) est un photon, la réalisation physique envisagée par les auteurs fait appel à un milieu non linéaire (pour obtenir une interaction photon-photon).
(...)
ils ont été dirigés selon les états des commutateurs (switches). Ils sont donc, en général, dans un état superposé (et bien entendu intriqués avec les états des qubits de contrôle agissant sur les commutateurs).

Si je comprend bien tu veux dire que chaque switch intrique le "photon passant par lui" avec un autre (ou un autre état quantique), non représenté sur la figure, dont la présence détermine si le "photon passant" passe par lui. Correct?

[invite0bbfd30c]

Si je comprend bien tu veux dire que chaque switch intrique le "photon passant par lui" avec un autre (ou un autre état quantique), non représenté sur la figure, dont la présence détermine si le "photon passant" passe par lui. Correct?

Les qubits (éventuellement portés par des photons) déterminant l'état de chaque commutateur sont inscrits dans les cercles de la figure (c'est bien précisé dans la légende). Selon l'état du commutateur, le qubit incident (à ne pas confondre avec les qubits de contrôle qui déterminent les états des commutateurs) sort selon l'une ou l'autre des voies de sorties (ou une superpositions des deux, en général). Je pense que tu es allé un peu vite à la lecture de la légende

[invite6c250b59]

Je pense que tu es allé un peu vite à la lecture de la légende

Each circle represents a switch, addressed by the qubit inscribed within. Merding si tu savais le temps que j'ai passé sur ce truc alors que c'est écrit en toutes lettres. Merci Chip!

Next si tu le veux bien. "The qubits are then routed back": est-ce qu'il faut comprendre que les qubits de contrôle X0, X1, etc à l'aller sont les mêmes que les qubits de contrôle X0, X1, etc du retour? (ce qui expliquerait qu'ils aient le même petit nom...)

[invite0bbfd30c]

Next si tu le veux bien. "The qubits are then routed back": est-ce qu'il faut comprendre que les qubits de contrôle X0, X1, etc à l'aller sont les mêmes que les qubits de contrôle X0, X1, etc du retour? (ce qui expliquerait qu'ils aient le même petit nom...)

C'est ce qui est dit, effectivement. Par contre je ne saisis pas exactement le principe de cette second partie du schéma -- il faudrait, à mon sens, représenter les quatre voies des commutateurs (ce qui n'était pas obligatoire pour la première partie, les secondes voies d'entrée des commutateurs étant vides). Enfin bon, je n'ai pas regardé ça dans le détail...

[invite6c250b59]

je ne saisis pas exactement le principe de cette second partie du schéma -- il faudrait, à mon sens, représenter les quatre voies des commutateurs

Je crois que je comprend pourquoi ce n'est pas nécessaire: les changements de polarisation en d1-d4 sont indépendants de la position des photons. Donc ils n'ont pas plus d'effet sur les chemins que des miroirs. Donc le retour est complètement symétrique, en ce qui concerne les superpositions de chemins, que l'aller. Donc au niveau des "switchs" (pour autant que leur fonctionnement ne se base aucunement sur la polarisation) c'est symétrique aussi, et les "secondes voies d'entrées" se retrouvent à zéro autant à l'aller qu'à la sortie, et on peut les négliger dans les deux cas. Cool.

Next: je comprends toujours pas bien en quoi ça fait une mémoire, mais je demande si on peut pas utiliser ce principe, au moins en théorie, pour faire du calcul. Par exemple sur mon schéma si seul d1 tourne la polarisation, alors la polarisation dépend de ET(x2, x1) selon la table de vérité

x2 x1 final
0 0 tourne
0 1 passe
1 0 passe
1 1 passe

de même si d2 et d3 font tourner la polarisation alors la polarisation finale est un XOU de x2 et x1 selon la table de vérité

x2 x1 final
0 0 passe
0 1 tourne
1 0 tourne
1 1 passe

Non?

[invite0bbfd30c]

Euh... je ne comprends pas pourquoi tu reviens à des considérations sur la polarisation. A priori il n'est pas question de polarisation ici (sauf éventuellement pour les qubits de contrôle s'ils sont portés par des photons, mais ce n'est même pas nécessaire, et non précisé). Sais-tu précisément à quelle partie du texte se rattache le schéma? Ça pourrait m'aider à comprendre la chose

[invite6c250b59]

A priori il n'est pas question de polarisation ici

Pas pour le "routage", mais pour le contenu de la mémoire c'est bien sur la polarisation que ça joue: The classical database [les d1-d4] could be just a simple sheet of plastic in which a 'zero' transmits light unchanged, and a 'one' shift the polarisation of the incident light by 90°

Sais-tu précisément à quelle partie du texte se rattache le schéma? Ça pourrait m'aider à comprendre la chose

A part la légende c'est le paragraphe p267 commençant par "In order for the oracle to function..." (j'adore ) jusqu'à "...leaving the data register with the desired contents."

[invite6c250b59]

je comprends toujours pas bien en quoi ça fait une mémoire

Bon si en fait. On se retrouve avec un état final dont la polarisation dépend des qubits de contrôle selon la table de vérité

x2 x1 final
0 0 d1
0 1 d2
1 0 d3
1 1 d4

...pour un schème à 2 qubits, et on peut étendre à 3

x3 x2 x1 final
0 0 0 d1
0 0 1 d2
0 1 0 d3
0 1 1 d4
1 0 0 d5
1 0 1 d6
1 1 0 d7
1 1 1 d8

...4, 5 etc avec n qubits de contrôle et 2ⁿ lignes à la table de vérité/bits en mémoire. On a donc bien un schème où une série d'informations classiques a été encodé dans des états quantiques, ce qui était le but de la manoeuvre.

Cela me laisse quand même perplexe. En effet en jouant dans la mémoire classique il semble qu'on puisse construire une fonction arbitraire des états des qubits de contrôle vers l'état final (...ce qui n'est pas une mauvaise définition pour "mémoire"). Or normalement seules les fonctions linéaires sont possibles, et là il semble qu'on puisse faire (par exemple) un ET sans mesure et sans qubit de scratch. Comme si jouer sur deux bases de mesures indépendantes (la position versus la polarisation) permettait de s'affranchir de la sacrosainte condition de réversibilité. Buzzant!

[invite0bbfd30c]

Pas pour le "routage", mais pour le contenu de la mémoire c'est bien sur la polarisation que ça joue

D'accord, je comprends maintenant.

Pour ce dont tu parles ensuite, il ne faut pas oublier que les éléments de mémoire d1...dN n'agissent pas seuls sur la polarisation (comme le feraient de bêtes lames de phase, par exemple). Ils ont besoin d'une étape faisant appel au processeur quantique, qui compare individuellement leur contenu (chaîne de l bits classiques) à la chaîne s. Je ne suis pas sûr que tes tables de vérités correspondent à l'algorithme de recherche décrit dans le texte, mais peut-être as-tu une autre idée...?

[invite6c250b59]

Pour ce dont tu parles ensuite, il ne faut pas oublier que les éléments de mémoire d1...dN n'agissent pas seuls sur la polarisation (comme le feraient de bêtes lames de phase, par exemple). Ils ont besoin d'une étape faisant appel au processeur quantique, qui compare individuellement leur contenu (chaîne de l bits classiques) à la chaîne s.

En fait dans le schéma ce sont bien des bêtes lames à retard de phase. Mais c'est peut-être parce que c'est un simple exemple de comment loader des informations classiques sous forme quantique, ce qui s'insère dans un exercice plus large de réalisation d'un algorithme de recherche. J'ai pas encore tout compris à cet algorithme, mais il ne me semble pas qu'il fasse appel à des dx quantiques. De ce que je comprend il y a comparaison de "l'état final" (appelons le f) avec l'état recherché s, puis selon le résultat de cette comparaison une opération est appliquée aux qbits de contrôle, et encore jusqu'à localiser complètement l'adresse de s en mémoire. Plusieurs choses m'échappent et il faut que j'y travaille encore...

Je ne suis pas sûr que tes tables de vérités correspondent à l'algorithme de recherche décrit dans le texte, mais peut-être as-tu une autre idée...?

Oui c'est une autre idée: le "load" d'une mémoire tel qu'il est décrit peut facilement être considéré comme une façon d'implémenter une fonction arbitraire. A la base j'étais surpris parce que des fonctions non unitaires semblaient possibles, mais en y réfléchissant un peu plus la réversibilité est assurée par les d1-d4 -qu'ils soient classiques ou quantiques. Si c'était des opérateurs quantiques, ce serait eux qui se chargerait d'être des qubits de scratch donc il n'y a pas de problème à ce niveau. Ouf
Je demeure assez séduit par l'idée d'implémenter des fonctions de cette façon, c'est assez élégant je trouve.

[invite0bbfd30c]

En fait dans le schéma ce sont bien des bêtes lames à retard de phase. Mais c'est peut-être parce que c'est un simple exemple de comment loader des informations classiques sous forme quantique, ce qui s'insère dans un exercice plus large de réalisation d'un algorithme de recherche.

Effectivement... c'est quand même un cas très particulier puisque limité à une chaîne s à 1 bit (donc de peu d'intérêt pour un algorithme de recherche, à mon avis). Je ne vois pas comment rester avec de simples lames de phase dès que la base à traiter comprend des chaînes de plus de un bit... Enfin c'est déjà un exemple intéressant.

[invite6c250b59]

comment rester avec de simples lames de phase dès que la base à traiter comprend des chaînes de plus de un bit...

Peut-être comme ça: 1) on répète le schéma 1 pour chaque bits 2) chaque bits à sa série spécifique de lames de phases 3) les qbits de contrôle x1, x2, etc de chaque schéma sont intriqués entre eux.
Qu'est-ce que tu en penses?

[invite0bbfd30c]

Peut-être comme ça: 1) on répète le schéma 1 pour chaque bits 2) chaque bits à sa série spécifique de lames de phases 3) les qbits de contrôle x1, x2, etc de chaque schéma sont intriqués entre eux.
Qu'est-ce que tu en penses?

1) tu veux dire on scinde chaque chaîne (de longueur l) en l bits d11, d12... d1l, mis côte à côte dans la mémoire? Ça, ça ne marche pas.
2) Ça ne marche pas non plus, il faut une combinaison de lames de phases qui, pour plusieurs polarisations d'entrées possibles, les laisse toutes inchangées sauf une. Je ne vois pas d'autre possibilité pour faire ça que le cas à un bit.
3) je ne pense pas que ça élimine le problème. Il faudrait que pour chaque schéma, il y ait un seul élément de mémoire qui ait son unique bit à 1, ou bien à 0 (ce n'est d'ailleurs pas ce qui est représenté sur leur figure, étonnamment), ce qui n'est en général pas le cas.

Je ne vois pas...

[invite6c250b59]

1) tu veux dire on scinde chaque chaîne (de longueur l) en l bits d11, d12... d1l, mis côte à côte dans la mémoire?

Non non c'est pas l'idée. Je serais peut-être plus clair en décomposant la manoeuvre: D'abord 1) on devrait avoir l schémas, 2) chacun avec sa série de lame.

A cette étape on a alors 3 tables de vérités complètement indépendantes. Dans le cas l=n=3 on a alors

x13 x12 x11 f1
0 0 0 d11
0 0 1 d12
0 1 0 d13
0 1 1 d14
1 0 0 d15
1 0 1 d16
1 1 0 d17
1 1 1 d18

x23 x22 x21 f2
0 0 0 d21
0 0 1 d22
0 1 0 d23
0 1 1 d24
1 0 0 d25
1 0 1 d26
1 1 0 d27
1 1 1 d28

x33 x32 x31 f3
0 0 0 d31
0 0 1 d32
0 1 0 d33
0 1 1 d34
1 0 0 d35
1 0 1 d36
1 1 0 d37
1 1 1 d38

Maintenant 3) imaginons que les qbits de contrôle étaient intriqués au départ (x11 avec x21 et x31; x12 avec x22 et x32; x31 avec x32 et x33). Les trois tables fusionnent!

x3 x2 x1 f1 f2 f3
0 0 0 d11 d21 d31
0 0 1 d12 d22 d32
0 1 0 d13 d23 d33
0 1 1 d14 d24 d34
1 0 0 d15 d25 d35
1 0 1 d16 d26 d36
1 1 0 d17 d27 d37
1 1 1 d18 d28 d38

...et on a alors un schéma avec un nombre arbitraire de lignes (2ⁿ avec n=nombre de qubits de contrôle) fonction du nombre de cases mémoire voulue, et un nombre arbitraire (l) de colonnes de "f", fonction du nombre de bits par case mémoire. A priori n=l mais c'est même pas obligatoire àmha.

[invite0bbfd30c]

Je comprends bien, mais ça ne marche pas du tout...

1) si s ne fait qu'un bit, l'algorithme quantique utilisant des lames de phases ne marche que si * un * élément du registre (l'élément à trouver) est différent de tous les autres, identiques entre eux. Au passage, je ne vois pas pourquoi ce n'est pas le cas dans la figure de Nielsen & Chuang.

2) si s fait plusieurs bits, comme dans ton exemple, ça ne marche pas non plus. Il ne faut pas oublier que la condition pour que ça marche est que la fonction d'onde est multipliée par -1 pour un unique élément du registre. Ça marche dans le cas extrêment particulier où on cherche un élément du type 111 parmi des éléments qui valent tous 000 (ou bien 101 parmi 010 etc.), ce qui revient au cas à 1 bit (puisque en faisant la recherche sur le premier bit on trouve l'élément). De plus il faut que s ait un nombre impair de bits, sinon la fonction d'onde est multipliée par 1 aussi pour l'élément recherché.

Bref, ça ne marche pas avec des lames de phase pour des chaînes de plus d'un bit... Qu'en penses-tu?

[invite6c250b59]

Je comprends bien, mais ça ne marche pas du tout...

Oh 'scuse je pensais que ton désaccord était avec la procédure "load", mais visiblement c'est l'algo de recherche qui pose problème. Perso je suis déjà bien content d'avoir compris le load! Concernant l'algo, je t'avouerais que moi aussi la description me semble plus que sibylline.

On a 4 register, le premier étant les qbits de contrôle, le deuxième étant la solution à chercher, le troisième contient le contenu loadé, et le quatrième un qubit superposé qui a l'air comme un cheveu sur la soupe. J'imagine qu'en fait c'est pour dire qu'on explore les qbits de contrôle avec un état superposé. La procédure passe par comparer les registres 2 et 3, qui flip le 4 si c'est la solution et ne fait rien sinon. Mais là je ne suis pas sur s'il y a une mesure à cette étape, ni où, et encore moins comment on enchaine les procédures pour que ça nous donne l'adresse en un nombre d'étape de l'ordre de sqrt(2ⁿ)!

Je suppose qu'en fait on peut se passer du 4 en décrivant le résultat directement sur les qubits de contrôles. Reprenons la table de vérité, avec la solution à chercher en gras

x3 x2 x1 f1 f2 f3
0 0 0 d11 d21 d31
0 0 1 d12 d22 d32
0 1 0 d13 d23 d33
0 1 1 d14 d24 d34
1 0 0 d15 d25 d35
1 0 1 d16 d26 d36
1 1 0 d17 d27 d37
1 1 1 d18 d28 d38

si on suppose qu'une étape de la procédure passe par flipper les qbits de contrôle dans le cas de la solution, et que ça agit en bout de ligne sur les qubits de contrôle, alors une étape peut se décrire comme suit

x3 x2 x1 => x3' x2' x1'
0 0 0 => 0 0 0
0 0 1 => 0 0 1
0 1 0 => 0 1 0
0 1 1 => 0 1 1
1 0 0 => 1 0 0
1 0 1 => 0 1 0
1 1 0 => 1 1 0
1 1 1 => 1 1 1

Maintenant le truc je pense c'est d'utiliser des superpositions: si les qbits de contrôle sont tous superposés on obtient en moyenne 5/8 de "010", si le premier est fixé à 0 on obtient 1/2 de "01" ou "10", s'il est fixé à 1 on obtient 3/4 de "10" et 1/4 de "01". De même en fixant deux qbits on obtient le troisième qbits avec certitude dans 1/4 des cas, et une égalité le reste du temps.

Dans la section résumé page 275 il est parlé d'avoir le résultat "with high probability" ce qui me fait penser que c'est la bonne piste, mais je vois pas comment on ferait pour avoir une solution en environ 3 étapes (sqrt(8)) donc je suis peut-être dans le champ total. Une idée toi?

[invite6c250b59]

Concernant l'algo, je t'avouerais que moi aussi la description me semble plus que sibylline.

Rhaaaa c'est sibyllin car décrit en détail précédemment, voir en particulier box 6.1 p 256 pour exemple à n=2.

x2---H---\ /---H---X-------\_CNOT/--------X---H---
x1---H--- O --H---X---H---/^CNOT\---H---X---H---
so---H---/ \----------------------------------------------

on part de x2=x1=[0> et so=[1>

les premiers H mettent les qbits de contrôle en superposition
x2'=x1'=1/sqrt(2) ( [0> + [1> )

puis il y a appel à l'oracle. On a alors une superposition des 4 "chemins" incluant la solution à chercher en gras

x2' x1' => x2'' x1''
0 0 => 0 0
0 1 => 0 1
1 0 => 0 1
1 1 => 1 1

Autrement dit on passe à
x2''=sqrt(3/4) [0> + sqrt(1/4) [1> et
x1''=sqrt(3/4) [1> + sqrt(1/4) [0>

Après il n'y a qu'à suivre la suite des étapes. J'ai essayé

 Cliquez pour afficher

passe la deuxième série de H
x2'''=sqrt(3/4) 1/sqrt(2) ( [0> + [1> ) + sqrt(1/4) 1/sqrt(2) ( [0> - [1> )
x1'''=sqrt(3/4) 1/sqrt(2) ( [0> - [1> ) + sqrt(1/4) 1/sqrt(2) ( [0> + [1> )

ce qui se récrit
x2'''=sqrt(2/3) [0> + sqrt(1/3) [1>
x1'''=sqrt(2/3) [0> - sqrt(1/3) [1>

passe les X
x2''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1''''=sqrt(2/3) [1> - sqrt(1/3) [0>

passe un H pour x1''''
x2'''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1'''''=sqrt(2/3) 1/sqrt(2) ( [0> - [1> ) - sqrt(1/3) 1/sqrt(2) ( [0> + [1> )

ce qui se réécrit
x2'''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1'''''=sqrt(1/4) [0> - sqrt(3/4) [1>

passe le CNOT entre x2''''' et x1'''''
x2''''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1''''''=sqrt(1/4) sqrt(2/3) [1> - sqrt(3/4) sqrt(1/3) [0>

ce qui se réécrit
x2''''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1''''''=sqrt(2/5) [1> - sqrt(3/5) [0>

passe un H pour x1
x2'''''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1'''''''=sqrt(2/5) 1/sqrt(2) ( [0> - [1> ) - sqrt(3/5) 1/sqrt(2) ( [0> + [1> )

ce qui se réécrit
x2'''''''=sqrt(2/3) [1> + sqrt(1/3) [0>
x1'''''''=-sqrt(1/6) [0> - sqrt(5/6) [1>

arrivent les derniers X
x2'''''''=sqrt(2/3) [0> + sqrt(1/3) [1>
x1'''''''=-sqrt(1/6) [1> - sqrt(5/6) [0>

puis les derniers H
x2'''''''=sqrt(2/3) 1/sqrt(2) ( [0> + [1> ) + sqrt(1/3) 1/sqrt(2) ( [0> - [1> )
x1'''''''=-sqrt(1/6) 1/sqrt(2) ( [0> - [1> ) - sqrt(5/6) 1/sqrt(2) ( [0> + [1> )

ce qui se réécrit
x2'''''''=sqrt(3/4) [0> + sqrt(1/4) [1>
x1'''''''=-sqrt(6/10) [0> - sqrt(4/10) [1>

...mais c'est pas concluant. Probablement des typos, mais aussi conceptuellement il y a un problème avec le qubits so. Je vois pas à quoi il sert, ni comment il est changé par l'oracle -je pense que mon erreur principale est là... j'ai un dead line, je reviendrais un peu plus tard

[invite0bbfd30c]

Perso je suis déjà bien content d'avoir compris le load! Concernant l'algo, je t'avouerais que moi aussi la description me semble plus que sibylline.

En fait je faisais fausse route, je pensais que le schéma combinait le load et le reste de l'agorithme, je ne voyais pas comment ça pouvait marcher sur des bases quelconques. Mais comme tu dis il s'agit bel et bien du load seul, il n'y a donc pas de problème de ce côté là (comme tu dis, on peut mettre plusieurs schémas de ce type en parallèle sans difficulté, il suffit que les qubits de contrôle agissent en parallèle sur chacun des schémas)... pour le reste je n'ai pas encore eu le temps de lire (demain!).

[invite6c250b59]

Deuxième tentative, avec des indices aux X pour éviter les chaînes de '''

on part de x2₁=x1₁=[0> et so=[1>

les premiers H mettent les qbits de contrôle en superposition
x2₂=x1₂=1/sqrt(2) ( [0> + [1> )

puis il y a appel à l'oracle (le load). On a alors une superposition des 4 "chemins" incluant la solution à chercher en gras

x2₂ x1₂ => x2₃ x1₃
0 0 => 0 0
0 1 => 0 1
1 0 => 0 1
1 1 => 1 1

Autrement dit on passe à
x2₃=sqrt(3/4) [0> + sqrt(1/4) [1> et
x1₃=sqrt(3/4) [1> + sqrt(1/4) [0>

Jusque là on a simplement fait un load avec des qbits de contrôle en état superposé. Si on mesurait les qbits de contrôle à cette étape, la bonne adresse (le complément de 01 dans cet exemple) aurait plus de chance de sortir que les autres. Mais c'est moche: il faudrait répéter l'opération plusieurs fois pour avoir une bonne confiance dans l'adresse. Pire, quand on augmente le nombre de qbits pour des exemples plus grand, le nombre de répétition nécessaire augmente très vite. De manière générale, avec une procédure à n qbits de contrôle la bonne valeur sortirait (2^n-1+1)/2ⁿ pour chaque qbits (3/4 pour deux qbits, 5/8 pour trois qbits, 9/16 pour quatre qbits, etc). Le coût en nombre de répétition exploserait donc rapidement.

Je suppose que le truc consiste à transformer la petite information (i.e. la différence de probabilité par rapport au hasard) répartie uniformément sur tous les qbits de contrôle en la concentrant sur un seul qbit de manière à ce qu'elle soit aisément mesurable. On aurait alors une étape à faire pour chaque qbit de contrôle, ce qui correspondrait bien à un algorithme de recherche dont la taille augmenterait comme sqrt(N). Essayons

les qbits de contrôle passent dans une deuxième série de H
x2₄=sqrt(3/4) sqrt(1/2) ( [0> + [1> ) + sqrt(1/4) sqrt(1/2) ( [0> - [1> )
x1₄=sqrt(3/4) sqrt(1/2) ( [0> - [1> ) + sqrt(1/4) sqrt(1/2) ( [0> + [1> )

qui se réécrit
x2₄=sqrt(2/3) [0> + sqrt(1/3) [1>
x1₄=sqrt(2/3) [0> - sqrt(1/3) [1>

passe les X
x2₅=sqrt(2/3) [1> + sqrt(1/3) [0>
x1₅=sqrt(2/3) [1> - sqrt(1/3) [0>

passe un H pour x1₅
x2₆=sqrt(2/3) [1> + sqrt(1/3) [0>
x1₆=sqrt(2/3) sqrt(1/2) ( [0> - [1> ) - sqrt(1/3) sqrt(1/2) ( [0> + [1> )

qui se réécrit
x2₆=sqrt(1/3) [0> + sqrt(2/3) [1>
x1₆=sqrt(1/4) [0> - sqrt(3/4) [1>

passe le CNOT entre x2₆ et x1₆

Changeons l'écriture: on a
sqrt(1/3)*sqrt(1/4) [00>
sqrt(1/3)*-sqrt(3/4) [01>
sqrt(2/3)*sqrt(1/4) [10>
sqrt(2/3)*-sqrt(3/4) [11>

c'est-à-dire
sqrt(1/12) [00>
-sqrt(3/12) [01>
sqrt(2/12) [10>
-sqrt(6/12) [11>

qui se transforme sous l'action du CNOT en
sqrt(1/12) [00>
-sqrt(3/12) [01>
sqrt(2/12) [11>
-sqrt(6/12) [10>

revenons à la première écriture
x2₇= - sqrt(1/12)*sqrt(3/12) [0> - sqrt(2/12)*sqrt(6/12) [1>
x1₇= - sqrt(1/12)*sqrt(6/12) [0> - sqrt(3/12)*sqrt(2/12) [1>

qui se réécrit
x2₇= - sqrt(1/5) [0> - sqrt(4/5) [1>
x1₇= - sqrt(1/2) [0> - sqrt(1/2) [1>

passe un H pour x1
x2₈= - sqrt(1/5) [0> - sqrt(4/5) [1>
x1₈= - sqrt(1/2) sqrt(1/2) ( [0> + [1> ) - sqrt(1/2) sqrt(1/2) ( [0> - [1> )

qui se réécrit
x2₈= - sqrt(1/5) [0> - sqrt(4/5) [1>
x1₈= - 1 * [0> + 0 * [1>

arrivent les derniers X
x2₉= - sqrt(4/5) [0> - sqrt(1/5) [1>
x1₉= 0 * [0> - 1 * [1>

puis les derniers H
x2₁₀= - sqrt(4/5) sqrt(1/2) ( [0> + [1> ) - sqrt(1/5) sqrt(1/2) ( [0> - [1> )
x1₁₀= 0 * sqrt(1/2) ( [0> + [1> ) - 1 * sqrt(1/2) ( [0> - [1> )

qui se réécrit
x2₁₀= - sqrt(5/8) [0> + sqrt(3/8) [1>
x1₁₀= - sqrt(1/2) [0> + sqrt(1/2) [1>

pour rappel après l'oracle on avait

x2₃= sqrt(3/4) [0> + sqrt(1/4) [1> et
x1₃= sqrt(3/4) [1> + sqrt(1/4) [0>

Autrement dit l'information est bien supprimée sur x1, mais elle est diminuée sur x2 au lieu d'augmenter.

Si tu vois où est la boulette...

[invite0bbfd30c]

Si tu vois où est la boulette...

Je n'ai pas refait le calcul. Mais, si j'ai bien compris, il me semble qu'il y a un problème dans ce que tu as écrit : l'action de l'oracle n'est pas de faire un flip sur les bits du registre quand il voit la solution recherchée, mais sur son bit propre, ce qui revient à une multiplication par -1 de la fonction d'onde. Ce n'est pas ce que tu fais ici il me semble...

x2₂ x1₂ => x2₃ x1₃
0 0 => 0 0
0 1 => 0 1
1 0 => 0 1
1 1 => 1 1

[invite6c250b59]

l'action de l'oracle n'est pas de faire un flip sur les bits du registre quand il voit la solution recherchée, mais sur son bit propre, ce qui revient à une multiplication par -1 de la fonction d'onde. Ce n'est pas ce que tu fais ici il me semble...

Par la malpeste!!! Merci beaucoup! Encore une fois, tu mets le doigt en plein sur le bobo.... ça va aller mieux en corrigeant ça

Mes notations précédentes étant pas pratiques, j'ai shifté vers les suivantes, en commençant par écrire chaque porte de contrôle:

O == oracle ou load (0>-0; 1>-1), avec un index pour indiquer quel est la ligne recherchée
H2 == H appliqué aux deux qbits de contrôle (0>0+1; 1>0-1)
H1 == H appliqué au dernier qbit de contrôle
X == X appliqué aux deux qbits de contrôle (0>1; 1>0)

En négligeant la normalisation, les transformations sous forme de table de vérité sont:

_____ O1 _____ O2 ____ O3 ____ O4 ____ CNOT ____X_____H1_______H2
00 __ a > -a +_ a > a -__ a > a -__ a > a -__ a > a __ a > d __a > a+b -__a > a+b+c+d
01 __ b > b -__ b > -b +_ b > b -__ b > b -__ b > b __ b > c __b > a-b +__b > a-b+c-d
10 __ c > c -__ c > c -__ c > -c +_ c > c -__ c > d __ c > b __c > c+d -__c > a+b-c-d
11 __ d > d -__ d > d -__ d > d -__ d > -d +_ d > c __ d > a __d > c-d +__d > a-b-c+d

D'où il devient facile de suivre les étapes du circuit précédent je commence à comprendre l'intérêt de la notation matricielle...

___ debut -- H2 _ O1 __ H2 ___ X ____ H1 _ CNOT _ H1 __ X ____ H2
00 ___ 1 ___ 1 __ -1 _-__ 2 ___ -2 ___ -4 ____ -4 ___ -4 __ -4 ___ -16
01 ___ 0 ___ 1 _-_ 1 ___ -2 ___ -2 ___- 0 ___-_ 0 ___ -4 __ -4 ___-_ 0
10 ___ 0 ___ 1 _-_ 1 ___ -2 ___ -2 ___- 0 ____ -4 ___ -4 __ -4 ___-_ 0
11 ___ 0 ___ 1 _-_ 1 ___ -2 __-_ 2 ___ -4 ___-_ 0 ___ -4 __ -4 ___-_ 0

A partir de là, des considérations sur la symétrie montrent que ça doit marcher peu importe la ligne en mémoire. Mais on peut vérifier

___ debut -- H2 _ O2 __ H2 ___ X ____ H1 _ CNOT _ H1 __ X ____ H2
00 ___ 1 ___ 1 _-_ 1 __-_ 2 __-_ 2 _-__ 0 ___-_ 0 _-__ 4 __ -4 __-__ 0
01 ___ 0 ___ 1 __ -1 _-__ 2 ___ -2 ___- 4 ___-_ 4 ___ -4 _-_ 4 ___ -16
10 ___ 0 ___ 1 _-_ 1 ___ -2 _-__ 2 ___- 4 ___-_ 0 ___- 4 __ -4 ___-_ 0
11 ___ 0 ___ 1 _-_ 1 ___- 2 __-_ 2 __-_ 0 ___-_ 4 ___ -4 _-_ 4 ___-_ 0

___ debut -- H2 _ O3 __ H2 ___ X ____ H1 _ CNOT _ H1 __ X ____ H2
00 ___ 1 ___ 1 _-_ 1 __-_ 2 __-_ 2 _-__ 4 __-__ 4 __-_ 4 __ -4 _-___ 0
01 ___ 0 ___ 1 _-_ 1 ___ -2 __-_ 2 ___- 0 ___-_ 0 __-_ 4 __ -4 ___-_ 0
10 ___ 0 ___ 1 __ -1 _-__ 2 ___ -2 ___- 0 ____ -4 ___ -4 _-_ 4 ___ -16
11 ___ 0 ___ 1 _-_ 1 __-_ 2 __-_ 2 ___ -4 ___-_ 0 ___ -4 _-_ 4 ___-_ 0

___ debut -- H2 _ O4 __ H2 ___ X ____ H1 _ CNOT _ H1 __ X ____ H2
00 ___ 1 ___ 1 -__ 1 __-_ 2 ___ -2 __-_ 0 ___-_ 0 ___ -4 __ -4 _-___ 0
01 ___ 0 ___ 1 _-_ 1 _-__ 2 __-_ 2 ___ -4 ____ -4 __-_ 4 _-_ 4 ___-_ 0
10 ___ 0 ___ 1 _-_ 1 _-__ 2 _-__ 2 ___- 4 ___-_ 0 ___- 4 _-_ 4 ___-_ 0
11 ___ 0 ___ 1 __ -1 ___ -2 __-_ 2 _-__ 0 ___-_ 4 ___ -4 __ -4 ___ -16

Et voilà! Il me reste à voir dans le cas général avec n>2 mais avec les corrections que tu as amenés ça devrait être du gateau.

Encore merci!