L'ordinateur quantique peut-il tout résoudre ? - Celui

Celui — Fri, 23 May 2008 23:25:12 +0200

@Tom Roud,

1- Tout dépend de ce que l'on appelle ordinateur quantique. Si on voit ça comme un ordinateur d'aujourd'hui bien plus rapide parce que « quantique » alors nous en sommes clairement loin, et d'ailleurs, rien n'est vraiment fait dans cette direction.

Les efforts se concentrent à l'heure actuelle sur des petits « calculateurs quantiques » qui ne savent faire qu'une seule opération (ou qu'un seul algorithme) et qui serait appelé par un ordinateur classique quand il en aurait besoin. Et pour cela, pour avoir un algorithme de Shor qui fonctionne, il faut peut-être attendre entre 30 ans et 50 ans. Ces chiffres sont souvent avancés, mais ne repose sur rien de sérieux.

Ce qu'il faut bien comprendre déjà, c'est que le quantique n'accélère pas les calculs, de nombreux algorithmes ont la même complexité dans le cas classique et le cas quantique. C'est pour cela que la création d'un « vrai » ordinateur quantique me semble la recherche d'une chimère.

Au début (XXème siècle), certaines expériences ont été réalisées avec un faible nombre de qubits en utilisant les techniques qu'il y avait à l'époque, principalement grâce à des appareils de RMN, faut bien que les chimistes servent de temps en temps. À l'heure actuelle, le graal, c'est la « scalability »$$je ne sais pas le terme en français, s'il existe$$, c'est arriver à faire un système qui fonctionne parfaitement, quelque soit le nombre de qubits mis en jeu.

On ne sait pas quelle technique va l'emporter en premier, et il y a fort à parier qu'elle ne tiendra que quelques décénies, mais de nombreuses sont en concurrences, ion-trap, linear optics, cavity QED, calcul adiabatique.

Ce qui existe actuellement, et qui fonctionne, est surtout dans le domaine de la cryptographie, avec des produits commerciaux développés par ID quantique du côté européen, et Magic Q. outre Atlantique. Il y a de nombreux projets qui naissent comme fournir des générateurs de nombres aléatoires, réellement aléatoires, pour éviter le fiasco debian, par exemple.

2- On ne sait pas si l'ordinateur quantique est capable ou non de résoudre les problèmes NP-complets en temps polynomial ou non. Mais on pense que non. Il y a même des résultats qui suggèrent le contraire. C'est un peu comme P et NP, rien n'est prouvé, mais il serait vraiment étonnant que P=NP.

Mais à supposer qu'on démontre un jour que NP est inclus dans BQP (la classe des problèmes faciles pour les ordinateurs quantiques), ce ne sera, à mon avis, pas en vertu de la parralélisation. Cette idée « on fait tous les calculs en parrallèles » est naïve, tentante, mais finalement un peu fausse. Autant réduire, autant essayer de retenir cette image-ci :
on peut voir un calcul f comme une opération sur If l'image de f. À chaque étape de calcul, on élimine des solutions possibles de l'algorithme: on enlève des éléments de l'ensemble If. Quand il n'en reste qu'un seul, l'algorithme se termine. Dit autrement on regarde toutes les possibilités, et on élimine au fur et à mesure celles qui sont incompatibles avec les entrées. Dans le cas quantique, c'est cette élimination qui peut aller plus vite en faisant des interférences.

3- Pour la dernière question, comme on ne sait pas encore trop à quelle sauce on va être mangé, on attend de voir. Mais on s'inquiète car à l'INRIA, il n'y a pas de calcul quantique (à ma connaissance). Sinon, il y a de très bonnes équipes à Amsterdam, à Berkeley et à Montreal et à Waterloo.

L'ordinateur quantique peut-il tout résoudre ? - Tom Roud

Tom Roud — Thu, 22 May 2008 00:04:58 +0200

Bon je n'ai pas lu l'article, donc je ne peux pas dire grand chose, mais juste poser des questions :
- l'ordinateur quantique est-il à portée de main ou est-il simplement un projet purement théorique servant de prétexte appliqué à des demandes de grants ?
- ensuite, l'ordinateur quantique est-il capable de résoudre des problèmes NP-complet en temps polynomial par la vertu de la parallélisation ?
- l'informatique quantique rentre-t-elle dans la future division physique du CNRS, sera-t-elle chapeautée par l'INRIA, ou disparaîtra-t-elle corps et bien du paysage scientifique francais ? Question subsidiaire : dans quelle commission CNRS un spécialiste de l'informatique quantique candidate-t-il avant de s'expatrier ?

L'ordinateur quantique peut-il tout résoudre ? - Raveline

Raveline — Sat, 17 May 2008 20:54:04 +0200

L'ordinateur quantique, ce que j'en pense : ça a l'air chouette, mais moins que "consistent histories". Que voulez savoir sur lui : tout, vu que je ne vois pas ce que c'est.

Modeste contribution, pour remplir ton espoir.

Griffonnages - Tag - Vulgarisation - Commentaires

L'ordinateur quantique peut-il tout résoudre ? - Celui

L'ordinateur quantique peut-il tout résoudre ? - Tom Roud

L'ordinateur quantique peut-il tout résoudre ? - Raveline