Un ordinateur gravito-quantique est-il possible ?

[exciton]

Bonjour,

Je me suis beaucoup intéressé à l'informatique quantique pour l'étonnante puissance de calcul qu'il apporte. Certains chercheurs suspectent que BQP, la classe des calculs quantiques "faciles", contiendrait des problèmes inaccessibles à un ordinateur classique. Par exemple, trouver une combinaison secrète dans un espace plus grand que le nombre d'atome que l'univers. Ce serait la porte ouverte vers une intelligence calculatoire à la Deep Blue.

Alors je me demande si la relativité générale apporterait encore plus de puissance. Connaissez-vous des travaux sur l'ordinateur relativiste, ou mieux gravito-quantique ?
-----

[Deedee81]

Salut,

Alors je me demande si la relativité générale apporterait encore plus de puissance. Connaissez-vous des travaux sur l'ordinateur relativiste, ou mieux gravito-quantique ?

Pas à ma connaissance.

La relativité générale ne devrait rien apporter de plus car ce qui permet l'augmentation de la puissance des ordinateurs quantiques est le principe de superposition quantique. Alors que la relativité générale reste une théorie totalement classique.

Si on parle de la gravitation quantique, je ne sais pas. C'est possible qu'on puisse imaginer des trucs. Je ne vais pas m'avancer. Mais d'une part nous n'avons pas encore de théorie validée (il y a plusieurs théories candidates, peut-être toutes fausses), d'autre part ce domaine est loin, très loin, très très loin de toute possibilité expérimentale.

[WizardOfLinn]

Il me semble qu'il y a quelques spéculations sur l'exploitation de boucles temporelles pour la résolution de problèmes NP-complets.
L'ordinateur prend le temps qu'il faut pour résoudre son problème et renvoie la solution dans le passé.
Ne sait-on pas "créer" des boucles temporelles en RG ? (en théorie, hein)

[invite231234]

Salut !

L'ordinateur quantique est une bête bizarre ... il faut des algos spéciaux et on ne peut actuellement dire qu'il n'est pas en mesure de détrôner l'informatique classique !

Maintenant pour le gravito, je ne vois pas comment faire mais je sais que Jiav s'y connait mieux que moi dans tous ce qui calculs très très puissants !

[A voir en vidéo sur Futura]

[Deedee81]

Ne sait-on pas "créer" des boucles temporelles en RG ? (en théorie, hein)

Il peut théoriquement en exister mais ces solutions sont normalement considérées comme non physiques. Et même si on les considères comme physique je ne crois pas qu'il existe un processus physique qui pourrait mener à ça (à vérifier mais je m'étais même déjà poser la question de manière plus générale sans pouvoir y répondre).

Je ne connaissais pas ces spéculations. Mais c'est vrai que si l'on disposait de boucles temporelles, woaw, on pourrait faire des calculs phénoménaux en une fraction de seconde

[invite231234]

Je viens de me souvenir ... suis-je bête ?

Ce que Jiav m'avais instruit : hypercalcul

Qu'en pensez-vous par rapport aux possibilités offertes par l'ordinateur quantique ?

[Deedee81]

Salut,

Qu'en pensez-vous par rapport aux possibilités offertes par l'ordinateur quantique ?

Que ça va bien au-delà. Toute fonction calculable par un ordinateur quantique l'est aussi par un ordinateur classique. L'ordinateur quantique offre seulement une possibilité d'exécuter beaucoup plus rapidement ces calculs, notamment ceux dit NP-Complet.

Ici, l'hypercalcul permettrait de calculer des fonctions non calculables au sens de Turing et donc non calculables sur un ordi classique ou quantique.

Par exemple, la fonction http://fr.wikipedia.org/wiki/Castor_affair%C3%A9

Soit un ordinateur disposant d'une mémoire de taille M. Quelle est la plus grande longueur de 1 que l'ordinateur peut sortir avant de s'arrêter (c'est important, sinon la réponse est "l'infini") et sans interagir avec l'extérieur évidemment. Disons L cette longueur. La fonction L(M) est non calculable.

Plus exactement, tu pourrais écrire un algorithme capable de calculer cette fonction pour un certain nombre de valeurs. Algo(L(1) .... L(10)) par exemple. Mais tu ne peux pas trouver un algorithme général qui calculerait L(M) pour une valeur quelconque de M.

C'est démontré.

L'hypercalcul le permettrait.

Je suis d'accord avec Church et Turing : je pense que ce n'est pas réalisable. Il faudrait disposer, par exemple, d'un Oracle. Les boucles temporelles permettraient de réaliser ça. Mais je n'y crois pas vraiment (un tel Oracle peut conduire très facilement à des contradictions, un aspect exploré dans le film Paycheck où une machine qui permet de voir le futur ne peut faire que des prédictions autoréalisatrices : des prédictions qui se réalisent car on les connait. Il est assez évident que ce n'est pas toujours possible !).

[invite231234]

Merci Deedee !

ça fait quand même bizarre un calcul non calculable !

[Deedee81]

ça fait quand même bizarre un calcul non calculable !

Ca je ne te le fait pas dire. J'avais lu par exemple dans un article (je crois PLS) un exemple amusant avec une démonstration détaillée :

Quel est le plus grand nombre que je peux écrire avec n caractères ? Appelons ce nombre N(n).

Exemple avec deux lettre : "un", mais je peux faire mieux : "99".

En excluant les phrases qui ne définissent pas vraiment un nombre ("truc", "banane", etc...) ou les phrases auto-référentes :
"le plus grand nombre que je peux écrire avec 50 caractères + 1" (cette phrase fait 50 caractères )

Et bien, cette fonction N(n) n'est pas calculable !!!! (au sens donné ci-dessus)

Quand j'ai lu ça la première fois, j'ai été stupéfait. J'étais jeune (il y a donc longtemps ) et ça m'a donné envie de lire les théories de Turing, sur la calculabilité, la complexité, etc....

[exciton]

Quel est le plus grand nombre que je peux écrire avec n caractères ? Appelons ce nombre N(n).

La fonction N(n) me semble calculable au sens de Turing. Voici une méthode de calcul par force brute.

fonction N(n)
{
plus_grand_nombre := 0

Pour toutes les phrases x de 1 à n caractères faire
Si Est_Un_Nombre(x)
plus_grand_nombre := max(Lire_Nombre(x), plus_grand_nombre)
Fin Si
Fin pour

Retourner plus_grand_nombre
}

Cette algorithme a une complexité exponentielle pour les nombres écrits en chiffres et en lettres.

Mais si on autorise des définitions arbitraires, le calcul bloque sur certaines phrases (ex: "la plus courte preuve que P!=NP").

[invite73192618]

Certains chercheurs suspectent que BQP, la classe des calculs quantiques "faciles", contiendrait des problèmes inaccessibles à un ordinateur classique.

Il faut différencier la complexité de la calculabilité. Au sens de calculabilité, on sait que BQP est une classe calculable, donc calculable par (l'idéalisation d') un ordinateur classique. Ce qui est suspecté (mais non prouvé formellement) c'est que le temps de résolution de problèmes dans BQP par un ordinateur classique est (plus que polynomialement) plus long que par un ordinateur quantique (si telle chose est possible, ce qui est très très probable pour des raisons fortes mais reste à réaliser).

Alors je me demande si la relativité générale apporterait encore plus de puissance.

Peut-être que oui, peut-être que non. Le truc que c'est que cela dépend de ce que la relativité générale autorise:
-si on pense que la relativité générale n'autorise pas de boucle temporelle ni de tachyon, alors il n'y a aucun gain à attendre (c'est probablement la position la plus raisonnable).
-si la relativité générale autorise des boucles temporelles mais que ces boucles respectent la causalité (situation qui serait analogue à l'intrication de paires EPR où des changements se produisent instantanément et pourtant sans violation de causalité), alors celles-ci mèneraient à un gain de puissance absolument colossal (sans toutefois permettre de résoudre des problèmes incalculables au sens de la théorie de la calculabilité).
-si la relativité générale autorise des violations de causalité (comme on pourrait naïvement le penser en présence d'intrication quantique ou en cas de tachyon) alors cela permettrait de l'hypercalcul donc de résoudre des problèmes incalculables, ce qui aurait très probablement des conséquences quasi magiques de type voyage dans le temps et énergie gratuite.

Brut de décoffrage, la relativité générale est en soit parfaitement compatible avec chacun de ces scénarios. Comme dit Deedee81, à l'intuition les physiciens considèrent généralement que la dernière situation est non physique (et ne sont généralement pas au courant de la seconde ).

ça fait quand même bizarre un calcul non calculable !

Plus bizarre encore, on peut faire des niveaux dans l'incalculable, chaque niveau supérieur étant incalculable du point de vue du niveau précédent. On peut le prouver mais bonjour pour l'interprétation!

La fonction N(n) me semble calculable au sens de Turing.

Il existe une preuve ultra-classique qu'elle ne l'est pas (calculable). Que se passe-t-il quand n est suffisamment grand pour contenir la description de la fonction N?

[invite73192618]

PS:

Toute fonction calculable par un ordinateur quantique l'est aussi par un ordinateur classique. L'ordinateur quantique offre seulement une possibilité d'exécuter beaucoup plus rapidement ces calculs, notamment ceux dit NP-Complet.

Tu as tout-à-fait raison pour la première partie, mais il est très improbable que les ordinateurs quantiques puissent résoudre des problèmes NP-complet (bien sur ce n'est pas prouvé puisqu'on ne sait pas prouver P<NP, mais BQP est entre les deux).

[exciton]

J'ai trouvé des articles intéressants sur la question.

1/ NP-complete Problems and Physical Reality

Réf: http://arxiv.org/pdf/quant-ph/0502072.pdf

Il définit de nouvelles classes de complexité pour le calcul gravito-quantique: BQGP (Bounded-Error Quantum Gravity Polynomial Time) et BQ_CTC (Bounded-Error Closed Timelike Curve).

- BQ_CTC est la classe des fonctions calculables avec des boucles temporelles. Elles doivent satisfaire des conditions de causalité du type "On ne peut pas remonter dans le temps pour tuer son grand-père". Ça peut se formaliser par une équation au point fixe: x = f(x).

Il n'existe pas toujours de solution déterministe mais une solution aléatoire est possible: D = f(D) avec D une distribution de probabilité sur l'espace de valeur. Il est impératif que la fonction soit réversible ce qui est le cas en mécanique quantique.

Par exemple, le paradoxe du grand-père se résout si on nait avec une chance sur deux. Cela donne un résultat probabiliste cohérent.

"you are born with 1/2 probability, and if you are born you go back in time to kill your grandfather, from which it follows that you are born with 1/2 probability, and so on."

Scott Aaronson montre que la physique quantique n'augmente pas la puissance de calcul des boucles temporelles. On a donc BQ_CTC = PCTC. Et même mieux, PCTC = PSPACE. On pourrait donc résoudre des problèmes PSPACE-Complet à l'aide de la relativité générale. C'est bien plus vaste que NP.

Cependant, la nature probabiliste du résultat pourrait être inexploitable. On n'en sait rien.

- BQGP est la classe des fonctions calculables en temps polynomial sur un ordinateur gravito-quantique. Ils n'ont pas avancé sur ce terrain car la notion de temps n'est pas claire dans ce modèle de calcul. Il est difficile d'imaginer comment ça fonctionnerait.

2/ Breaking the Turing Barriers

Réf: http://www.cs.swan.ac.uk/cie06/files...esentation.pdf

Ils ne présentent pas un ordinateur gravito-quantique à proprement parler. Ils se basent sur les différences d'écoulement du temps dans un champs de gravité. Ainsi, le temps passe plus vite dans l'espace que sur Terre. Leur première idée était donc de calculer en apesanteur mais l'accélération serait ridiculement faible (ex: la correction relativiste des GPS est de quelques microsecondes).

Leur deuxième idée est de se rendre sur astre très massif. Le "mieux" serait un trou noir car l'accélération devient infinie à l'approche de la singularité d'espace-temps.

D'après ce que je comprend, ce serait une sorte d'hibernation gravitationnelle. On vivrait au ralenti dans un trou noir tandis que le reste changerait à vitesse grand V. Il serait possible de revenir dans un milliard d'années le temps que les calculs soient finis.

Cette seconde approche ne me plait pas mais ça fonctionne en théorie.

[Deedee81]

Salut,

mais il est très improbable que les ordinateurs quantiques puissent résoudre des problèmes NP-complet

"Résoudre rapidement" je suppose (car on sait déjà les résoudre, c'est juste trop long ).

Improbable je ne sais pas mais non prouvé, ça oui. J'ai déjà lu de sérieuses objections. Mais je ne connais pas assez pour savoir quelle est la situation exacte de la question en l'état actuel.

[exciton]

"Résoudre rapidement" je suppose (car on sait déjà les résoudre, c'est juste trop long ).

Improbable je ne sais pas mais non prouvé, ça oui. J'ai déjà lu de sérieuses objections. Mais je ne connais pas assez pour savoir quelle est la situation exacte de la question en l'état actuel.

Moi aussi je doute sérieusement que ce soit possible, surtout qu'un ordinateur quantique retourne des résultats aléatoires, de même qu'une machine à base de boucles temporelles. Au pire, il faut répéter l'opération un nombre exponentiel de fois pour obtenir la réponse correcte.

De plus, le théorème de hiérarchie démontre l'existence de problèmes aussi durs que l'on veut: en O(n), O(n^2), ..., O(n^1 000 000). Et ce serait étrange qu'un problème NP-Complet ne soit pas le plus dur de la classe NP ...
http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Par exemple, si on pouvait résoudre SAT en O(n^3), on le trouverait "facile" comparé au test de primalité en O(n^12). Une telle inversion me parait improbable .

[exciton]

"Résoudre rapidement" je suppose (car on sait déjà les résoudre, c'est juste trop long ).

Improbable je ne sais pas mais non prouvé, ça oui. J'ai déjà lu de sérieuses objections. Mais je ne connais pas assez pour savoir quelle est la situation exacte de la question en l'état actuel.

Moi aussi je doute sérieusement que ce soit possible, surtout qu'un ordinateur quantique retourne des résultats aléatoires, de même qu'une machine à base de boucles temporelles. Au pire, il faut répéter l'opération un nombre exponentiel de fois pour obtenir la réponse correcte.

De plus, le théorème de hiérarchie démontre l'existence de problèmes aussi durs que l'on veut: en O(n), O(n^2), ..., O(n^1 000 000). Et ce serait étrange qu'un problème NP-Complet ne soit pas le plus dur de la classe NP ...
http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Par exemple, si on pouvait résoudre SAT en O(n^3), on le trouverait "facile" comparé au test de primalité en O(n^12). Une telle inversion me parait improbable .

[invite73192618]

"Résoudre rapidement" je suppose (car on sait déjà les résoudre, c'est juste trop long ).

Oui! Merci pour l'ajout de précision En fait moui: associer "rapidement" et "en temps polynomial" n'est pas tout-à-fait juste

De plus, le théorème de hiérarchie démontre l'existence de problèmes aussi durs que l'on veut: en O(n), O(n^2), ..., O(n^1 000 000). Et ce serait étrange qu'un problème NP-Complet ne soit pas le plus dur de la classe NP ...

Le N en vert est de trop n'est-ce pas?

[invitec96cb2be]

Bonsoir la science avance toujours un peu, la réalisation de composants à intrication plutot que de couches : http://www.presence-pc.com/actualite...nsistor-43575/ et la greffe de cellules vivantes sur des composants électroniques : http://www.letemps.ch/Page/Uuid/5792..._un_ordinateur, après la mecanique quantique, c'est des paradoxes et des évènements difficilement appréhendables par notre jugement...

[evrardo]

Un ordinateur gravito quantique?
Pourquoi faire?
Les ordinateurs qu'on utilise sont déjà largement assez puissants pour les usages qu'on en fait.
Qu'est ce qu'on ferait de plus avec un ordinateur qui stocke 100 fois plus d'infos et qui calcule 100 fois plus vite?

[exciton]

Ben on pourrait résoudre des problèmes NP-difficiles. Ils apparaissent dans bon nombre de calculs économiques et scientifiques. Par exemple, l'optimisation d'une chaine logistique, la découverte de nouveaux médicaments/matériaux, les défis énergétiques de demain.

D'ailleurs, on développe sans cesse de nouveaux supercalculateurs. Le dernier en date dépasse le pétaflops (10^15 opérations/secondes) et les chercheurs prévoient atteindre l'exaflops d'ici quelques années, soit la puissance de calcul du cerveau humain. Mais avec la technologie actuelle, il faudrait une centrale nucléaire pour faire tourner un tel "monstre". Un processeur classique est très gourmand en énergie et dégage beaucoup de chaleur. Il faut donc inventer des solutions innovantes.

[evrardo]

les chercheurs prévoient atteindre l'exaflops d'ici quelques années, soit la puissance de calcul du cerveau humain. .

Je me demande comment est ce qu'un ordinateur pourrait avoir la puissance de l'intuition de notre cerveau. Cela ne se détermine pas en nombre d'opérations par secondes, mais par le sentiment qu'on peut avoir.

[exciton]

C'est plus simple que ça. On estime qu'il faudrait un exaflops pour simuler 100 milliards de neurones humains avec 10 000 synapses en moyenne. Bien sûr, ça reste très théorique vu qu'on ne dispose pas du schéma de connexion complet. Mais c'est le minimum si on espère égaler l'Homme un jour.

[evrardo]

C'est plus simple que ça. On estime qu'il faudrait un exaflops pour simuler 100 milliards de neurones humains avec 10 000 synapses en moyenne. Bien sûr, ça reste très théorique

Oui, très très théorique.
Apprenons déjà à nous servir de notre cerveau...

[exciton]

Ben oui, c'est de la recherche fondamentale. Ça montre que nos ordinateurs sont beaucoup trop lents pour avoir l'air intelligent. Fais le calcul : 10^18 opérations nerveuses = 30 ans de calcul sur un processeur 1GHz. Ça correspond à une seconde d'activité cérébrale.

Du coup, les démonstrations d'IA fonctionnent en régime très dégradé, l'équivalent d'un cerveau un milliard de fois plus petit, pas plus gros qu'une mouche

[evrardo]

Ben oui, c'est de la recherche fondamentale. Ça montre que nos ordinateurs sont beaucoup trop lents pour avoir l'air intelligent. Fais le calcul : 10^18 opérations nerveuses = 30 ans de calcul sur un processeur 1GHz. Ça correspond à une seconde d'activité cérébrale.

Du coup, les démonstrations d'IA fonctionnent en régime très dégradé, l'équivalent d'un cerveau un milliard de fois plus petit, pas plus gros qu'une mouche

Et donc pour arriver à réaliser des ordinateurs beaucoup plus puissants, il faudra qu'on multiplie le nombre de nos "opérations nerveuses" dans notre cerveau. Donc plus on fait des ordinateurs intelligents, plus on devient intelligents.
Les ordinateurs sont donc condamnés à toujours nous suivre.

[myoper]

Ben oui, c'est de la recherche fondamentale. Ça montre que nos ordinateurs sont beaucoup trop lents pour avoir l'air intelligent. Fais le calcul : 10^18 opérations nerveuses = 30 ans de calcul sur un processeur 1GHz. Ça correspond à une seconde d'activité cérébrale.

Du coup, les démonstrations d'IA fonctionnent en régime très dégradé, l'équivalent d'un cerveau un milliard de fois plus petit, pas plus gros qu'une mouche

Et donc pour arriver à réaliser des ordinateurs beaucoup plus puissants, il faudra qu'on multiplie le nombre de nos "opérations nerveuses" dans notre cerveau. Donc plus on fait des ordinateurs intelligents, plus on devient intelligents.
Les ordinateurs sont donc condamnés à toujours nous suivre.

Bonsoir.
J'ai du mal à suivre le raisonnement.
Par exemple, pourquoi et comment ces ordinateurs nous rendraient plus intelligents (greffe ?) ?

[exciton]

Et donc pour arriver à réaliser des ordinateurs beaucoup plus puissants, il faudra qu'on multiplie le nombre de nos "opérations nerveuses" dans notre cerveau. Donc plus on fait des ordinateurs intelligents, plus on devient intelligents.
Les ordinateurs sont donc condamnés à toujours nous suivre.

Je vois pas comment tu parviens à cette conclusion. Pour faire simple, les logiciels d'IA sont beaucoup trop lourds pour les ordinateurs d'aujourd'hui. Attendons les processeurs exaflops pour voir ce que ça donne.

On peut comparer avec l'affichage graphique. Il y a 40 ans, on avait des jeux affreux du style Pong, maintenant on simule des univers 3D hyper-réalistes avec calcul d'effets d'ombres et de lumière. C'était pas possible avec les tout premiers processeurs car ça coute coute des milliers d'opérations par pixel et l'écran en contient des millions (1024x768 x 3 canaux RVB). Total = environ un milliard d'opérations graphiques.

Pour répondre à ta question, les ordinateurs ne rendront pas l'homme plus intelligents. Ils feront les choses à notre place et pourront se programmer tout seul mieux qu'un humain ne le ferait. Ça porte un nom: la singularité. Ce seront les êtres les plus intelligents sur Terre et l'Homme restera loin derrière eux.

[invite73192618]

Du coup, les démonstrations d'IA fonctionnent en régime très dégradé, l'équivalent d'un cerveau un milliard de fois plus petit, pas plus gros qu'une mouche

C'est pas faux, mais la puissance brute n'est pas tout non plus. En théorie on a largement la capacité d'émuler un cerveau d'abeille, pourtant celles-ci ont des comportements qu'on aimerait bien pouvoir programmer, par exemple en reconnaissance d'image.

http://www.plosone.org/article/info:...l.pone.0004086

Dans la même veine un aphorisme dit qu'en terme de résolution de SAT il vaut mieux avoir les algorithmes d'aujourd'hui tournant sur un hardware datant de trente ans, que les algorithmes d'il y a trente ans tournant sur un hardware actuel.

[yoda1234]

Ben on pourrait résoudre des problèmes NP-difficiles. Ils apparaissent dans bon nombre de calculs économiques

Je ne pense pas que ce soit souhaitable dans le domaine de l'économie, c'est déjà assez casse-gueule avec le HFT (High Frequency Trading). J'ai lu quelques articles qui seraient hors charte ici, mais qui sont intéressants et inquiétants.

[evrardo]

Bonsoir.
J'ai du mal à suivre le raisonnement.
Par exemple, pourquoi et comment ces ordinateurs nous rendraient plus intelligents (greffe ?) ?

Bonjour Myoper.
Tout simplement parce que pour arriver à créer des ordinateurs et des logiciels d'IA plus puissants, on doit développer nos capacités cérébrales, donc devenir plus intelligents.