En 1985 David Deutsch, en la Universidad de Oxford, publica 'Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer' en Proceedings of the Royal Society A, formalizando el primer modelo matemático de un ordenador cuántico universal. Deutsch parte de la propuesta de Feynman (1981) y la convierte en teoría rigurosa: define la máquina de Turing cuántica como generalización de la máquina de Turing clásica, introduce el concepto de qubit —un bit que puede existir en superposición de 0 y 1— y de puerta cuántica, y demuestra que un ordenador cuántico universal puede simular cualquier sistema físico finito. Crucialmente, propone el primer algoritmo cuántico con ventaja demostrable sobre cualquier algoritmo clásico: el problema de Deutsch, que determina si una función booleana es constante o equilibrada con una sola evaluación, frente a las dos que necesita cualquier algoritmo clásico. Este paper funda la teoría de la computación cuántica: sin él no existe el marco formal sobre el que Shor (1994) y Grover (1996) construyen sus algoritmos.