Ordinateur quantique en vue

[trebor]

Bonjour à tous, j'ai lu, je ne sais plus ou, que si l'ordinateur quantique devait exister un jour, qu'il n'y aurait plus de sécurité pour les cartes bancaires et autres ?
-----

[pm42]

Bonjour à tous, j'ai lu, je ne sais plus ou, que si l'ordinateur quantique devait exister un jour, qu'il n'y aurait plus de sécurité pour les cartes bancaires et autres ?

C'est une version simpliste. Certains algorithme cryptographiques actuels ne seront plus sur si on dispose d'ordinateurs quantiques en effet.
C'est pour cela qu'on développe des versions dites "post-quantiques".

Et le sujet ne concerne pas que les cartes à puce mais aussi la signature de documents, la sécurité sur Internet... C'est pour cela qu'il y a beaucoup de recherche sur le sujet actuellement.

https://fr.wikipedia.org/wiki/Crypto...post-quantique

[MissJenny]

Est-ce qu'on ne peut pas dire que si une machine, quelle qu'elle soit, a besoin d'un temps non nul pour effectuer un calcul, alors on peut l'occuper pendant le temps qu'on veut, simplement en lui proposant une suite de calculs à faire dont chacun dépend du résultat du calcul précédent ? auquel cas il y aura toujours des problèmes qu'aucun ordinateur ne pourra résoudre dans un temps donné.

[Deedee81]

Salut,

Est-ce qu'on ne peut pas dire que si une machine, quelle qu'elle soit, a besoin d'un temps non nul pour effectuer un calcul, alors on peut l'occuper pendant le temps qu'on veut, simplement en lui proposant une suite de calculs à faire dont chacun dépend du résultat du calcul précédent ? auquel cas il y aura toujours des problèmes qu'aucun ordinateur ne pourra résoudre dans un temps donné.

Ca dépend du problème, l'analyse de l'algorithme peut très bien être adapté pour obtenir les résultats que tu cites dans devoir faire les étapes intermédiaires. Un exemple, considère l'étape "prendre le résultat précédent et faire +1", que tu fais N fois. Tu changes en une seule étape "faire +N" et hop c'est plus rapide.

