Complexité de l'algorithme de Shor

[invite06fcc10b]

Bonjour,

L'algorithme de Shor est un algorithme quantique utilisé pour la factorisation.
(voir wikipédia par exemple : http://fr.wikipedia.org/wiki/Algorithme_de_Shor)
Cet algorithme est annoncé comme pouvant réduire la complexité algorithmique de façon importante, typiquement en temps polynomial, ce qui ne serait pas le cas avec un algorithme classique.
Pourtant, d'après ce que j'en ai compris, il me semble qu'on peut remplacer chaque particule initiale par un ordinateur et effectuer les mêmes calculs en parallèle, ce qui fait qu'en terme de complexité, on aboutit également à une complexité polynomiale.
La question est donc :
Est-ce que j'ai mal compris, ou est-ce que l'algorithme de Shor ne révolutionne rien du tout ? Bien sûr, le fait de passer à l'échelle atomique permet sans doute un gain en temps de calcul, mais ce que je remets en cause, c'est le fait qu'il y ait un gain en "complexité" algorithmique. On ne peut pas comparer 2 approches en autorisant le parallélisme massif d'un côté et en l'interdisant de l'autre, non ?

Cordialement,
Argyre
-----

[invite06fcc10b]

Personne ne répond ?
Dois-je en conclure que personne n'a compris le concept d'ordinateur quantique ?
Si très peu de gens comprennent, on peut se poser la question de la pertinence des résultats de ce domaine. Est-ce que dans 10 ans, plus personne ne parlera d'ordinateur quantique ? Y a t-il comme moi des sceptiques ?

Cordialement,
Argyre

[JPL]

Personne ne répond ?
Dois-je en conclure que personne n'a compris le concept d'ordinateur quantique ?

Il me semble que tu extrapoles indûment à partir du simple fait que personne depuis hier ne s'est jugé assez compétent pour répondre à ta question !

[invitec00162a9]

Bonjour,

de ce que j'ai compris des algo quantiques à partir de mes bouquins d'informatique quantique, c'est qu'ils sont essentiellement des variantes de l'algorithme de Grover qui effectue une recherche en O(N^0.5) au lieu de O(N) avec un ordinateur quantique. C'est un gain qui n'est pas négligeable, sans être faramineux.
Maintenant, pour en revenir au sujet de l'algorithme de Shor, il est évident qu'en parallélisant le calcul de factorisation, on arrive à obtenir "facilement" les facteurs : c'est ainsi qu'on casse les clés du RSA en distribuant le calcul à travers le réseau Internet.
David Deutsch en tire même un argument pour sa thèse multimonde dans son livre "L'étoffe de la réalité" : si l'algorithme de Shor "marche", c'est que le calcul est en fait distribué dans le multivers.

My 2 cents.

[A voir en vidéo sur Futura]

[invite06fcc10b]

Il me semble que tu extrapoles indûment à partir du simple fait que personne depuis hier ne s'est jugé assez compétent pour répondre à ta question !

Quand on provoque un peu, on a toujours un peu plus de réponses ...
Cordialement,
Argyre

[invite06fcc10b]

Maintenant, pour en revenir au sujet de l'algorithme de Shor, il est évident qu'en parallélisant le calcul de factorisation, on arrive à obtenir "facilement" les facteurs : c'est ainsi qu'on casse les clés du RSA en distribuant le calcul à travers le réseau Internet.
David Deutsch en tire même un argument pour sa thèse multimonde dans son livre "L'étoffe de la réalité" : si l'algorithme de Shor "marche", c'est que le calcul est en fait distribué dans le multivers.

My 2 cents.

Ok, merci. Mais donc, comme je l'ai indiqué, il n'est pas très fair play de comparer un algo parallèle à un algo séquentiel, sans faire référence aux algorithmes parallèles concurrents. En réalité, je n'ai pas lu l'article de référence de Shor, mais seulement le résumé dans Wikipédia. Et c'est donc au moins ce résumé qui ne me parait pas scientifiquement "honnête".

Cordialement,
Argyre

[GillesH38a]

Personne ne répond ?
Dois-je en conclure que personne n'a compris le concept d'ordinateur quantique ?
Si très peu de gens comprennent, on peut se poser la question de la pertinence des résultats de ce domaine. Est-ce que dans 10 ans, plus personne ne parlera d'ordinateur quantique ? Y a t-il comme moi des sceptiques ?

Cordialement,
Argyre

Je ne suis pas sûr d'avoir bien compris le concept d'ordinateur quantique, mais il me semble que le gain en complexité vient du fait que si tu veux représenter une fonction d'onde quantique à N particules correlées , tu dois te placer dans un espace à 3N dimensions : le nombre de calculs à faire si tu remplaces tes N particules par le calcul de leur fonction d'onde croit donc comme A^N, alors que l'ordinateur quantique lui ne croît que lineairement avec N. Ce qui revient au même de dire que l'ordinateur quantique ne croit que logarithmiquement avec le nombre d'opérations classiques à faire, et donc polyniomalement là ou un ordinateur classique croit exponentiellement.

[invite06fcc10b]

Je ne suis pas sûr d'avoir bien compris le concept d'ordinateur quantique, mais il me semble que le gain en complexité vient du fait que si tu veux représenter une fonction d'onde quantique à N particules correlées , tu dois te placer dans un espace à 3N dimensions : le nombre de calculs à faire si tu remplaces tes N particules par le calcul de leur fonction d'onde croit donc comme A^N, alors que l'ordinateur quantique lui ne croît que lineairement avec N. Ce qui revient au même de dire que l'ordinateur quantique ne croit que logarithmiquement avec le nombre d'opérations classiques à faire, et donc polyniomalement là ou un ordinateur classique croit exponentiellement.

Hum ....
La phrase en gras mérite d'être développée. Pourquoi voudrais-tu avoir A^N fonctions d'onde, alors que, précisément, une seule formule comportant n variables suffit à modéliser l'état du système ?

Cordialement,
Argyre

[GillesH38a]

Hum ....
La phrase en gras mérite d'être développée. Pourquoi voudrais-tu avoir A^N fonctions d'onde, alors que, précisément, une seule formule comportant n variables suffit à modéliser l'état du système ?

Cordialement,
Argyre

tu n'as pas A^N fonctions d'onde, tu as une fonction d'onde dépendant de A^N paramètres.

Un système 1 à 2 états aura une fonction d'onde se développant sur ces deux états, donc dépendant de deux coefficients complexes. (en fait il y a une condition de normalisation et une invariance de phase globale qui ne laisse que deux paramètres réels libres mais laissons les détails techniques)


Maintenant si tu as N systèmes corrélés, tu n'as pas 2N paramètres mais 2^N paramètres, parce que justement l'état global ne peut PAS etre ecrit comme la factorisation d'un état 1 x un état 2 x un état 3 (ce qui serait le cas d'un état classique). La fonction d'onde se développe sur les 2^N états



