His work on quantum algorithms began with a 1985 paper, later expanded in 1992 along with Richard Jozsa, to produce the Deutsch–Jozsa algorithm, one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. In his nomination for election as a Fellow of the Royal Society (FRS) in 2008, his contributions were described as: