baez@x.ucr.edu (john baez) (04/15/90)
In article <54872@bbn.COM> aboulanger@bbn.com writes: >In article <965p02gf9cNw01@amdahl.uts.amdahl.com> kp@uts.amdahl.com (Ken Presting) writes: > Penrose does cite David Deutch, "Quantum thoery, the Church-Turing > pinciple, and the universal quantum computer", Proc. Roy. Soc. (1985) > A400, 97-117. Apparently, a quantum device can exhibit some of the > *speed* properties of a non-deterministic TM. As far as I know, there > is no (well-founded) suggestion that non-recursive functions can be > computed by these devices. Computing NP-complete things in polynomial time would be interesting and mildly believable, though I'd be inclined to believe that the NP nature would simply be pushed off into some other aspect. Someone at Princeton showed you could solve some NP complete problems fast using "mechanical computers" (imaginary machines made of gears and such), but I am inclined to believe that in this case the machines must be tooled with accuracy rapidly growing as a function of the size of the problem. I very much doubt that any real-world system can *repeatably* compute a non-recursive function. Of course, if quantum mechanics is truly random, alternately measuring an electron's spin along two orthogonal axes should produce a non-recursive sequence of bits. But this isn't a repeatable "calculation" in my opinion. Try out: John Baez, Recursivity in Quantum Mechanics, Trans. Amer. Math. Soc., {\bf 280} (1983), 339 - 350. Pour-El, Marian B. (Marian Boykan), 1928- Computability in analysis and physics / Marian B. Pour -El, J. Ian Richards. Berlin ; New York : Springer Verlag, c1989. > This is very interesting. Discreteness in the spectrum of energy states > is not by itself sufficient - there is no problem in having a denumerable > infinity of discrete states within a finite interval. To be more precise, quantum systems in bounded regions of space can be expected to have Hamiltonians with pure point spectrum, so their motion will be "almost periodic" in the technical sense, not chaotic. > If a real system can depend in a macroscopically observable way on > how close it gets to (eg) an ionization energy, then chaotic behavior > might be observable in QM. How are the mathematical examples constructed? That's right, chaos might appear near ionization (continuous spectrum), but systems in a "box" don't really have continuous spectrum. There could be some residual vestiges of chaos lurking about though if one could find a good mathematical way of identifying them. One typical bogus way of getting continuous spectrum for a quantum system in a bounded region is to take Schroedinger's equation on R^n and apply a map from R^n onto an open ball of finite radius, say, to get a differential equation on the open ball with continuous spectrum. One might also be able to do it by using potentials that are sufficiently nastily unbounded below. >The issue of chaos in the correpondence limits of quantum systems is a >hot topic. For those interested in the issue of quantum chaos, I >strongly suggest: > >"Classical Mechanics, Quantum Mechanics, and the Arrow of Time" >T. A. Heppenheimer, Mosiac, Volume 20, No 2, Summer 1989, 2-11 Arrow of time, oh-oh! :-)