Komputer kuantum adalah mesin Turing. Ini berbeda dari komputer tradisional bukan dengan melepaskan diri dari batasan komputabilitas, tetapi dengan cara ia memproses informasi. Ini masih terkurung dalam dunia Church–Turing. Itu tidak dapat menyelesaikan Masalah Berhenti, juga tidak dapat menghitung