Discussion :

[MClerc]

Comme tout ce qui est quantique c'est très contre-intuitif, mais ne concerne (pour l'instant) qu'un problème précis ad hoc.

Néanmoins, si cette preuve peut être étendue à d'autres problèmes, par exemple la décomposition d'un entier en facteurs premiers (dont on sait déjà que la complexité est polynomiale sur une machine quantique (mais pour l'instant néanmoins croissante avec la taille du nombre), alors il y a vraiment du souci à se faire pour la cryptographie : pour tous les algos type RSA il sera (relativement) facile de craquer un code en un temps raisonnable, quelle que soit sa taille.

Au passage cela rend un peu ringard le problème P=NP (ou non). Sauf qu'il y a toujours un million de dollars à la clé

[foetus]

vu que les ordinateurs quantique ne savent pas tous faire. ils sont très bon pour certain type de taches mais pas pour d'autres. mème s'il sont époustouflants dans les taches qu'ils gèrent pourquoi parler de suprématie quantique.
(comme un gars autiste aspeger comparé a un gars normal avec une intelligence toute relative )
suprématie voudrai dire que les pc classiques sont obsolètes... ce n'est pas le cas

C'est un thème récurrent de la S.F. et notamment chez Philip K. Dick : Les êtres/ humains qui ont des "pouvoirs" (lire les pensées, comprendre le monde différemment, ...) utilisent leur pouvoir pour dominer/ diriger/ asservir les humains normaux.

Ou alors comme dans report minoritaire, on renforce leurs pouvoirs quitte à ce qu'ils deviennent de gros légumes et ensuite on les met dans une pièce adaptée pour qui travaillent

[lsbkf]

Faux, il est mathématiquement prouvé qu'un mec bourré a 100% de chance de retrouver son chez soi ...à la seule condition qu'il dispose d'un temps infini, ce pourcentage se réduit à mesure que l'on "retranche" à l'infini.
Un autre exemple moins trollesque, mais tout aussi vrai : le calcul de pi, étant un nombre irrationnel, son écriture n'est ni fractionnaire (avec des chiffres), ni finie (avec des chiffres).
Pi est calculable, on en connait un bon milliard de décimales, mais étant constitué d'une infinité de décimales, il faut au calcul une infinité de temps de calcul.
De plus, en mathémathique, il y a des concepts, des idées, mais certaines attendes toujours leurs mises en équation /formule. C'est ce que j'entendais par "qui soient à la fois formulable en langage mathématique concret".

Quand je parle de choses impossibles à calculer, je parle par exemple d'avoir une fonction A qui prend une autre fonction B en entrée et renvoie true si B se termine. Il est prouvé qu'une telle fonction n'existe pas (ça consiste à créer une fonction C : "tant que A(C) == true, boucle", et on a un paradoxe sur les bras), en tout cas si A et B sont exprimés sur le même modèle calculatoire. Il existe des tas d'autres problèmes qu'on peut exprimer mais qu'aucun algorithme ne peut résoudre avec une certaine précision de calcul.

À ma connaissance, rien n'est dit sur l'existence ou non d'un programme quantique capable de résoudre un problème incalculable avec un programme classique (dans l'exemple du dessus, B tournerait sur une machine de Turing, A sur un nouveau modèle révolutionnaire, et on peut pas écrire C vu que les modèles collent pas, donc il faut une autre démonstration). Peut-être que ça reste impossible, peut-être qu'il y a une classe de problèmes bien définis où ça l'est. Personne n'a trouvé une solution satisfaisante, ou alors c'est très bien caché dans la masse de pseudo-vulgarisation des ordinateurs quantiques, ou alors la réponse est triviale.
Bref, voilà où je veux en venir sur les raisons qui m'ont fait cliquer sur cette news et les déceptions qui s'ensuivent.

[jean12]

Personnellement j'y trouve beaucoup d'avantages en plus de la possibilité de plus puissants algorithmes pour l'intelligence artificielle par exemple, on peut citer en plus la rapidité d'exécution de nos futures applications, la superposition rendra possible de stocker des quantité inimaginables de données sur juste un petit support (nouvelles génération de clés USB), etc.

[denis18]

Le plus étonnant c'est que l'on a aucun moyen de savoir vraiment ce qu'ils font pour le démontrer.
On veut bien les croire mais tout ceci nous semble abstrait, si ce n'est que de reproduire les mêmes
exemples selon lesquelles un qubits peut avoir toutes les valeurs a la fois, ce n'est pas parce que l'on
ne les comprend pas qu'ils sont intelligents comme dans les livres des dames savantes de molière. denis.

[Steinvikel]

Quand je parle de choses impossibles à calculer, je parle par exemple d'avoir une fonction A qui prend une autre fonction B en entrée et renvoie true si B se termine. Il est prouvé qu'une telle fonction n'existe pas (ça consiste à créer une fonction C : "tant que A(C) == true, boucle", et on a un paradoxe sur les bras), en tout cas si A et B sont exprimés sur le même modèle calculatoire. Il existe des tas d'autres problèmes qu'on peut exprimer mais qu'aucun algorithme ne peut résoudre avec une certaine précision de calcul.

J'entends ta réponse, mais je diverge sur la définition de "calculable" qui est différente de la mienne dans tes propos.
Ce que je tente d'exprimer par calculable --> "formulable en langage mathématique concret", c'est de pouvoir remplacer l'intégralité de la formulation par une forme purement numérique ...l'un des rares critères pour être "calculé" au sens commun, et non factorisé, canonisé, réduit, simplifié, etc.
Mais si je m'appuie sur le sens que tu lui donnes, alors je te rejoins.

Beaucoup de lignes de codes présentes des mises en oeuvres insolubles (résultat non pertinent). Certaines sont liés à la version du langage, d'autres au langage lui même, d'autres au format des données, d'autres à l'architecture de la machine... mais comme en mathématique, pour résoudre un problème complexe (au sens commun), il faut choisir son contexte de raisonnement (le système d'axiomes), les outils adaptés, etc.

Certaines théories ne sont pas calculables (autrement plus concret que démontrable) car il est démontré qu'il n'est pas possible d'aboutir (insoluble)... mais raisoné dans un autre référenciel (système d'axiomes ex: Euclide, ZFC), cette même théorie devient calculable.
Certains problèmes sont insolubles (ni démontrable, ni réfutable), puis viens l'arrivée de nouveaux outils, et certaines de ces théories insolubles deviennent soudains résolu (ex: l'espace de Laplace qui permet de se soustraire de la composante temporelle).

Je reste convaincu, dans cette vision de la mathématique, que si il est possible de coucher sous forme purement numérique une formulation mathématique, alors elle est "calculable", et ce, sans tenir compte du temps nécessaire à sa résolution.