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.[5] In his nomination for election as a Fellow of the Royal Society (FRS) in 2008, his contributions were described as:[4]
[having] laid the foundations of the quantum theory of computation, and has subsequently made or participated in many of the most important advances in the field, including the discovery of the first quantum algorithms, the theory of quantum logic gates and quantum computational networks, the first quantum error-correction scheme, and several fundamental quantum universality results. He has set the agenda for worldwide research efforts in this new, interdisciplinary field, made progress in understanding its philosophical implications (via a variant of the many-universes interpretation) and made it comprehensible to the general public, notably in his book The Fabric of Reality.
Since 2012,[8] he has been working on constructor theory, an attempt at generalizing the quantum theory of computation to cover not just computation but all physical processes.[9][10] Together with Chiara Marletto, he published a paper in December 2014 entitled Constructor theory of information, that conjectures that information can be expressed solely in terms of which transformations of physical systems are possible and which are impossible.[11][12]
In his 1997 book The Fabric of Reality, Deutsch details his "Theory of Everything". It aims not at the reduction of everything to particle physics, but rather mutual support among multiversal, computational, epistemological, and evolutionary principles. His theory of everything is somewhat emergentist rather than reductive. There are four strands to his theory:
Karl Popper's epistemology, especially its anti-inductivism and requiring a realist (non-instrumental) interpretation of scientific theories, as well as its emphasis on taking seriously those bold conjectures that resist falsification.
In a 2009 TED talk, Deutsch expounded a criterion for scientific explanation, which is to formulate invariants: "State an explanation [publicly, so that it can be dated and verified by others later] that remains invariant [in the face of apparent change, new information, or unexpected conditions]".[13]
"A bad explanation is easy to vary."[13]: minute 11:22
"The search for hard-to-vary explanations is the origin of all progress"[13]: minute 15:05
"That the truth consists of hard-to-vary assertions about reality is the most important fact about the physical world."[13]: minute 16:15
Deutsch's second book, The Beginning of Infinity: Explanations that Transform the World, was published on 31 March 2011. In this book, he views the European Enlightenment of the 17th and 18th centuries as near the beginning of a potentially unending sequence of purposeful knowledge creation. He examines the nature of knowledge, memes, and how and why creativity evolved in humans.[15]
Deutsch supported Brexit, with his advocacy quoted by the then government adviser, Dominic Cummings.[22] Although Cummings quoted Deutsch in relation to his campaign for Brexit,[23] Deutsch claimed that he "had absolutely no effect on the campaign".[24]: 00:28 Regarding his mention by Michael Gove during a BBC Brexit debate, he said "No-one was more surprised than I."[24]: 00:10 Regarding the debate, he also said:
"In Britain there is a clear path if you have a grievance, you can join a pressure-group, the pressure-group will pressure the government, or you can see your MP, and the MP will see the grievance building up, and so-on. Whereas, Europe is structured in such a way that it's very difficult to know whom to address your grievance to, or what they could do about it."
^ abc"Professor David Deutsch FRS". royalsociety.org. London: Royal Society. 2008. Archived from the original on 16 November 2015. Retrieved 14 November 2017. One or more of the preceding sentences incorporates text from the royalsociety.org website where: