Répondre à la discussion
Affichage des résultats 1 à 15 sur 15

Complexité de l'algorithme de Shor



  1. #1
    Argyre

    Complexité de l'algorithme de Shor

    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

    -----


  2. Publicité
  3. #2
    Argyre

    Re : Complexité de l'algorithme de Shor

    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

  4. #3
    JPL

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par Argyre Voir le message
    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 !
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  5. #4
    shahinshah

    Re : Complexité de l'algorithme de Shor

    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.

  6. #5
    Argyre

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par JPL Voir le message
    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

  7. A voir en vidéo sur Futura
  8. #6
    Argyre

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par shahinshah Voir le message
    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

  9. Publicité
  10. #7
    GillesH38a

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par Argyre Voir le message
    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 AN, 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.

  11. #8
    Argyre

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par gillesh38 Voir le message
    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 AN, 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 AN fonctions d'onde, alors que, précisément, une seule formule comportant n variables suffit à modéliser l'état du système ?

    Cordialement,
    Argyre

  12. #9
    GillesH38a

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par Argyre Voir le message
    Hum ....
    La phrase en gras mérite d'être développée. Pourquoi voudrais-tu avoir AN 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 AN fonctions d'onde, tu as une fonction d'onde dépendant de AN 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 2N 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 2N états



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


    Cette fonction d'onde spécifie la probabilité de chacun des 2N 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 2N 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.

  13. #10
    Argyre

    Re : Complexité de l'algorithme de Shor

    Bonjour,
    Citation Envoyé par gillesh38 Voir le message
    tu n'as pas AN fonctions d'onde, tu as une fonction d'onde dépendant de AN 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) à 2n 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 2n paramètres à gérer et donc 2n é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 2n 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 2n. 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

  14. #11
    spi100

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par Argyre Voir le message
    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.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  15. #12
    GillesH38a

    Re : Complexité de l'algorithme de Shor

    Citation Envoyé par Argyre Voir le message
    Néanmoins, de manière fondamentale, je pense qu'on peut contre-argumenter sur le fait que la complexité en 2n 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 2n. 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.

  16. Publicité
  17. #13
    Stibium

    Re : Complexité de l'algorithme de Shor

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

  18. #14
    Nephret

    Re : Complexité de l'algorithme de Shor

    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 ?

  19. #15
    arthur369

    Re : Complexité de l'algorithme de Shor

    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

Sur le même thème :

Discussions similaires

  1. Les Algorithmes de Shor et de Grover
    Par Sleep7 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 23/02/2007, 16h52
  2. svp un liens pour apprendre l'algorithme
    Par The Rings dans le forum Internet - Réseau - Sécurité générale
    Réponses: 2
    Dernier message: 26/10/2006, 16h14
  3. Démonstration de l'algorithme d'Euclide.
    Par EaGle58 dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 02/07/2006, 19h53
  4. TPE sur l'algorithme de CORDIC
    Par laetibox dans le forum TPE / TIPE et autres travaux
    Réponses: 1
    Dernier message: 02/02/2006, 09h24
  5. L'algorithme ultime
    Par boardingman dans le forum Discussions scientifiques
    Réponses: 52
    Dernier message: 30/08/2004, 09h07