The original questions were posted here.

From Dr. Seth Lloyd’s answers it is clear that:
1) he is assuming the Deutsch quantum computing model, which is Turing reducible and
2) he is assuming that quantum particles encode a finite amount of information, so that they are completely discrete in every possible sense, including: space/time, mass, energy, momentum, and any other possible physical value.

1 and 2 are, by the way,  standard views in both fields, quantum computing (defined by David Deutsch) and quantum mechanics (as defined by several authors). From 1 and 2 it can be deduced that Seth Lloyd indirectly implies that the universe is Turing computable (since the only difference between a quantum computer and a Turing machine -disregarding the usual fact about the infinite tape- is the run time, a fact borne out by his answers). Regarding 2, most quantum quantities and solutions to equations suggest that there are minimum values, namely the Planck time and the Planck length, a fact which assorts well with a discrete scenario. However the issue is commonly bypassed by physicists and by the theory itself. In other words, quantum mechanics seems to be consistent with both a continuum and a  discrete universe and does not offer final evidence or an ultimate theoretical conclusion one way or the other. In fact it is usual among physicists to think of  superposition as an entanglement in a space continuum, which would allow  a particle to be in an infinite number of  states simultaneously.

From 1 and 2 we can conclude that Church’s thesis–in both its weak and strong non-physical and physical versions, which we will discuss in a separate post– remains intact  even when Dr. Lloyd’s approach is closer to a physical basis (an accepted modern model of the universe) and of course the empirical data (which supports quantum mechanics itself). His chain of reasoning is basicaly as follows:

a&b->c:

a) the universe is completely describable by quantum mechanics
b)  standard quantum computing completely captures quantum mechanics
c) therefore the universe is a quantum computer.

He proved a relation between a and b, which probably puts the standard (or some standard) theory of quantum mechanics and the standard quantum computing model in an isomorphic relation with each other. Here “standard” means that some assumptions were made.

Here is a literal transcription of the answers to my questions given by Dr. Seth Lloyd:
—–
A: A quantum computer differs from a Turing machine in that its bits are quantum bits, and so can exist in a superposition. In addition, it can be instructed to put those bits in superpositions. These two features make a quantum computer apparently much more powerful than an ordinary Turing machine. What a quantum computer does is still Turing computable, but a typical quantum computation of T steps on N qubits requires O(2^N) bits on a classical Turing machine, and O(T 2^2N )logical operations. That is, it takes a Turing machine exponential amounts of time and space to simulate a quantum computer or quantum Turing machine. (Compare the definition of universality: a universal Turing machine can simulate any other Turing machine in polynomial time.)
So a quantum computer is apparently more powerful than a classical computer.
There is a perfectly good definition of a quantum Turing machine (basically, a Turing machine with qubits and extra instructions to put those qubits in superposition, as above). A universal quantum computer is a physical system that can be programmed (i.e., whose state can be prepared) to simulate any quantum Turing machine. The laws of physics support universal quantum computation in a straightforward way, which is why my colleagues and I can build quantum computers. So the universe is at least as powerful as a universal quantum computer. Conversely, a number of years ago I proved that quantum computers could simulate any quantum system precisely, including one such as the universe that abides by the standard model. Accordingly, the universe is no more computationally powerful than a quantum computer.

A: As long as a quantum particle encodes 3, 4, or M states, where M is a finite number, then the computational picture remains the same (this is also true classically). Now, it is a fact that a physical
system with finite energy confined to a finite volume of space has only a finite number of discrete states. So we are OK.
——-
“Now, it is a fact that a physical system with finite energy confined to a finite volume of space has only a finite number of discrete states.”—I wish the obviousness of this final remark were readily apparent to me.

Dr. Seth Lloyd’s work is very compelling, and I am engaged in a project inspired by ideas related to those he expounds here—mining the computational universe to uncover Lloyd’s programmer monkeys. But I find that his theory of the universe– which by the way I agree with, though it may sometimes seem otherwise– assumes no less than any other conception of the universe, which leaves space for continued thinking on evocative hypotheses, including Church’s, even as we attempt to hack the universe.

Lloyd’s thesis adds to the conception of the Universe as a Turing computer an important and remarkable claim (albeit one that depends on the conception of the quantum computer), viz.  that the Universe is not only Turing computable, but because it is constituted by quantum particles which behave according to quantum mechanics, it is a quantum computer computing its future state from its current one. The better we understand and master such theories, the better prepared we would be to hack the universe in order to perform the kind of computations -quantum computations- we would like to perform.

I would agree with Rudy Rucker too as to why Seth Lloyd assigns such an important role to quantum mechanics in this story. Rudy Rucker basically says that being a subscriber to quantum mechanics, Lloyd doesn’t give enough consideration to the possibility of deterministic computations. Lloyd writes, “Without the laws of quantum mechanics, the universe would still be featureless and bare.” However, though I am one among many (including Stephen Wolfram) who agree  that it is unlikely that the universe is a cellular automaton, simply because cellular automata are unable to reproduce quantum behavior from empirical data (but note that Petri and Wolfram himself attempt explanations of quantum processes based on nets), there’s  absolutely no need to rush headlong into quantum mechanics. If you look at computer simulations of physical systems, they don’t use quantum mechanics as a randomizer, and they seem to be able to produce enough variations to feed a computational universe. Non-deterministic randomness is not neccesary; pseudorandomness or unpredictable computation seem to be enough.

Last Modified : May 17th, 2008 Filed under : Complexity, Computability, Universality and Unsolvability, Conferences, Minds and Machines Navigate : Previous post / Next post