1
|
Fundamental Physics and Computation: The Computer-Theoretic Framework. UNIVERSE 2022. [DOI: 10.3390/universe8010040] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
The central goal of this manuscript is to survey the relationships between fundamental physics and computer science. We begin by providing a short historical review of how different concepts of computer science have entered the field of fundamental physics, highlighting the claim that the universe is a computer. Following the review, we explain why computational concepts have been embraced to interpret and describe physical phenomena. We then discuss seven arguments against the claim that the universe is a computational system and show that those arguments are wrong because of a misunderstanding of the extension of the concept of computation. Afterwards, we address a proposal to solve Hempel’s dilemma using the computability theory but conclude that it is incorrect. After that, we discuss the relationship between the proposals that the universe is a computational system and that our minds are a simulation. Analysing these issues leads us to proposing a new physical principle, called the principle of computability, which claims that the universe is a computational system (not restricted to digital computers) and that computational power and the computational complexity hierarchy are two fundamental physical constants. On the basis of this new principle, a scientific paradigm emerges to develop fundamental theories of physics: the computer-theoretic framework (CTF). The CTF brings to light different ideas already implicit in the work of several researchers and provides a new view on the universe based on computer theoretic concepts that expands the current view. We address different issues regarding the development of fundamental theories of physics in the new paradigm. Additionally, we discuss how the CTF brings new perspectives to different issues, such as the unreasonable effectiveness of mathematics and the foundations of cognitive science.
Collapse
|
2
|
Braverman M, Schneider J, Rojas C. Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems. PHYSICAL REVIEW LETTERS 2015; 115:098701. [PMID: 26371687 DOI: 10.1103/physrevlett.115.098701] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/05/2014] [Indexed: 06/05/2023]
Abstract
We report a new limitation on the ability of physical systems to perform computation-one that is based on generalizing the notion of memory, or storage space, available to the system to perform the computation. Roughly, we define memory as the maximal amount of information that the evolving system can carry from one instant to the next. We show that memory is a limiting factor in computation even in lieu of any time limitations on the evolving system-such as when considering its equilibrium regime. We call this limitation the space-bounded Church-Turing thesis (SBCT). The SBCT is supported by a simulation assertion (SA), which states that predicting the long-term behavior of bounded-memory systems is computationally tractable. In particular, one corollary of SA is an explicit bound on the computational hardness of the long-term behavior of a discrete-time finite-dimensional dynamical system that is affected by noise. We prove such a bound explicitly.
Collapse
Affiliation(s)
- Mark Braverman
- Computer Science Department, Princeton University, 35 Olden Street, Princeton, New Jersey 08540, USA
| | - Jonathan Schneider
- Computer Science Department, Princeton University, 35 Olden Street, Princeton, New Jersey 08540, USA
| | - Cristóbal Rojas
- Departamento de Matemáticas, Universidad Andres Bello, República 220, Santiago, Chile
| |
Collapse
|
3
|
Rønnow TF, Wang Z, Job J, Boixo S, Isakov SV, Wecker D, Martinis JM, Lidar DA, Troyer M. Quantum computing. Defining and detecting quantum speedup. Science 2014; 345:420-4. [PMID: 25061205 DOI: 10.1126/science.1252319] [Citation(s) in RCA: 88] [Impact Index Per Article: 8.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/02/2022]
Abstract
The development of small-scale quantum devices raises the question of how to fairly assess and detect quantum speedup. Here, we show how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup. We illustrate our discussion with data from tests run on a D-Wave Two device with up to 503 qubits. By using random spin glass instances as a benchmark, we found no evidence of quantum speedup when the entire data set is considered and obtained inconclusive results when comparing subsets of instances on an instance-by-instance basis. Our results do not rule out the possibility of speedup for other classes of problems and illustrate the subtle nature of the quantum speedup question.
Collapse
Affiliation(s)
- Troels F Rønnow
- Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland
| | - Zhihui Wang
- Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA. Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA
| | - Joshua Job
- Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA. Department of Physics, University of Southern California, Los Angeles, CA 90089, USA
| | - Sergio Boixo
- Google, 150 Main Street, Venice Beach, CA 90291, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA
| | | | - David Wecker
- Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA
| | - John M Martinis
- Department of Physics, University of California Santa Barbara, CA 93106-9530, USA
| | - Daniel A Lidar
- Department of Chemistry, University of Southern California, Los Angeles, CA 90089, USA. Center for Quantum Information Science and Technology, University of Southern California, Los Angeles, CA 90089, USA. Department of Physics, University of Southern California, Los Angeles, CA 90089, USA. Information Sciences Institute, University of Southern California, Los Angeles, CA 90089, USA. Department of Electrical Engineering, University of Southern California, Los Angeles, CA 90089, USA
| | - Matthias Troyer
- Theoretische Physik, ETH (Eidgenössische Technische Hochschule) Zurich, 8093 Zurich, Switzerland.
| |
Collapse
|