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

arXiv:quant-ph/0402128

Computable Functions, the Church-Turing Thesis and the Quantum Measurement Problem

R. Srikanth

Published Feb 18, 2004• 5 citations
arXivHTMLPDF

Abstract

It is possible in principle to construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolution, would contradict the Church-Turing thesis, which lies at the foundation of computer science. Elsewhere we have argued that the quantum measurement problem implies a finite, computational model of the measurement and evolution of quantum states. If correct, this approach helps to identify the key feature that can reconcile quantum mechanics with the Church-Turing thesis: finitude of the degree of fine-graining of Hilbert space. This suggests that the Church-Turing thesis constrains the physical universe and thereby highlights a surprising connection between purely logical and algorithmic considerations on the one hand and physical reality on the other.

DOI
10.48550/arxiv.quant-ph/0402128

Related papers

Computable Functions, Quantum Measurements, and Quantum Dynamics

Michael A. Nielsen

We construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolutions, would contradict the Church-Turing thesis which lies at the foundation of computer science. We conclude that either the Church-Turing thesis needs revision, or that only restricted classes of observables may be realized, in principle, as measurements, and that only restricted classes of unitary operators may be realized, in principle, as dynamics.

arXiv:quant-ph/9706006•Physical Review Letters•Oct 13, 1997•54 citations

Measurability and Computability

Masanao Ozawa

The conceptual relation between the measurability of quantum mechanical observables and the computability of numerical functions is re-examined. A new formulation is given for the notion of measurability with finite precision in order to reconcile the conflict alleged by M. A. Nielsen [Phys. Rev. Lett. 79, 2915 (1997)] that the measurability of a certain observable contradicts the Church-Turing thesis. It is argued that any function computable by a quantum algorithm is a recursive function obeying the Church-Turing thesis, whereas any observable can be measured in principle.

arXiv:quant-ph/9809048•Sep 16, 1998•8 citations

The Quantum Measurement Problem and Physical reality: A Computation Theoretic Perspective

R. Srikanth

Abstract. Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP-complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete subphysical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor's quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper-bounded. If this bound is associated with the quantum-classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.

•Feb 14, 2006•8 citations

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 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

Quantum computation: From Church-Turing thesis to Qubits

Shankhadip Kundu, Rajdeep Kundu, Shubhabrata Kundu +4 more

In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)•Oct 1, 2016•7 citations
It is possible in principle to construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolution, would contradict the Church-Turing thesis, which lies at the foundation of computer science. Elsewhere we have argued that the quantum measurement problem implies a finite, computational model of the measurement and evolution of quantum states. If correct, this approach helps to identify the key feature that can reconcile quantum mechanics with the Church-Turing thesis: finitude of the degree of fine-graining of Hilbert space. This suggests that the Church-Turing thesis constrains the physical universe and thereby highlights a surprising connection between purely logical and algorithmic considerations on the one hand and physical reality on the other.
The conceptual relation between the measurability of quantum mechanical observables and the computability of numerical functions is re-examined. A new formulation is given for the notion of measurability with finite precision in order to reconcile the conflict alleged by M. A. Nielsen [Phys. Rev. Lett. 79, 2915 (1997)] that the measurability of a certain observable contradicts the Church-Turing thesis. It is argued that any function computable by a quantum algorithm is a recursive function obeying the Church-Turing thesis, whereas any observable can be measured in principle.
Abstract. Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP-complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete subphysical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor's quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper-bounded. If this bound is associated with the quantum-classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
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.
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].
In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.