Un ordinateur quantique est, rappelons-le, un modèle de calcul qui exploite astucieusement certaines caractéristiques de la mécanique quantique (la superposition des états et l’intrication) pour construire des algorithmes qui, dans certains cas précis, battraient à plate couture toute machine classique, basée sur le modèle usuel de Türing. Toute nos machines actuelles sont basées sur ce dernier modèle.
Les deux principales catégories d’algorithme pour lesquels une machine quantique sera littéralement imbattable par n'importe quelle machine classique sont:
- Les algo du type de celui de Peter Shor qui permet de factoriser un grand nombre en ses facteurs premier en un temps polynomial (dans le nombre de bits du nombre à factoriser). Une grande partie de la cryptographie, et en particulier l’algo RSA seraient alors menacé d’être craquer… D’où les phantasmes suscités par la possible réalisation de telles machines
- Les algo du type de celui de Grover qui permet d’effectuer des recherches dans des listes non-structurées en en temps d’ordre racine(N) plutôt que N. Le gain, s’il est moins spectaculaire que dans le premier cas, reste appréciable et permet par exemple d’accélérer la découverte de solutions de problème NP-complet de type voyageur de commerce.
Or voici deux jours que la blogosphère et même la presse bruissent d’une rumeur faisant état de l’exploitation par Google d’un nouveau type de processeur quantique, réalisé par une boite canadienne (D-Wave). Un nouveau type d’algo (Adiabatic Quantum Computing AQC) serait utilisé pour la reconnaissance d’images. Il semblerait que cette nouvelle puce "magique", qui comporterait 16 Q-bits, ferait des miracles. La prétendue nature quantique est pour l'instant sujet à controverse parmi les spécialistes. Pour autant les performances sont bien là et naturellement pour Google c'est ce qui compte.
Quid du décryptage de RSA alors ? Il semble que de ce côté il n’y a pas encore trop de soucis à se faire, car un tel exploit nécessiterait un processeur quantique de plusieurs centaines de Q-bits, à des années lumières des 16 Q-bits du processeur de D-Wave.
Et pour les petits malins qui penseraient qu'il suffit de mettre en parallèle 'N' chips de 'M' Q-bits pour réaliser une machine quantique de (N*M) Q-bits... ben ça marche pas... eh oui, ça serait trop facile ;-)
Une affaire à suivre dans tous les cas…
Merci à Quang TU LE et Arnaud DESLANDES pour m'avoir transmis l'info.
Pour les geeks, voici le commentaire le plus clair que j’ai lu dans ce débat, il émane de l’auteur du projet lui-même, en réponse à une remarque d’un autre commentateur sur le blog de recherche de Google:
Dear Mike,
Thanks for mentioning my work but this forced me to clarify some confusions.
1. The article you refer to, I think, is PRA 79, 022107 (2009). At the end of this article we state that local AQC requires quantum coherence in order to have scaling benefit. However, local AQC is unfeasible anyway because one needs to know the spectrum before hand. In real life one would never use local AQC, and for usual AQC (which is what we do in
practice) as we showed in the same paper, quantum coherence is not crucial.
2. This brings me to your other remark about coherence. There is a false belief that coherence is the only quantum mechanical effect that exists in the world. Quantum mechanics was not discovered by observing coherence but was by observing energy quantization. Indeed energy quantization is the only thing you need for AQC and coherence (I mean coherence in the energy basis) is unimportant. Of course strong coupling to environment will screw up energy quantization eventually, but there is much more robustness compared to other models of quantum computation.
Every measurement on our qubits so far has been in complete agreement with quantum mechanics, even in coherent regime. We have a measurement of quantum tunneling amplitude in the coherent regime in complete agreement with quantum predictions (see figure 15b in arXiv:0909.4321).
We haven't done coherent oscillation measurement because it is unimportant to us and it requires fast control which is not necessary for AQC.
3. Finally it comes the question of scaling of AQC. Up to now true scaling is unknown. There are some features that can make a problem very difficult (see arXiv:0904.1387) but there may be some ways around it (see arXiv:0909.4766). But for a company like Google or us it is not the scaling in the complexity theory sense that is important. What is important is whether the system can outperform classical computation on average for a particular type of problems.