Ordinateur quantique en vue

[Deedee81]

SAlut,

Un jeu NP-Difficile : Donkey Kong !

Sans rire, avec le jeu démineur il existe bien un problème NP (article de Delahaye dans logique et calcul) A partir d'une configuration donnée ("partiellement jouée"), vérifier que celle-ci correspond bien une solution possible (pour une configuration arbitraire ce n'est pas nécessairement le cas, c'est facile d'en inventer qui ne peuvent pas correspondre à des jeux réels).

Analogue (la raison est plus évidente) : prouver qu'une configuration au échec correspond bien à un jeu possible. Question qu'on rencontre souvent quand on invente des rétro-problèmes (on l'appelle alors "partie justificative"). J'en ai créé quelques uns à une époque (et j'avais même écrit en C# un programme d'analyse rétrograde).

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.

Attention car justement avec un ordinateur quantique.... c'est rapide.

Pour la décohérence on en a déjà parlé. C'est un des enjeux :
- avec les q-bits photoniques il n'y a pas ou quasiment pas de décohérence. Mais ce type de q-bits est difficile à manipuler.
- avec d'autres dispositifs il existe maintenant des méthodes de restauration de la cohérence, en amplitude ou en phase. Grosso modo : on démultiplie le q-bits (pour en utiliser un seul) et on utilise ces q-bits pour restaurer la cohérence. C'est un peu amusant car ça me fait penser à un système classique déjà existant : les mémoires dynamiques (enfin, sur le principe de refresh du moins, car la méthode elle reste assez différence). J'avais lu ça dans PLS et je n'arrive pas à trouver de référence sur la méthode.... si quelqu'un a ça c'est le bienvenu. La principale difficulté est de restaurer en amplitude et en phase, car pour avoir un seul q-bit utile il en faudrait des milliers qui ne servent qu'à ça. C'est à la fois trop couteux et trop complexe.

Donc on peut dire que si (certains) calculs NP exacts restent plus faciles en classique qu'en quantique ce n'est pas à cause de la décohérence mais juste à cause des technologies qui doivent encore mûrir (il y a dix ans, oui, la décohérence semblait impossible à contourner, mais on fait des progrès )
-----

[invite7a0a8d2e]

Sans rire, avec le jeu démineur il existe bien un problème NP (article de Delahaye dans logique et calcul) A partir d'une configuration donnée ("partiellement jouée"), vérifier que celle-ci correspond bien une solution possible (pour une configuration arbitraire ce n'est pas nécessairement le cas, c'est facile d'en inventer qui ne peuvent pas correspondre à des jeux réels).

Oui, mais attention, c'est un sujet sérieux (Donkey Kong ) :

Classic Nintendo Games are (Computationally) Hard
Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta
February 10, 2015

