# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Quantum theory, the Church-Turing principle and the universal quantum computer. (English) Zbl 0900.81019
A novel, “physical”, version of Church’s thesis is proposed: Any finite realizable physical system can be simulated by a universal finite means computing machine. It is claimed that the thesis is false in classical physics due to the continuous nature of the states available to finite realizable classical systems. A construction is offered for the appropriate finite means quantum computer, and it is claimed that such a “machine” does obey the “physical” version of a Church thesis given above. The universal quantum computer differs from the classical primarily in allowing a class of programs which evolve computational basis states into linear superpositions of one another. The problem of the irreducible interaction of a finite system with an external environment is discussed in this computational context. Next it is argued that “quantum theory is a theory of parallel interfering universes”, and that “there are circumstances under which different computations performed in different universes can be combined in $Q$ [ the universal quantum computer ] giving it a limited capacity for parallel processing”. The “quantum parallelism” allegedly shows up in the ability in some cases to do a better job of minimizing some minimum or maximum computation time than could be obtained by a stricly serial quantum computation. It is claimed that these results can be used to give an experimental test of the Everett (“many-universe”) interpretation of quantum mechanics against the other interpretations, contrary to the usual belief that all the interpretations are experimentally indistinguishable. It is claimed that only the Everett interpretation offers an answer to the question which arises when computation is speeded up by “parallel processing”: “where did the parallel computations take place?”. Next the discussion turns to the use of quantum computation to determine “complexity” of a state. It is argued that counterintuitive results of a definition of C. H. Bennett become more acceptable in the quantum context. Other relations to such problems as “why quantum mechanics is the case” and the direction of time and growth of complexity are briefly touched upon.

##### MSC:
 81P10 Logical foundations of quantum mechanics; quantum logic 03D99 Computability; recursion theory 68Q99 Theory of computing 03G12 Quantum logic