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/9706006 · Physical Review Letters

Computable Functions, Quantum Measurements, and Quantum Dynamics

Michael A. Nielsen

Published Oct 13, 1997• 54 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.79.2915

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

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

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 and the Church–Turing Hypothesis

Christopher G. Timpson

Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.

Oxford University Press eBooks•Apr 25, 2013•0 citations

Implementability of observables, channels and instruments in quantum theory of measurements

Mikko Tukiainen

Measurements play an integral part in any scientific theory. Indeed, the observations revealing causal behaviour and symmetries in our world of experience lie at the heart of determining the truth or the falsity of scientific hypotheses. In this regard, quantum theory provides one of the most stringently tested and comprehensive description of the natural world. This thesis is an examination of the mathematical structures of quantum measurements with an emphasis on the measurement implementations of different operational devices: quantum observables, channels and instruments. The measurability of all the quantum properties a system bears is, in principle, guaranteed by quantum measurement theory. However, as physical processes, measurements are constrained by the laws of physics and it has been long known that certain conservation laws can inhibit the measurements of some of the quantum observables. In this work it is shown that such constraints stem from the fact that the measured observables inherit the symmetries of the measurement devices implementing them. A quantum measurement set-up can implement a multitude of operational devices as a function of the initial state of the apparatus. In other words, one can realize various maps – even incompatible ones – simply by controlling the apparatus’ state. Due its close resemblance with the classical analogue, this operation is often referred as quantum programming. In this thesis the capabilities and restrictions of quantum programming are explored using a measurement-theoretic approach. Moreover, quantitative methods are developed to address the mutual relations between the programming states of an arbitrary pair of observables or channels.

•Nov 25, 2017•1 citation

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 1, 1994•0 citations
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.
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.
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].
Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.
Measurements play an integral part in any scientific theory. Indeed, the observations revealing causal behaviour and symmetries in our world of experience lie at the heart of determining the truth or the falsity of scientific hypotheses. In this regard, quantum theory provides one of the most stringently tested and comprehensive description of the natural world. This thesis is an examination of the mathematical structures of quantum measurements with an emphasis on the measurement implementations of different operational devices: quantum observables, channels and instruments. The measurability of all the quantum properties a system bears is, in principle, guaranteed by quantum measurement theory. However, as physical processes, measurements are constrained by the laws of physics and it has been long known that certain conservation laws can inhibit the measurements of some of the quantum observables. In this work it is shown that such constraints stem from the fact that the measured observables inherit the symmetries of the measurement devices implementing them. A quantum measurement set-up can implement a multitude of operational devices as a function of the initial state of the apparatus. In other words, one can realize various maps – even incompatible ones – simply by controlling the apparatus’ state. Due its close resemblance with the classical analogue, this operation is often referred as quantum programming. In this thesis the capabilities and restrictions of quantum programming are explored using a measurement-theoretic approach. Moreover, quantitative methods are developed to address the mutual relations between the programming states of an arbitrary pair of observables or channels.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.