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

The frontiers collection

Computation and Simulation

Liam Graham

Published Jan 1, 2025• 0 citations
Publisher

Abstract

Computation and simulation are key parts of the scientific project and are also central to understanding emergence. After a general discussion of the role of simulations in science, the chapter turns to the theory of computation, Turing machines and the Church-Turing principle. Limits to the scope of simulation would imply limits to science. Absolute limits would arise if some things are non-computable. Thinking about practical limits leads us to quantum computers, quantum simulations and an estimation of the computational capacity of the universe. The physical version of the Church-Turing principle states that if we can build a universal quantum computer we can simulate every physical system.

DOI
10.1007/978-3-031-69288-8_5

Related papers

Church’s Thesis, Turing’s Limits, and Deutsch’s Principle

Rossella Lupacchini

In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.

Cambridge University Press eBooks•May 17, 2018•2 citations

Quantum theory, the Church–Turing principle and the universal quantum computer

David Deutsch

Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.

Proceedings of the Royal Society of London A Mathematical and Physical Sciences•Jul 8, 1985•4,778 citations

Limits of Computation and Physical Reality

Apostolos Syropoulos

The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.

WORLD SCIENTIFIC eBooks•Feb 1, 2020•0 citations

Quantum Computation

Cristopher Moore, Stephan Mertens

Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.

Oxford University Press eBooks•Aug 11, 2011•0 citations

The limits of computation

Mingji Xia, Zhengfeng Ji

The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.

Chinese Science Bulletin (Chinese Version)•Jan 25, 2016•1 citation

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2000•0 citations
Computation and simulation are key parts of the scientific project and are also central to understanding emergence. After a general discussion of the role of simulations in science, the chapter turns to the theory of computation, Turing machines and the Church-Turing principle. Limits to the scope of simulation would imply limits to science. Absolute limits would arise if some things are non-computable. Thinking about practical limits leads us to quantum computers, quantum simulations and an estimation of the computational capacity of the universe. The physical version of the Church-Turing principle states that if we can build a universal quantum computer we can simulate every physical system.
In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.
Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.
The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].