Quantum algorithmic information theory

The agenda of quantum algorithmic information theory, orde re ‘top-down,’ is the quantum halting amplitude, followed by the quantum algorithmic informatio n content, which in turn requires the theory of quantum computation. The fundamental atoms processed by qu antum computation are the quantum bits which are dealt with in quantum information theory. The theo ry f quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capable of arbitrary U(2) transformations. Basic to all these considerations is quan t m theory, which is most conveniently expressible in Hilbert space. 1 Information is physical, so is computation The reasoning in constructive mathematics [16, 19, 20] and recursion theo ry, at least insofar as their applicability to worldly things is concerned, makes implicit assumption s about the operationalizability of the entities of discourse. It is this postulated correspondence between practical nd theoretical objects, subsumed by the Church-Turing thesis, which confers power to the formal m ethods. Therefore, any finding in physics concerns the formal sciences; at least insofar as they claim to be applicab le in the physical universe. In this sense one might quite justifiably say that the Church-Turin g thesis is under permanent physical attack. 1 Conversely, any feature of the (constructive or non-constructive [16 , 19, 96]) formalism should correspond to some physically operationalizable [21] property. Hence, any theory of information, if applicable, has to deal with entities whi ch are operational [21, 64, 62, 60, 65]. In Bridgman’s words [22, p. V], “the meaning of one’s terms are to be found by an analysis of the oper ations which one performs in applying the term in concrete situations or in verifying the t ruth of statements or in finding the answers to questions.” In particular, the fundamental atom of information, the bit, must be r epresented by whatever physical theories are available and must be experimentally producible and manipulable by whatever physical operations are available. 1For an early discussion of this topic, see Davis [31, p. 11]: “ : : : how can we ever exclude the possibility of our presented, som e day (perhaps by some extraterrestrial visitors), with a (perhaps extremely complex) device or “oracle” that “ computes” a non computable function?” A main theme of Landauer’s work has been the connections betw een physics and computation; see, for example, his 1967 arti cle [62] “Wanted: a physically possible theory of physics,” or his more recent survey [64] “Information is physical.” See also Rosen [84]. As Deutsch puts it more recently [34, p. 101], “The reason why we find it possible to construct, say, electro nic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics ‘happen to’ permit the existence of physical models for the operations of arithmet ic such as addition, subtraction and multiplication. If they did not, these familiar operations would be non-computable functions. We might still knowof them and invoke them in mathematical proofs (which would presumably be called ‘non c structive’) but we could not perform them.”