Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

WORLD SCIENTIFIC eBooks

What is Computation? (How) Does Nature Compute?

David Deutsch

Published Oct 18, 2012• 6 citations
Publisher

Abstract

Figure 1: Introducing David Deutsch Adrian German (addressing the audience1): Our next guest is the recipient of the 2005 Edge of Computation Science Prize and will be speaking to us via video-link2 from the University of Oxford. He pioneered the field of quantum computation and was the first person to formulate a description for a quantum Turing machine and to specify an algorithm designed to run on a quantum computer. He is also a proponent of the many-worlds interpretation of quantum mechanics and his new book entitled “The Beginning of Infinity” is due to appear early next year3. Ladies and gentlemen it is with great pleasure that I am asking you now to join me in welcoming Prof. David Deutsch. (Applause.) And with

DOI
10.1142/9789814374309_0028

Related papers

The Computer, from Physics to Biology

Bernard Dugué

Turing's machine and the quantum computer are epistemological markers of the author's time, which for some 70 years witnessed the emergence of a physics of information that completes the mechanical physics inherited from the 19th Century. Since the late 19th Century, biology has been in the “trailer” of physics. For Seth Lloyd, as for David Deutsch, current physical laws must be surpassed in order to understand nature, and especially this order in the universe which cannot be explained by narrow classical theories, particularly “computation” theories, solely based on binary calculators that follow Turing's machine paradigm. Contemporary quantum physics suggests that if there is affinity and coupling, it is because there are resonances, because there is communication and information transfer. The quantum calculator associates the computer with information which is no longer numerical but quantum.

Wiley eBooks•Apr 16, 2018•0 citations

An Introduction to Quantum Computing

David K. Ferry

The idea of using quantum mechanics to provide more power than classical computers seem to have begun around 1981 to 1982, but Deutsch put the concept on a sounder footing a short time later. Deutsch reformulated the Turing thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Progress beyond mathematical approaches came later when Lloyd suggested that arrays of weakly coupled quantum systems might be able to serve as the quantum computer if they were subjected to a sequence of controlled electromagnetic pulses, which could place the quantum bits into the desired super-positions. It was John von Neumann, working with the computer pioneers at the University of Pennsylvania, who suggested that the binary system should be used for simplicity in building computers.

CRC Press eBooks•Nov 6, 2020•17 citations

Deutsch's Universal Quantum Turing Machine (Revisited)

Willem L. Fouché, Johannes Heidema, Jones, Glyn +1 more

Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.

arXiv:quant-ph/0701108•Jan 16, 2007•8 citations

Physics and Computation

Armond Duwell

This Element has three main aims. First, it aims to help the reader understand the concept of computation that Turing developed, his corresponding results, and what those results indicate about the limits of computational possibility. Second, it aims to bring the reader up to speed on analyses of computation in physical systems which provide the most general characterizations of what it takes for a physical system to be a computational system. Third, it aims to introduce the reader to some different kinds of quantum computers, describe quantum speedup, and present some explanation sketches of quantum speedup. If successful, this Element will equip the reader with a basic knowledge necessary for pursuing these topics in more detail.

Cambridge University Press eBooks•Aug 20, 2021•35 citations

Keynote Speech: Quantum Physics and the Nature of Computation

Umesh V. Vazirani

Quantum physics is a fascinating area from a computational viewpoint. The features that make quantum systems prohibitively hard to simulate classically are precisely the aspects exploited by quantum computation to obtain exponential speedups over classical computers. In this talk I will survey our current understanding of the power (and limits) of quantum computers, and prospects for experimentally realizing them in the near future. I will also touch upon insights from quantum comuptation that have resulted in new classical algorithms for efficient simulation of certain important quantum systems.

IEEE International Parallel and Distributed Processing Symposium (IPDPS)•Mar 1, 2007•2 citations

Varieties of Divergence: A Response to Saunders and Wallace

Paul Tappenden

