"Lorsque tu mesures un qubit, tu le détruis, et il y a des propriétés (par exemple, le non-clonage) qui font que tu ne peux pas refaire ta mesure autant de fois que tu le veux."

C'est à peu près pour les mêmes raisons que pour le chat de Schrödinger non ?
Mais dans ce cas, qu'est-ce que l'ordinateur va utiliser : la probabilité des différents états ou l'état effectivement mesuré après calcul des probabilités ?

Justement c'est là qu'est la difficulté, on ne peut pas connaître de manière exacte le qubit (= connaitre la distribution de probabilité des différents états), on peut seulement le mesurer et obtenir un état (et on ne sait pas quelle était la probabilité de l'avoir, on sait juste qu'on a eu ça !)

Pourtant, certains calculateurs quantiques ont été fabriqués (en mettant en oeuvre l'algo de Shor).
Comment ont-ils contourné ce problème de décohérence quantique ?

Ce topic part un peu à la dérive mais c'est toujours sympa d'élargir le sujet.

Ils n'ont pas "contourné" le problème, c'est juste comme ça que se comporte un algorithme quantique. L'algorithme de Shor prend tout ça en compte.

Ouais du coup, malins comme ils sont les mecs, ils ont dû réussir à transformer cet inconvénient en avantage.
Mais du coup, il doit parfois se planter votre algorithme, faut le lancer plusieurs fois pour une même tâche histoire d'être sûr ? ;o

Sinon, en parlant de P=NP, appel aux matheux et logiciens du forum. Parmi les problèmes du millénaire (qui rapportent un million de dollars à celui qui en résout un, à part s'il s'appelle Grigori Perelman), celui-là est le seul qui peut être accessible à tout le monde vu qu'il est "simple" à comprendre. Donc si vous avez du temps à perdre ... x)

Factoriser un entier est difficile, mais une fois qu'on obtient un résultat il suffit de faire la multiplication pour vérifier qu'il soit correct. Du coup si l'algo se trompe, il suffit de le relancer jusqu'à ce que ça marche.

D'où la classe de complexité BQP : "Bounded-error Quantum Poly time". Ce sont les algorithmes qui se résolvent avec un taux d'erreur borné. Une fois qu'on a ça, on peut obtenir un taux d'erreur arbitrairement petit, il suffit de réitérer l'algorithme, et on reste polynomial