Il existe des problèmes faciles à vérifier mais très difficiles à résoudre. Par exemple, on donne une longue chaîne de conditions, et il faut déterminer si on peut les satisfaire toutes en même temps. Si quelqu'un propose une réponse, la vérifier est rapide. Mais trouver la réponse, c'est comme essayer toutes les combinaisons d'un cadenas : à chaque nouvelle condition, le travail double.
Des chercheurs ont construit une mesure quantique qui, si elle était réalisable, résoudrait ces problèmes très vite. Mais alors elle résoudrait aussi des problèmes considérés comme insolubles même pour les ordinateurs quantiques. C'est une contradiction. Une telle mesure n'existe donc pas. Elle ressemble à une clé que les mathématiques ont dessinée, mais que le monde physique n'a pas pu fabriquer.
Il en découle une chose étrange : si la mesure est impossible, alors certaines transformations d'états quantiques le sont aussi. Et si deux états ne peuvent pas être transformés l'un en l'autre, leur mélange et leur superposition se ressemblent. Aucun appareil ne distinguera « soit l'un, soit l'autre » de « les deux à la fois ». Ces états semblent interdits par la nature elle-même, non par une loi de la physique, mais par la complexité des calculs.
On pensait autrefois que le monde quantique devenait ordinaire parce que les objets de grande taille interagissent sans cesse avec leur environnement. On découvre maintenant qu'il existe une autre raison : certains effets quantiques ne peuvent tout simplement pas être observés, car il faudrait pour cela résoudre un problème que le monde ne sait pas résoudre rapidement. La porte est verrouillée non parce que la serrure est cassée, mais parce que la clé exigerait l'impossible.
Pour annuler un résultat de mesure indésirable, on utilise un code quantique à quatre qubits, qui encode deux qubits logiques. C'est le plus petit code possible capable de corriger une erreur dont la position est connue.