I continue to maintain that David Lewis’s concept of overlapping persons cannot yield pre-measurement uncertainty in the Everett interpretation of quantum mechanics in the way that Simon Saunders and David Wallace originally seemed to suggest. However, I argue that in their reply to me they make it clear that they do not wish to invoke overlap of persons after all. That makes it mysterious why they defended their interpretation of personal overlap in the first place and questionable what role overlap has to play in their proposal. If Everettian branching can be understood to involve the divergence of distinct, non-overlapping worlds a concept of pre-measurement uncertainty is available. That idea was first proposed by David Deutsch but required an ad hoc postulate. Saunders has recently suggested that a similar scheme arises naturally out of the physics. If correct, that is important as it offers escape from some bizarre consequences of current alternative ways of understanding probability in the Everett interpretation

•Jun 1, 2010•1 citation
Figure 1: Introducing David Deutsch Adrian German (addressing the audience1): Our next guest is the recipient of the 2005 Edge of Computation Science Prize and will be speaking to us via video-link2 from the University of Oxford. He pioneered the field of quantum computation and was the first person to formulate a description for a quantum Turing machine and to specify an algorithm designed to run on a quantum computer. He is also a proponent of the many-worlds interpretation of quantum mechanics and his new book entitled “The Beginning of Infinity” is due to appear early next year3. Ladies and gentlemen it is with great pleasure that I am asking you now to join me in welcoming Prof. David Deutsch. (Applause.) And with
Turing's machine and the quantum computer are epistemological markers of the author's time, which for some 70 years witnessed the emergence of a physics of information that completes the mechanical physics inherited from the 19th Century. Since the late 19th Century, biology has been in the “trailer” of physics. For Seth Lloyd, as for David Deutsch, current physical laws must be surpassed in order to understand nature, and especially this order in the universe which cannot be explained by narrow classical theories, particularly “computation” theories, solely based on binary calculators that follow Turing's machine paradigm. Contemporary quantum physics suggests that if there is affinity and coupling, it is because there are resonances, because there is communication and information transfer. The quantum calculator associates the computer with information which is no longer numerical but quantum.
The idea of using quantum mechanics to provide more power than classical computers seem to have begun around 1981 to 1982, but Deutsch put the concept on a sounder footing a short time later. Deutsch reformulated the Turing thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Progress beyond mathematical approaches came later when Lloyd suggested that arrays of weakly coupled quantum systems might be able to serve as the quantum computer if they were subjected to a sequence of controlled electromagnetic pulses, which could place the quantum bits into the desired super-positions. It was John von Neumann, working with the computer pioneers at the University of Pennsylvania, who suggested that the binary system should be used for simplicity in building computers.
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.
This Element has three main aims. First, it aims to help the reader understand the concept of computation that Turing developed, his corresponding results, and what those results indicate about the limits of computational possibility. Second, it aims to bring the reader up to speed on analyses of computation in physical systems which provide the most general characterizations of what it takes for a physical system to be a computational system. Third, it aims to introduce the reader to some different kinds of quantum computers, describe quantum speedup, and present some explanation sketches of quantum speedup. If successful, this Element will equip the reader with a basic knowledge necessary for pursuing these topics in more detail.
Quantum physics is a fascinating area from a computational viewpoint. The features that make quantum systems prohibitively hard to simulate classically are precisely the aspects exploited by quantum computation to obtain exponential speedups over classical computers. In this talk I will survey our current understanding of the power (and limits) of quantum computers, and prospects for experimentally realizing them in the near future. I will also touch upon insights from quantum comuptation that have resulted in new classical algorithms for efficient simulation of certain important quantum systems.
I continue to maintain that David Lewis’s concept of overlapping persons cannot yield pre-measurement uncertainty in the Everett interpretation of quantum mechanics in the way that Simon Saunders and David Wallace originally seemed to suggest. However, I argue that in their reply to me they make it clear that they do not wish to invoke overlap of persons after all. That makes it mysterious why they defended their interpretation of personal overlap in the first place and questionable what role overlap has to play in their proposal. If Everettian branching can be understood to involve the divergence of distinct, non-overlapping worlds a concept of pre-measurement uncertainty is available. That idea was first proposed by David Deutsch but required an ad hoc postulate. Saunders has recently suggested that a similar scheme arises naturally out of the physics. If correct, that is important as it offers escape from some bizarre consequences of current alternative ways of understanding probability in the Everett interpretation