où chaque i1, i2... iN vaut 1 ou 2, ce qui fait bien 2^N coefficients a.


Cette fonction d'onde spécifie la probabilité de chacun des 2^N résultats de mesure possible (trouver 1 dans l'état i1 ET 2 dans l'état i2 ET ... N dans l'état iN). L'évolution de cet état par un hamiltonien revient bien à faire simulatément le calcul de 2^N quantités avec N particules.

Toute l'étrangeté de la Meca Q est que tu ne peux pas calculer les probabilités ci dessus en spécifiant juste la probabilité d'avoir 1 dans l'état i1, 2 dans l'état i2 etc.. (chaque probabilité etant indépendante des autres états ). Ca correspondrait à un état factorisé du premier type mais ce serait justement un état sans corrélation. C'est ce qui rend l'interprétation en variables cachées tellement compliquée, et en pratique impossible.

[invite06fcc10b]

Bonjour,

tu n'as pas A^N fonctions d'onde, tu as une fonction d'onde dépendant de A^N paramètres.
...

Ok, j'ai pigé.
Donc pour en revenir à l'algorithme de Shor, il y a effectivement n étapes expérimentales conduisant (dans le cas où il y a 2 états par système) à 2ⁿ paramètres de corrélation dans la fonction d'onde.
Si on tente une simulation de cet algorithme sur un ordinateur classique, on a obligatoirement 2ⁿ paramètres à gérer et donc 2ⁿ étapes de calcul ne serait-ce que pour accéder à la valeur de ces paramètres.
Vu comme ça, il y a donc effectivement un gain notable en complexité algorithmique.
Néanmoins, de manière fondamentale, je pense qu'on peut contre-argumenter sur le fait que la complexité en 2ⁿ existe belle et bien dans l'ordinateur quantique, sauf qu'elle est implicite et que c'est dame nature qui se débrouille pour gérer le problème. Donc, quelque part, le procédé est ingénieux pour gagner du temps, mais d'un point de vue théorique, la complexité algorithmique reste en 2ⁿ. Rappelons qu'en algorithmique, la complexité est indépendante du support matériel. Si quelqu'un trouve un support matériel qui réalise une partie du traitement de façon naturelle grâce aux lois de la physique, tant mieux, mais cela ne remet pas en cause la complexité de l'algorithme.
D'ailleurs, on doit pouvoir trouver des astuces du même style pour d'autres systèmes physiques, sans avoir recours à la fonction d'onde. Par exemple, dans un système à n corps avec pour unique attracteur la force gravitationnelle, si on cherche à connaître la position de chaque corps à chaque instant, nul besoin de procéder à un calcul de complexité exponentielle, il suffit d'avoir les n corps en question et de mesurer leur position, ce qui requiert n étapes à chaque instant ...

