This appears in http://mitworld.mit.edu/video/149/ at 1:28:28. Question: "How does your Principle of Computational Equivalence (PCE) explain the separation in complexity between a classical cellular automaton (CA) and a quantum CA?" Wolfram: "OK, so... that's a complicated question... So, one question is: if you take quantum mechanics as we currently know it, and you say, okay... let's use quantum mechanics... let's just assume that we can make measurements infinitely quickly and that the standard formalism of quantum mechanics sort of is an exact description of the actual world, not some kind of an idealization of the world (as we know that it is, because we know that in fact when we make measurements... that we have to, for example, take one... some degree of freedom and amplify it to an almost an infinite number of degrees of freedom, and things like that... but let's assume we don't worry about that... let's take the idealization that it's just... you know... that, as the formalism suggests that we just... do a measurement and it happens...,) okay, so then the question is what... how does... how does what I am talking about relate to the computation that you can get done in the classical case vs. the quantum case. So..., first thing I should say is that, ultimately, the claim of my PCE is that in our universe it is in fact not possible to do things that are more sophisticated than what a classical CA, for example, can do. So, if it turned out that quantum CAs (or quantum computers of some kind) can do more sophisticated things than any of these classical CAs then this PCE of mine would just be wrong." And he smiles (roguish smile) and waits, to see if the answer thus far is sinking in. At this time the question is refined: Question: "By more sophisticated do you mean with a better complexity then, or do you mean in a univers..." Wolfram: "Okay, so to be more specific... I mean... so one question is: can it do more than a universal Turing machine, can it break Church's thesis? Another is: can it do... you know... an NP-complete computation in polynomial time? Okay... so, on the second issue: I am not so sure! On the first issue, I'm really... you know... I'm, I'm... I certainly will claim very strongly... I mean... I certainly believe that in our actual universe one can't do computations that are more sophisticated than one can get done by a standard classical Turing machine. Now, having said that there's already then a sort of technical question which is: if you allow quantum mechanics... if you allow sort of standard idealizations of quantum mechanics, which involve complex amplitudes that have an arbitrary number of bits in them, and things like that, even within the formalism... can you do computations that are more sophisticated than you can do in a standard classical universal Turing machine? I think that people generally feel that probably you can't. But, to show that... would be interesting. For example, the following is true: if you say that you do computations just with polynomials, that the only operations that you can have are: writing down a polynomial, and solving a polynomial. Or, solving a polynomial inequality or something. Well... then, it turns out that there is a result from the 1930s, I guess, that it is at least... it's... that... if you're only working with polynomials and solving polynomials and so on... then... it's a decidable problem; then, every question you ask is decidable... it was Tarski's result [...] so, within... if the kind of primitives you have in your theory would be only polynomial primitives then it is the case that even using these arbitrary precision amplitudes in quantum mechanics you couldn't compute something more than what we can classically compute... but as soon as you allow transcendental functions for example... that is no longer the case, because for example even with trigonometric functions you can easily encode an arbitrary diophantine equation in your... sort of, continuous system, so... if you allow such functions then you can immediately do computations that cannot be done by a classical Turing machine and if there was a way to get quantum mechanics to make use of those transcendental functions, which certainly seems not impossible that could be... then it would imply that quantum mechanics in its usual idealization would be capable of doing computations beyond the Church's thesis limit. So... Then you can ask questions about the NP completeness level of things: I'm less certain about that... my own guess... speculation... is that in fact if you try... eventually, unravel the idealizations that are made in sort of particle [physics] and quantum mechanics that you will find that in fact you don't succeed in doing things that are sort of more sophisticated than you could do with a classical Turing machine type system... but I don't know that for sure!" That's the end of the answer regarding the relationship between PCE, and the classical vs. quantum models of computation. The answer then goes a bit further, explaining how NKS is interesting and important even without any reference to quantum models of computation, and this last part of Wolfram's answer briefly discusses a problem involving a lower bound on a space of Turing machines. Note: one can also go to the video here: http://mitworld.mit.edu/play/147/