Abstract
We prove NP-hardness results for ve of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versions of Super Mario Bros. 1{3, The Lost Levels, and Super Mario World; Donkey Kong Country 1{3;all Legend of Zelda games; all Metroid games; and all Pokemon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games

https://arxiv.org/pdf/1203.1895.pdf

Sinon, un article intéressant (très complet, ça s'invente pas ) sur la complexité :
https://www.oezratty.net/wordpress/2...ue-complexite/

Attention car justement avec un ordinateur quantique.... c'est rapide.

Oui, mais bon, moi j'attends de voir.
Je ne crois que ce que je vois.

[Deedee81]

Oui, mais attention, c'est un sujet sérieux (Donkey Kong ) :

Ah ben ça

Merci de la ref.

https://arxiv.org/pdf/1203.1895.pdf

Sinon, un article intéressant (très complet, ça s'invente pas ) sur la complexité :
https://www.oezratty.net/wordpress/2...ue-complexite/

Oui, mais bon, moi j'attends de voir.
Je ne crois que ce que je vois.

Facile : "voit" ceci :
https://en.wikipedia.org/wiki/Shor%27s_algorithm

(pour ce qui est de "c'est plus rapide", évidemment : "sera" plus rapide avec un appareil réel, au futur, sinon plus personne ne contesterait la suprématie quantique )

[MissJenny]

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.

n^3 n'est pas exceptionnel, si? le produit de 2 matrices nxn est en n^3.

je suis frappé par la relative célérité des petits GPS de nos bagnoles, quand ils calculent l'itinéraire le plus court, dans un graphe qui doit avoir des dizaines de milliers de sommets (souvent la cartographie de toute l'Union Européenne). Je me demande quel est l'algorithme utilisé, et s'il trouve la solution exacte ou une solution approchée.

[pm42]

n^3 n'est pas exceptionnel, si? le produit de 2 matrices nxn est en n^3.

En fait, c'est en n^2.3728596 : https://en.wikipedia.org/wiki/Matrix...tion_algorithm
Dans les cas réels, il arrive fréquemment que les grosses matrices soient creuses ce qui permet de diminuer la complexité sans recourir à des algos lourds et pas forcément pratiques.

je suis frappé par la relative célérité des petits GPS de nos bagnoles, quand ils calculent l'itinéraire le plus court, dans un graphe qui doit avoir des dizaines de milliers de sommets (souvent la cartographie de toute l'Union Européenne). Je me demande quel est l'algorithme utilisé, et s'il trouve la solution exacte ou une solution approchée.

On utilise des algos bien pensés avec des heuristiques qui font baisser la complexité : https://en.wikipedia.org/wiki/A*_sea...thm#Complexity

Pour plus d'infos : https://www.researchgate.net/figure/...fig2_266673685

[Deedee81]

EDIT arg, grillé par pm42. Et j'étais pas loin : du n²

n^3 n'est pas exceptionnel, si? le produit de 2 matrices nxn est en n^3.

Je ne suis pas sûr pour le produit matriciel, mais bon, j'ai rarement dû multiplier des grosses matrices (je suppose que dans des applications scientifiques ça doit être plus fréquent).

je suis frappé par la relative célérité des petits GPS de nos bagnoles, quand ils calculent l'itinéraire le plus court, dans un graphe qui doit avoir des dizaines de milliers de sommets (souvent la cartographie de toute l'Union Européenne). Je me demande quel est l'algorithme utilisé, et s'il trouve la solution exacte ou une solution approchée.

Ah, ça, j'ai eut l'occasion de creuser. Là c'était un collègue qui travaillait là-dessus. J'avais lu sa thèse. Son problème était l'optimisation d'un bras robotique avec un grand nombre de degrés de liberté dans un tore de tokamak. Le problème étant la recherche d'un chemin dans un espace de configuration avec contraintes. Il avait illustré ça avec la recherche du chemin le plus court dans un labyrinthe et c'est analogue à la cartographie ou ce que fait le GPS.

L'astuce consiste à faire une recherche arborescente en prolongeant d'abord le noeud minimisant a*r1+b*r2 r1 distance déjà parcourue r2 distance à vol d'oiseau à l'arrivée. On peut démontrer que c'est optimal tant en résultat qu'en temps d'exécution pour a=b=1 (me souviens plus de la démonstration, elle était dans sa thèse). Et la vitesse est en effet très étonnante. C'est trèèèèèès loin du NP complet. Je ne connais pas la complexité exacte mais pour avoir expérimenté l'algorithme (et avoir vu les essais du collègue) ça doit être du n*log n ou du style. Et ça marche même avec des pondérations (par exemple des routes plus ou moins rapides, limitation de vitesse, avec travaux, avec bouchons). Extraordinaire.

David C, je ne sais pas si tu viens sur Futura, mais si oui et que tu te reconnais, tu as mon bonjour

[xxxxxxxx]

...
Attention car justement avec un ordinateur quantique.... c'est rapide.

Pour la décohérence on en a déjà parlé. C'est un des enjeux :
- avec les q-bits photoniques il n'y a pas ou quasiment pas de décohérence. Mais ce type de q-bits est difficile à manipuler.
...

bonjour

puisque qu'avec les q-bits photoniques il n'y a pas ou quasiment pas de décohérence, serait il possible de faire des ordi quantiques juste pour résoudre un problème à un vitesse phénoménale au lieu de chercher à un faire un ordi complexe programmable ?

est ce faisable ?

merci

[Merlin95]

Salut,



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



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

Aucune mauvaise foi je ne vois même pas comment résoudre un problème np-complet peut-être compris par donner une approximation. Pour moi cela relève même d'une carence dans le langage scientifique de la personne. Mais j'ai tord car je suis souvent trop scrupuleux sur les termes (c'est un défaut : forme de perfectionnisme exagéré "involontairement"). Si nous avons du mal a nous comprendre inutile d'être agressif non plus. Pareil je parlais de la multiplication mais sincèrement je n'y refaisais plus référence mais voulais parler des problèmes classiques. N'y vois pas de la mauvaise foi c'est offensant, je n'ai juste pas été précis comme tu l'as dit. Quand à ma remarque "qu'est ce que tu racontes" c'était juste pour te faire comprendre une forme de stupéfaction personnelle (déplacée peut-être), pas de mauvaise intention ou arrière-pensées de ma part.

[Deedee81]

est ce faisable ?

C'est une très bonne question..... mais je n'en sais fichtre rien (même si je suppose que ce n'est pas si simple sinon ils l'auraient déjà fait).

Aucune mauvaise foi je ne vois même pas comment résoudre un problème np-complet [blabla bla bla]

Ton message ne parlait pas de np-complet. Relis-toi.

[xxxxxxxx]

Merci Deedee

[pm42]

je ne vois même pas comment résoudre un problème np-complet peut-être compris par donner une approximation.

Tous les jours, on utilise des algos pour faire les trajets des livreurs : c'est le problème du voyageur de commerce.
Et ça marche très bien justement parce qu'on se contente d'une solution approchée justement.

[Deedee81]

J'avais pas vu cette partie de la remarque.

Il faut noter qu'on utilise souvent des approximations, c'est même le plus courant, et pas seulement pour le NP. L'exemple bateau étant les calculs aérodynamique (résolution des équations aux dérivées partielles).
Un mathématicien parlera plus volontiers de solutions exacte, mais un ingénieur, un physicien, un spécialiste du calcul numérique (qui est le sujet) parle de solutions aussi bien exactes que approchées.

J'ai travaillé (mais à la fac cette fois, pas en milieu professionnel) sur des algorithmes d'équations linéaires.... et même dans ce cas on utilise des solutions approchées (enfin, pour des cas volumineux, pas pour de petits ou la méthode du pivot est excellente). C'est encore plus vrai en optimisation.

EDIT anecdote, en écrivant un algo de résolution exact d'équation aux dérivées partielles (en automatique) j'ai eut une mauvaise surprise. Il y a une autre source d'approximation : l'arrondi numérique. Et mon algorithme divergeait à cause de ça (j'ai résolu en augmentant la précision numérique). C'est une simple anecdote, évidemment, l'approximation numérique n'a rien à voir avec le fait de choisir classique versus quantique.

Et ça marche très bien justement parce qu'on se contente d'une solution approchée justement.

Une des méthodes les plus fréquentes : https://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
Du moins quand on a besoin d'une très bonne approximation (et une approximation sûre, évitant les "minimums locaux"). Si on veut du simple et pouvant donner un minima local, la simple itération marche bien, est assez précise (hors le local) et très rapide. Sinon on change le problème (mais là on triche )

[pm42]

Une des méthodes les plus fréquentes : https://fr.wikipedia.org/wiki/Recuit_simul%C3%A9

Oui, chouette méthode. On l'utilise aussi pour faire de l'allocation de registres du processeur dans les compilateurs.

[Deedee81]

On l'utilise aussi pour faire de l'allocation de registres du processeur dans les compilateurs.

Ah tiens, ça j'ignorais (faut dire que j'ai potassé ce sujet.... avant l'invention de cette méthode). Merci,

[Merlin95]

Ton message ne parlait pas de np-complet. Relis-toi.

Pas besoin de me relire, je le sais bien, c'est pourquoi j'ai dit que je me suis mal exprimé.

[Merlin95]

Tous les jours, on utilise des algos pour faire les trajets des livreurs : c'est le problème du voyageur de commerce.
Et ça marche très bien justement parce qu'on se contente d'une solution approchée justement.

Oui je connais il existe des méthodes qu'on appelle heuristiques qui donne de bonnes solutions c'est à dire qui ont de bonnes chances d'être à cité de la solution exacte mais dont on ne peut jamais être sûr que c'est une solution optimale. J'ai étudié cela donc je vois bien de quoi il s'agit mais moi personnellement je n'appellerai pas ça résoudre un problème NP-complet. D'autres apparemment le font sans broncher ca amène à de gros malentendus mais inutile d'en venir à donner des ordres par exemple à son interlocuteur (ne pas oublier que "relis toi" reste un impératif).

[invite7a0a8d2e]

Une des méthodes les plus fréquentes : https://fr.wikipedia.org/wiki/Recuit_simul%C3%A9
Du moins quand on a besoin d'une très bonne approximation (et une approximation sûre, évitant les "minimums locaux"). Si on veut du simple et pouvant donner un minima local, la simple itération marche bien, est assez précise (hors le local) et très rapide. Sinon on change le problème (mais là on triche )

J'aime bien cette méthode, je l'avait inventée sur mon Amstrad à l'époque.

[Deedee81]

Salut,

je me suis mal exprimé.

Alors ne m'en veut pas d'avoir mal réagit Voilà, on s'est réconcilié

ca amène à de gros malentendus

L'inverse est vrai aussi . Se focaliser uniquement sur les solutions exactes (ce qui est rare en science, sauf en math, et en particulier en informatique, sujet du fil) amène aussi à des malentendus. Mais bon, ça va, maintenant on s'est compris (enfin j'espère ).

mais inutile d'en venir à donner des ordres par exemple à son interlocuteur (ne pas oublier que "relis toi" reste un impératif).

Oulàlà, chatouilleux, susceptible et énervé Un pt'tit prozac ?
C'était plus une invitation à vérifier qu'un ordre.

J'aime bien cette méthode, je l'avait inventée sur mon Amstrad à l'époque.

On a tous commencé ainsi Moi c'était TRS80 et une méthode d'analyse de systèmes d'équations (j'avais rien inventé) et une méthode d'analyse de jeux (là j'avais inventé, mais quand j'ai découvert les méthodes minimax et alpha bêta, j'ai laissé tombé ma méthode qui était franchement utiliser un camion toupie pour préparer une portion de pâte à tarte ) Chose amusante le mini max est un outil de la théorie des jeux (avec un théorème de von Neuman si ma mémoire est bonne) et moi je l'ai appris par des articles de programmation des jeux, chacun ses sources (mais bon je devais avoir 15/16 ans lors de ces lectures, faut pas me jeter la pierre hein, la théorème en question je devais avoir une bonne vingtaine d'année lorsque je l'ai lu dans une encyclopédie de mathématiques)
EDIT vérifié, c'est bien von Neumann

[Merlin95]

Non pas énervé ok on s'est compris no souci

[Merlin95]

L'inverse est vrai aussi . Se focaliser uniquement sur les solutions exactes (ce qui est rare en science, sauf en math, et en particulier en informatique, sujet du fil) amène aussi à des malentendus. Mais bon, ça va, maintenant on s'est compris (enfin j'espère

J'espère pas , d'autant plus que je vous propose une autre explication qui est que quelque chose me dérangeait c'est que bon nombre de mathématiciens qui essaient de démontrer que P=NP est juste, doivent en fait passer leur temps à essayait jusqu'à aujourd'hui de trouver une heuristique optimale, non ?

[xxxxxxxx]

bonjour

puisque qu'avec les q-bits photoniques il n'y a pas ou quasiment pas de décohérence, serait il possible de faire des ordi quantiques juste pour résoudre un problème à un vitesse phénoménale au lieu de chercher à un faire un ordi complexe programmable ?

est ce faisable ?

merci

La photo de cet article me laisse penser que les chinois y sont arrivés. Mais je n'en suis pas sûr du tout

[Deedee81]

Salut,

La photo de cet article me laisse penser que les chinois y sont arrivés. Mais je n'en suis pas sûr du tout

T'arrive à déduire ça d'une photo toi ? Mazète, c'est encore plus fort qu'avec une vidéo youtube
(regarde ici : https://www.1jour1actu.com/wp-conten...-demasque.jpeg Tu dois sûrement en déduire que le yéti existe )

Sans rire :
- La suprématie quantique a déjà été atteinte une dizaine de fois.... et contestée une dizaine de fois. Faut rester prudent. Les chercheurs ont tendance à être trop enthousiastes
- Il n'est pas exclut qu'ils y soient arrivés, les chinois investissant énormément dans ce domaine
- les chinois adorent la propagande (comme les autres pays , mais c'est plus difficile à vérifier)

Bref .... on ne peut rien conclure (c'est pas des actus qu'il faut mais des articles validés en comité de lecture voire un truc commercial testé par d'autres).
(d'autant que j'ai lu du bien sur TrustMyScience mais aussi du mal, un coup d'oeil général que je viens de faire me montre surtout un site d'actu visant le tape à l'oeil spectaculaire..... comme tous les sites d'actus).
Les actus sont intéressantes pour avoir une idée des news en général mais mon opinion est que les actus sans liens vers une source scientifique sont à la science ce que le papier cul est à la papeterie.
(edit sans vouloir être désobligeant pour les actus, la douceur de mon gluteus maximus en témoigne , faut de tout pour faire un monde mais il faut aussi aller "plus loin" que cette vue superficielle)

[Deedee81]

Soyons plus précis :

La factorisation des grands nombres est un problème difficile. La sécurité cryptographique est d'ailleurs souvent basée là dessus.
Il existe des challenges : https://fr.wikipedia.org/wiki/Comp%C...torisation_RSA
basés sur les limites de ce qu'on arrive à faire avec le calcul classique.

Or c'est un des trucs où le quantique peut faire mieux (c'est même un des plus anciens algo quantique : l'algorithme de Shor : https://fr.wikipedia.org/wiki/Algorithme_de_Shor)

Le jour où des concepteurs de calcul quantique en profiteront pour rafler le prix d'un tel challenge, ce sera non seulement vérifiable et concret mais un véritable dépassement du calcul classique : alors là oui j'accepterai de dire "la suprématie quantique est atteinte". Pas avant.

En attendant ce n'est que du vent et des affirmations gratuites et/ou trop optimistes.

[xxxxxxxx]

Salut,



T'arrive à déduire ça d'une photo toi ? Mazète, c'est encore plus fort qu'avec une vidéo youtube
(regarde ici : https://www.1jour1actu.com/wp-conten...-demasque.jpeg Tu dois sûrement en déduire que le yéti existe )

Sans rire :
- La suprématie quantique a déjà été atteinte une dizaine de fois.... et contestée une dizaine de fois. Faut rester prudent. Les chercheurs ont tendance à être trop enthousiastes
- Il n'est pas exclut qu'ils y soient arrivés, les chinois investissant énormément dans ce domaine
- les chinois adorent la propagande (comme les autres pays , mais c'est plus difficile à vérifier)

le schéma avec les saphirs sera sans doute plus parlant pour toi

il y a un article arxiv que je n'ai pas consulté

[Deedee81]

On s'est croisé.

le schéma avec les saphirs sera sans doute plus parlant pour toi

Un dessin c'est pas mieux qu'une photo

il y a un article arxiv que je n'ai pas consulté

Je ne l'avais pas vu. Merci,

Il est clairement sérieux mais apparemment pas publié (dans une revue, n'oublions pas que ArXiv est une simple archive ouverte). Si ce qu'ils disent est vrai ils atteignent de sacrées performances (j'ai regardé en diagonal, surtout la fin). Article à décortiquer. Et affaire à suivre donc.

[xxxxxxxx]

Un dessin c'est pas mieux qu'une photo

remplacer le silicium par des saphirs est un changement notable en terme de vecteur d'information utilisé : photons à la place d'électrons non ?

[Deedee81]

remplacer le silicium par des saphirs est un changement notable en terme de vecteur d'information utilisé : photons à la place d'électrons non ?

Il y a déjà plusieurs autres techniques avec photons (et d'autres avec ions, etc...). Ca ne change rien au niveau vitesse. Les difficultés techniques ne sont pas là. Un bon dossier à lire (et pas vieux) : https://www.pourlascience.fr/sd/info...n018-18881.php

Ils décrivent les techniques et les difficultés. Très bon dossier.

Par exemple plusieurs visent les techniques à semi-conducteurs (là c'est l'électron) avec puits quantiques car :
- il existe des outils performant de miniaturisation
- cela s'intègre avec l'électronique existante
Mais rien ne dit évidemment que les percées viendront de là

[xxxxxxxx]

Il y a déjà plusieurs autres techniques avec photons (et d'autres avec ions, etc...). Ca ne change rien au niveau vitesse.

et au niveau du "bruit", quel est le moyen le plus stable ?

[Deedee81]

et au niveau du "bruit", quel est le moyen le plus stable ?

Je crois que les photons sont les meilleurs. Les ions les pires.
Il y a aussi les outils de contrôle de q-bits. Là les photons sont les pires. Les ions les meilleurs.
Les électrons à mi-chemin.

C'est donc énervant (en fait plus un système est insensible aux perturbations plus il est difficile à contrôler.... pour les mêmes raisons). Mais les choses évoluent si vite qu'il faut se documenter.

[xxxxxxxx]

Ok merci.

Je surveille les avancées. On verra la suite (de cette solution mais aussi des progrès des autres)

Bonne journée