Un ordinateur quantique est une machine de Turing. Il diffère des ordinateurs traditionnels non pas en s'affranchissant des limites de la calculabilité, mais par la manière dont il traite l'information. Il est toujours confiné au monde de Church–Turing. Il ne peut pas résoudre le problème de l'arrêt, ni peut-il calculer.