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

Measurability and Computability

Masanao Ozawa

Published Sep 16, 1998• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/9809048

Related papers

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

R. Srikanth

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.

arXiv:quant-ph/0402128•Feb 18, 2004•5 citations

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

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

On the Completeness of Quantum Computation Models

Pablo J. Arrighi, Gilles Dowek B

Abstract. The notion of computability is stable (i.e. independent of the choice of an indexing) over infinite-dimensional vector spaces pro-vided they have a finite “tensorial dimension”. Such vector spaces with a finite tensorial dimension permit to define an absolute notion of com-pleteness for quantum computation models and give a precise meaning to the Church-Turing thesis in the framework of quantum theory. 1

•Mar 20, 2010•9 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

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,597 citations
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.
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.
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.
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.
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.