Tu sais que tous les algorithmes quantiques connus ne donnent en temps polynomial aucun résultat correct avec une probabilité égale à 1.
Tu définis les critères qui satisfont tes désirs ...
ça c'est du blabla, pas un algorithme. Donc toujours rien ...
Si tu comprends ce que tu cites (et si tu connais un tout petit peu le sujet) tu te rends compte que c'est exactement ce que je décris depuis le début :
* toutes les machines de Turing sont équivalentes (cf #127, #134, #137)
* les algo quantiques n'impliquent pas une accélération exponentielle des algo classiques (cf #127, #134)
* l'aléatoire est pris en compte dans la théorie (cf #145,#146)
* il ne te reste plus comme échappatoire les supertâches et l'hypercalcul (cf #127) ... bonne chance
En aparté : dans ta citation wikipedia il y a une note de bas de page, la numéro 9 :
Même dans cet article vulgarisant ces notions, il est important de ne pas mécomprendre ce qui est entendu par «Elles sont même, d'un certain point de vue, moins complètes que les machines de Turing classiques» ... l'auteur est, il est vrai quelque peu maladroit dans sa formulation. Ce fameux point de vue ne fait que reprendre le fait que l'accélération n'est pas forcément exponentielle, rien de plus.[...] propriétés parmi toutes les propriétés conjointes possibles étaient calculables de cette manière, alors qu'elles les sont toutes avec une machine de Turing classique9.
[...]
9 Mais, évidemment, une machine de Turing quantique pouvant simuler une machine de Turing classique, une machine de Turing quantique est capable de calculer toutes les propriétés conjointes, mais sans utiliser ses propriétés propres
-----