D'accord ?

Cordialement,
Argyre

[spi100]

D'ailleurs, on doit pouvoir trouver des astuces du même style pour d'autres systèmes physiques, sans avoir recours à la fonction d'onde. Par exemple, dans un système à n corps avec pour unique attracteur la force gravitationnelle, si on cherche à connaître la position de chaque corps à chaque instant, nul besoin de procéder à un calcul de complexité exponentielle, il suffit d'avoir les n corps en question et de mesurer leur position, ce qui requiert n étapes à chaque instant ...

D'accord ?

Cordialement,
Argyre

Peut être, pour répondre partiellement à ta question, les bases du calcul réversible : porte de Toffoli, Frendkin and Co, ont été posées bien avant que l'on parle de calcul quantique (dans le milieu des années 80). L'idée est que si l'on veut exploiter les systèmes microscopiques pour faire du calcul, les lois microscopiques étant réversibles, il faut alors imaginer des composants logiques réversibles. Les composants classiques n'ont effectivement pas cette propriété, par exemple une porte AND prend deux entrées pour une sortie: si tu ne connais que la sortie tu ne peux pas connaitre les deux entrées.

A partir de ces portes (donc Toffoli and Co), des systèmes de calcul basés sur des systèmes physiques classiques ont été imaginés. Le plus connu est le BBM (Billard Ball Model), tu peux jeter un oeil à cette thèse http://people.csail.mit.edu/nhm/thesis.pdf où il est entre autre expliqué comment fabriquer un système de calcul universel avec un billard.

[GillesH38a]

Néanmoins, de manière fondamentale, je pense qu'on peut contre-argumenter sur le fait que la complexité en 2ⁿ existe belle et bien dans l'ordinateur quantique, sauf qu'elle est implicite et que c'est dame nature qui se débrouille pour gérer le problème. Donc, quelque part, le procédé est ingénieux pour gagner du temps, mais d'un point de vue théorique, la complexité algorithmique reste en 2ⁿ. Rappelons qu'en algorithmique, la complexité est indépendante du support matériel. Si quelqu'un trouve un support matériel qui réalise une partie du traitement de façon naturelle grâce aux lois de la physique, tant mieux, mais cela ne remet pas en cause la complexité de l'algorithme.
D'ailleurs, on doit pouvoir trouver des astuces du même style pour d'autres systèmes physiques, sans avoir recours à la fonction d'onde.

Bien sur je pense que tu as raison, ce n'est pas la complexité algorithmique qui change : c'est juste que la réalisation matérielle avec une fonction d'onde donne des capacités de calcul qui croissent exponentiellement avec le nombre de particules, et donc permet de contourner la limitation pratique des algorithmes croissant exponentiellement, puisque ca redevient polynomial en terme d'exigences de taille et de temps de calcul. C'est impossible a faire autrement qu'en Meca Q, puisque justement un système classique de N particules EST séparable en N états d'une particule, et donc ne peut pas stocker une information plus que lineairement en N.

[Stibium]

"en algorithmique, la complexité est indépendante du support matériel", si ce n'est que la démonstration mathématique qui prouve cela repose sur des hypotheses que ne vérifient pas les ordinateurs quantiques!

Pour en revenir à la question, l'algorithme de Shor a donc bien une complexité polynomiale (il faut un nombre polynomial de portes quantiques pour factoriser un nombre).

Cela dit, on n'a toujours pas prouvé qu'il n'existait pas d'algorithme classique permettant de factoriser polynomialement les nombres...

[invitebfcc4f61]

Bien que ma question ne soit pas exactement la complexité de l'algorithme de Shor, elle s'y rattache fortement ! La page de wikipédia propose un algorithme classique de factorisation de la clé du code RSA. Est-ce que quelqu'un pourrait m'aider à en calculer la complexité. Je sais que je dois obtenir une complexité exponentielle, mais il n'y a pas moyen, je n'arrive pas à aboutir à ce résultat...
une bonne âme ?

[inviteb8e1e20a]

bonjour je vien dans ce topic pour dire que si quelqun arivarait a resoudre la complexiter de l'algorithme en question cela rendrai les ordinateur cree a parire de cette algoritme 4x plus rapide et donc d'eviter a des gens de faire comme lui LOL
donc voila je voulai juste vous donner mon avis byebye a tous