The physical Church-Turing thesis and the principles of quantum theory

DOI10.1142/S0129054112500153zbMATH Open1279.68096arXiv1102.1612OpenAlexW2962804872MaRDI QIDQ4902897FDOQ4902897

Authors: Pablo Arrighi, Gilles Dowek 

Publication date: 18 January 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information --- and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

Full work available at URL: https://arxiv.org/abs/1102.1612

Recommendations

• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• scientific article
• Around the physical Church-Turing thesis: cellular automata, formal languages, and the principles of quantum theory
• The computational status of physics
• Hypercomputation and the Physical Church‐Turing Thesis

zbMATH Keywords

cellular automataquantum computing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Cellular automata (computational aspects) (68Q80)

Cites Work

• Non-Turing computations via Malament--Hogarth space-times
• Quantum theory: concepts and methods
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Embedding infinitely parallel computation in Newtonian kinematics
• Experimental computation of real numbers by Newtonian machines
• Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
• Locality and information transfer in quantum operations
• More really is different
• Title not available (Why is that?)

Cited In (14)

• What is the Church-Turing Thesis?
• The stochastic thermodynamics of computation
• Semantics of quantum programming languages: Classical control, quantum control
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• An overview of quantum cellular automata
• Quantum principles and mathematical computability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Physical thinking and the GHZ theorem
• Deutsch's ``Quantum theory as a universal physical theory
• On the completeness of quantum computation models
• Around the physical Church-Turing thesis: cellular automata, formal languages, and the principles of quantum theory
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Classical physics and the Church--Turing Thesis

This page was built for publication: The physical Church-Turing thesis and the principles of quantum theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902897)