Mais il y aura toujours des problèmes trop complexes pour des ordinateurs, quels qu'ils soient. Quel que soit le problème à résoudre on peut trouver pire C'est juste que les problèmes en question ne sont pas piqués des vers.
(et il y a aussi les fonctions non calculables mais ça c'est un autre problème)

Un petit classement :
https://fr.wikipedia.org/wiki/Classe_de_complexit%C3%A9

[xxxxxxxx]

Sa position qui consiste à dire que puisse qu'il ne connait rien à la quantique et qu'il croit qu'elle peut être déterministe, il faut aller dans une direction considérée comme sans grand intérêt par toute la recherche mondiale ? Du haut de sa compétence qui se résume à comme il le dit lui même "lire le français" ?

salut pm42

juste deux ou trois questions:

- y a t'il besoin d'être calé en théorie quantique pour comprendre cet article futura qui traite de mécanique quantique ? savoir lire le français ne suffit t'il pas pour comprendre ?

- que tu trouves tu à redire à cette affirmation :

... tu serais étonné de voir comment on peut se passer de toute la complexité de la QFT pour calculer la densité d'énergie du vide alors qu'on l'a très simplement dans un cadre déterministe avec les unités de Planck. Une simple égalité aux dimensions suffit.

... pas besoin d'avoir étudié en profondeur toute la complexité des théories pour avoir le même résultat. c'est peut être rageant mais c'est comme ça

???

[Deedee81]

- y a t'il besoin d'être calé en théorie quantique pour comprendre cet article futura qui traite de mécanique quantique ? savoir lire le français ne suffit t'il pas pour comprendre ?

C'est le drame avec la mécanique quantique. Quand on ne la connait pas..... on croit comprendre. Et l'affirmation en question est du DK tout craché (*). Je ne te le reproche pas, faut juste que tu en prennes conscience.

(*) c'est d'ailleurs faux, L'analyse avec Planck ne suffit pas. Regarde la force de Casimir. Elle est simple (dans sa formulation finale). Essaie un peu de retrouver le coefficient et le signe avec l'analyse dimensionnelle (dans le livre de Itzykson et Zuber ils disent même que la valeur du signe est tout fait non intuitive) (en fait si on utilise des plateaux "non infinis", ce qui est quand même plus réaliste, c'est pire encore : impossible de trouver la formule par analyse dimensionnelle : il y a trop de grandeurs avec la même dimension). Ou l'effet Lamb ou la force de van der Waals (dû là aussi au vide quantique, et dans la force vdW l'exposant diffère même selon qu'on est en relativité ou pas, l'analyse dimensionnelle ne peut rien y faire)

[invite7a0a8d2e]

Question subsidiaire.
A-t-on pu démontrer à l'aide d'un seul exemple, qu'un "calcul quantique" avait été réalisé plus rapidement qu'un "calcul classique" ?
Traduit en terme scientifique : Le temps de préparation des n qbit avant calcul (qui pour ma part doit être considéré comme faisant partie du calcul) est-il exponentiel ou linéaire en fonction du nombre n de qbit ?

[Deedee81]

A-t-on pu démontrer à l'aide d'un seul exemple, qu'un "calcul quantique" avait été réalisé plus rapidement qu'un "calcul classique" ?

Je l'avais dit plus haut. Oui mais avec un exemple "très artificiel". Je ne me souviens plus de quoi malheureusement (c'était dans PLS sur la polémique de la suprématie quantique) mais c'était un exemple vraiment conçu "exprès pour ça", et en pratiquement totalement inutile. EDIT et j'ai pas mes revues sous la main, je ne suis pas chez moi.

[xxxxxxxx]

Et l'affirmation en question est du DK tout craché (*). Je ne te le reproche pas, faut juste que tu en prennes conscience.

(*) c'est d'ailleurs faux, L'analyse avec Planck ne suffit pas. Regarde la force de Casimir. Elle est simple (dans sa formulation finale). Essaie un peu de retrouver le coefficient et le signe avec l'analyse dimensionnelle (dans le livre de Itzykson et Zuber ils disent même que la valeur du signe est tout fait non intuitive) (en fait si on utilise des plateaux "non infinis", ce qui est quand même plus réaliste, c'est pire encore : impossible de trouver la formule par analyse dimensionnelle : il y a trop de grandeurs avec la même dimension). Ou l'effet Lamb ou la force de van der Waals (dû là aussi au vide quantique, et dans la force vdW l'exposant diffère même selon qu'on est en relativité ou pas, l'analyse dimensionnelle ne peut rien y faire)

tu réponds à coté je crois: je parle de la densité d'énergie du vide et toi de la force Casimir

dans mon cas on passe par tout le bazar de la fonction d'onde de la MQ dans la QFT on renormailise et tout le tintouin pour aboutir à la même chose qu'une égalité aux dimensions

[Merlin95]

Tant qu'on ne sait pas faire une multiplication je vois mal comment faire des outils utiles au public après ce n'est pas forcément un argument que l'on dépense bcp d'argent j'ai l'impression que l'emballement, la "folie" touche aujourd'hui tous les milieux même dit plus ou moins scientifique.

[Deedee81]

tu réponds à coté je crois: je parle de la densité d'énergie du vide et toi de la force Casimir

La force de Casimir est un effet de la densité d'énergie du vide (à une dérivée près, la formule c'est l'énergie du vide).

Dis moi, tu le fais exprès, hein ?
Enfin, bon, au moins tu as dis "je crois"

[xxxxxxxx]

edit : croisement, pas le temps de rectifier, j'y reviens plus tard au besoin

par contre sur ce point tu as raison : a priori il n'y a pas de formulation de la force Casimir en unité de Planck

Mais pour la densité d'énergie du vide de la QFT (3.83 10⁶⁹ m^-2) c'est tout simplement l_p^-2 .....edit, je crois que tu fais erreur sur ce point

[Deedee81]

Tant qu'on ne sait pas faire une multiplication je vois mal comment faire des outils utiles au public après ce n'est pas forcément un argument que l'on dépense bcp d'argent j'ai l'impression que l'emballement, la "folie" touche aujourd'hui tous les milieux même dit plus ou moins scientifique.

Là c'est pas exclut. Faut le dire, la science fonctionne parfois par effet de mode. Mais c'est plus une question socio-économique que sientifique.

[Deedee81]

par contre sur ce point tu as raison : a priori il 'y a pas de formulation de la force Casimir en unité de Planck

Mais pour la densité d'énergie du vide de la QFT (3.83 10⁶⁹ m^-2) c'est tout simplement l_p^-2

Au fait, c'est spéculatif. En QFT la densité d'énergie du vide c'est zéro.
https://fr.wikipedia.org/wiki/Ordre_normal

DK, fois mille milliard, qui dit mieux. YOUPIIIIIII
Va y xxxxxxxxx continue à nous amuser

EDIT je quitte la discussion, tout ce qui devait être dit a été dit. Enfin, pour quelques années au moins
EDIT : et évidemment dans l'effet de Casimir, pour le vide quantique, il y a un abus de langage puisque 0... ne varie pas !!!! (le français étant très pauvre, je veux dire les langues humaines, pas que le français). Mais xxxxxxx le grand expert vous expliquera bien ça, il vous expliquera la différence entre vide quantique état de base, vide quantique en cosmologie et vide quantique de Casimir et tant que vous y être demandez lui la différence entre le vide quantique adiabatique, celui de Hartle-Hawking et celui de Bouilland
A+

[Merlin95]

Là c'est pas exclut. Faut le dire, la science fonctionne parfois par effet de mode. Mais c'est plus une question socio-économique que sientifique.

Étant donné tous les scientifiques qui travaillent dessus, perso aussi simple j'y crois plus. C'est même devenu politico-socio-economie scientifique avec la dernière décision de Macron si j'ai bien compris.

[xxxxxxxx]

Fais toi plaisir car en fait pour que ça ait la dimension d'une densité d'énergie il faut des J/m^3 et là c'est du 10¹¹³ J/m^3.

Bon j'arrête car ça pollue le file

[Merlin95]

Une révolution et des applications majeures
L’informatique quantique permet de résoudre des calculs complexes en quelques minutes là où le plus puissant calculateur d’aujourd’hui mettrait des centaines d’années. L’ordinateur quantique n’aura pas d’usage pour le citoyen lambda mais permettra aux chercheurs de calculer à grande échelle l’infiniment petit et l’infiniment grand avec infiniment de précision. Une révolution.

Quand je dis que la multiplication n'estmême pas disponible, je veux dire que la tendance même des spécialistes semblent dire que l'informatique quantique n'est pas pour les problèmes courants. Deedee tu as des infos scientifiques qui sous entendraient le contraire ?

[Deedee81]

Quand je dis que la multiplication n'estmême pas disponible, je veux dire que la tendance même des spécialistes semblent dire que l'informatique quantique n'est pas pour les problèmes courants. Deedee tu as des infos scientifiques qui sous entendraient le contraire ?

Je repasse pour répondre à ça. Non, c'est tout à fait juste. Les puces quantiques ce ne sera vraiment pas pour ce genre d'usage ou le classique faire ça super bien (ceci dit pour les multiplications de grand nombre même en classique on fait une transformée de Fourier). Il sera virtuellement impossible (ou idiot) d'avoir un calculateur généraliste purement quantique. La puce quantique (ou carte) idéale devra être totalement programmable mais ce sera pour des usages spécifiques, comme je le disais plus haut : comme un coprocesseur spécialisé. D'ailleurs il suffit de voir les portes logiques quantiques, c'est pas vraiment les ET/OU/NOR/NAND de notre jeunesse (enfin, la mienne en tout cas).

EDIT et écrire un programme pour calculateur quantique est un vrai cauchemar. Mais il y a des progrès, voir le lien que j'avais donné (j'ai plus suivi les actus hardware que software d'ailleurs, mais je m'y intéresserai peut-être un de ces quatre)

[Merlin95]

Ha non le classique ne sait pas résoudre les problèmes NP-complets de manière toujours "exploitable" Deedee (qu'est-ce que tu dis là ?)

[pm42]

Ha non le classique ne sait pas résoudre les problèmes NP-complets de manière toujours "exploitable"

Les ordinateurs quantiques non plus : https://fr.wikipedia.org/wiki/Problè...ique_quantique

[Deedee81]

Ha non le classique ne sait pas résoudre les problèmes NP-complets de manière toujours "exploitable" Deedee (qu'est-ce que tu dis là ?)

Je n'ai pas parlé des problèmes NP-Complet (enfin, si, un tout petit peu avec le voyageur de commerce, mais je parlais de l'avenir). Pourquoi dis-tu ça ?????

[Deedee81]

Je n'ai pas parlé des problèmes NP-Complet (enfin, si, un tout petit peu avec le voyageur de commerce, mais je parlais de l'avenir). Pourquoi dis-tu ça ?????

ROOOOOHH je viens de comprendre l'erreur : Merlin95 : la multiplication et les TF ce n'est pas du tout NP-Complet.
Et déjà dans ma jeunesse on utilisait des puces de TFT (transformée de Fourier rapide) (en laboratoire d'analyse des signaux, pendant mes études d'ingénieur). Et les histoires de calculs quantiques étaient encore dans les limbes (c'était il y a 35 ans)

EDIT la complexité d'une multiplication c'est n² (pas exp n !!!!) et avec une TFT : n*log n, ce qui est assez remarquable (et rapide).
EDIT bis : https://www.larecherche.fr/informati...multiplication

[Merlin95]

Les ordinateurs quantiques non plus : https://fr.wikipedia.org/wiki/Problè...ique_quantique

oui justement c'est bien ce que je veux exprimer. On en sait trop rien. Du lien que tu m'as donné :

Mais comme il n'est pas démontré que BQP est disjoint de NP-complet, on ne peut non plus formellement écarter l'hypothèse que les problèmes NP-complets puissent être en théorie calculable par un ordinateur quantique en temps polynomial.

@Deedee tu n'as pas parlé des problèmes NP-complet mais moi j'en ai parlé indirectement car ça fait partie des problèmes courants. Et tu as dit que l'informatique classique

fait ça super bien

ROOOOOHH je viens de comprendre l'erreur

Pas sûr.

[Deedee81]

@Deedee tu n'as pas parlé des problèmes NP-complet mais moi j'en ai parlé indirectement car ça fait partie des problèmes courants. Et tu as dit que l'informatique classique

Pas du tout. Il n'y avait rien d'indirect. Tu parlais de la multiplication. Et celle-ci n'est pas NP-Complet et est super facile avec l'informatique classique.
Les problèmes courants sont presque toujours plus faciles que les NP-Complet, heureusement d'ailleurs.
Et les NP-Complets sont abordés de manière approchée (recuit stimulé par exemple) et là aussi l'informatique classique fait ça super bien.

Si tu voulais parler des rares problèmes courants NP-Complet avec solution exacte (là c'est l'horreur), tu aurais dû le préciser. Je ne suis pas madame Irma.

[Merlin95]

Dans un forum scientifique, il me semble inutile de préciser que résoudre un problème NP-complet, signifie donner une solution exacte.
Le voyageur de commerce est un problème NO-coomplet, il y en a d'autres voir plein, ça me semble être un problème assez central. La factorisation des nombres premiers est peut-être ainsi un problème NP-Complet.

[Deedee81]

Salut,

Dans un forum scientifique, il me semble inutile de préciser que résoudre un problème NP-complet, signifie donner une solution exacte.

C'est normal qu'il ne faut pas préciser ça puisque c'est faux. Un problème NP-Complet (comme tout problème d'ailleurs) admet des solutions approchées. C'est même l'usage le plus fréquent. Tu sais la science c'est avant tout être clair et précis. Et pire que ça, tu ne parlais même pas de problème NP-Complet du tout, tu parlais de multiplication. Si la clarté de ton propos n'est pas toujours là (moi non plus d'ailleurs, ça m'arrive d'être brouillon ), je constate que la bonne foi ne risque pas non plus de t'étouffer (tu vivras peut-être plus longtemps ).

Le voyageur de commerce est un problème NO-coomplet, il y en a d'autres voir plein, ça me semble être un problème assez central. La factorisation des nombres premiers est peut-être ainsi un problème NP-Complet.

Important, pas central. J'ai été amené à écrire des centaines et des centaines d'algorithmes en 35 ans. Gestion comptable, gestion de stock, gestion de production en usine, gestion de planning, outils de bas niveaux pour la communication ou la gestion client/serveur... etc.... Certains de ces algorithmes n'étaient pas piqués des vers (gestion de production avec répartition de matière premières et commandes, liens triparties intérêts - postes comptables - lignes de dette, déclaration tva luxembourgeoise... sont cinglés eux avec cette déclaration , systèmes multitâches avec gestion de conflit, etc... ah oui et les amortissements, ouf aussi ça, et bien sûr tout ce qui tourne autour de la compilation)

Sais-tu combien de fois j'ai rencontré des problèmes NP-Complets (ou pire) ? UNE fois, dans une gestion de planning (j'ai râlé en voyant ça, j'ai modifié un peu les objectifs avec accord du patron pour rendre l'algo polynomial). Témoignage n'est pas raison, mais ça illustre bien la situation ici.

Les problèmes NP-Complets sont importants et ont des usages qu'on rencontre régulièrement, surtout dans certains domaines (exemple en conception de circuits intégrés pour le calcul des "lignes de connexion"). Mais dans tout ce qui est utilisé, rencontré,.... en informatique, ce n'est vraiment qu'une minuscule pointe de l'iceberg. Donc, il faut toujours préciser de quoi on parle.... si on veut être comprit (et ça n'a d'ailleurs rien à avoir avec le fait d'être sur un forum scientifique, ça ce n'est qu'une excuse à la c...)

[MissJenny]

j'ajouterais que ça n'est pas parce qu'un problème est NP-complet qu'on ne peut pas trouver des solutions exactes. C'est juste que quand la taille du problème augmente on n'y arrive plus, mais "à distance finie" c'est possible.

[Deedee81]

j'ajouterais que ça n'est pas parce qu'un problème est NP-complet qu'on ne peut pas trouver des solutions exactes. C'est juste que quand la taille du problème augmente on n'y arrive plus, mais "à distance finie" c'est possible.

Ah oui, c'est vrai, j'oubliais ça. Et d'ailleurs même avec une taille élevée on peut parfois..... avoir de la chance J'avais lu ça dans un article sur l'informatique et la logique du premier ordre (c'est pas récent, j'avais lu ça il y a une quinzaine d'années). Il y avait une jolie stat sur les proportions de solutions rapides même avec N élevés (stat tenant compte de la situation pratique qui était là assez favorable). Enfin, bon, on ne compte pas trop là-dessus d'habitude.

A l'inverse, pas fréquent mais à savoir, si on a un algo en n^7 par exemple (de mémoire le test "exact" de primalité général, si je ne me trompe pas), il n'est pas NP-complet et est même non exponentiel. Mais devient vite inutilisable. Bon, les pires que j'ai rencontré (hors le cas que j'ai cité) étaient en n^3. Mais même là ça peut devenir lourd.

[Deedee81]

On a ça aussi avec le voyageur de commerce. Dans certaines situations les solutions exacte même avec N élevées sont rapides. Malheureusement, il y a des situations où ce n'est pas le cas. Et même dans des applications avec cas favorables cela peut parfois arriver.... et c'est là que ça fait ch... Je me rappelle avoir lu ça dans les algorithmes de détection d'erreur dans la compilation. Personne n'a envie d'avoir un compilateur rapide mais qui de temps en temps met des heures

[invite7a0a8d2e]

Un jeu NP-Difficile : Donkey Kong !

Sinon, juste une remarque concernant les calculs quantiques.
Si le calcul est effectué trop longtemps, "l'ordinateur cesse d'être cohérent" (j'aime bien cette formule ), donc on peut considérer que le calcul est arrêté...
Donc faire des calculs de manière classique reste pour le moment (et pour toujours peut-être...) la méthode la plus efficace, même pour un problème NP.