Quantum Computing Since Democritus Lecture 9: Quantum
Many students indicated that this was their favorite lecture in the whole course — the one that finally made them feel at home in QuantumLand. Come read about why quantum mechanics, far from being a mysterious, arbitrary structure foisted on us by experiment, is something that mathematicians could easily have discovered without leaving their armchairs. (They didn’t? Minor detail…)
Marvel, too, at the beautiful … well anyway, at the displayed equations courtesy of mimeTeX, an eminently-useful CGI script that I downloaded and got working all by myself. (Who says complexity theorists can’t set up a CGI script? Boo-yah!)
If you’ve been thinking about following the course but haven’t, this lecture would be a perfect place to start — it doesn’t use any of the earlier lectures as prerequisites.
Follow
Comment #1 January 14th, 2007 at 4:54 pm
The “square root” argument for complex amplitudes is really convincing only if you insist on allowing all orthogonal transformations rather than special orthogonal transformations only (those of determinant 1).
So, is there an “intuitively obvious” reason why “mirror reversals” must be allowed in quantum mechanics ?
Comment #2 January 14th, 2007 at 5:13 pm
A thought occurred to me the other day after reading your survey on the implications of P != NP in physics. It appears to me that all the “limitation” thereoms/principles/laws etc. in physics are all fundamentally computer science or information theory based. Off the top of my head:
Special relativity gives non-superluminal travel, but we have to be careful about what is excluded by it. For example, wave phase velocity and the inherent quantum non-locality are excused from detention. It would appear that we can concretely state that no information can be transferred faster than the speed of light
2nd Law of Thermo. The Bayesians have already been trying to unite physical entropy and information entropy.
Uncertainty principle. Again, a statement about what information cannot be extracted from a system, conjugate pairs amongst them.
And adding your little survey, P != NP gives us a load of stuff on time loops, etc.
I wonder if this is crackpot thinking (it probably scores high on the Baez index), or whether it’s already been thought of and discarded, or even a well-known connection that just not taught to physics undergrads?
Comment #3 January 14th, 2007 at 5:37 pm
So, is there an “intuitively obvious” reason why “mirror reversals” must be allowed in quantum mechanics ?
Pascal: Excellent question! I thought about that as well.
One argument is that, even if we did disallow mirror reversals (i.e., restricted ourselves to the special orthogonal transformations only), we could still implement mirror reversals anyway by just going one dimension higher. And it seems inelegant to have an orthogonal transformation that we can implement in N dimensions, but only by going into the (N+1)st dimension.
Comment #4 January 14th, 2007 at 5:41 pm
Gen: If the idea that all the known “fundamental limitations” in physics somehow relate to information theory is crackpottery, then count me as a crackpot too!
Comment #5 January 14th, 2007 at 5:43 pm
Pascal Koiran:
that annoyed me too, but the Lucien Hardy paper Scott linked to requires that there be a transformation from |0) to |1). Uh…for a moment it made be feel better, but now it doesn’t. But maybe the paper will motivate this requirement.
Another thing that annoyed me was the presentation of Gleason’s theorem. In motivating the L2 norm, you assumed it in one place and got it out in another. Or, perhaps, you assumed part of it, and derived the whole thing. But Scott seemed to try to hide the assumption.
The argument about Haar measure seemed most convincing to me. (Of course, this subsumes the symmetry assumption that required reflections!)
I would like to say that from the point of view of the Mordell conjecture, what’s special about p=1,2 in Fermat’s last theorem is exactly the large symmetry group that made them special in this lecture, but I’m not sure how legitimate this claim is.
Comment #6 January 14th, 2007 at 8:25 pm
Nice lecture Scott.
Interesting as always.
As a layman, I can’t contribute to the discussion going on here, but I can say this: someone hire this man! He’s a great explainer.
Comment #7 January 14th, 2007 at 9:00 pm
Scott: but is that it then? Everyone thinks it, but no progress on actually groping towards a formal definition of things? For one, I’d like to know what the hell I mean when I say “limitation” theorem…
One route I’ve been thinking about is based on looking more closely at the interaction between “observer” and “system”. Given any set of physical laws, the observer-system interaction must also be governed by them. Maybe there some sort of procedure (a program, formally) that takes a set of laws, and gives constructable observables.
The uses of category theory in mathematical foundations has this sort of flavour: we call the natural numbers initial objects of a particular functor on _some_ category, neatly sidestepping the question of what category. Maybe some of the information theoretic “principles” would drop out merely as a necessary part of the way that the laws of physics would be observed.
Comment #8 January 14th, 2007 at 9:14 pm
Gen: I have trouble getting excited by any problem of the form, “Find a formal definition (or framework) for such-and-such.” That’s why I get turned off by category theory, and by the second halves of John Baez’s This Week’s Finds columns.
For me the question is always: why do you want a formal definition? What concrete question do you want to use your formalism to answer? Often there are many ways to formalize the same intuitive concept (for example, “limitation theorem in physics”), so you can’t even get started until you have some idea of what your goal is.
Comment #9 January 14th, 2007 at 10:23 pm
“So, cancellation between positive and negative amplitudes can be seen as the source of all “quantum weirdness” ”
isn’t the main “quantum weirdness” that n qubits need a 2^n complex numbers description ? And that is not due to cancellation or is it ?
Comment #10 January 14th, 2007 at 11:12 pm
Roland: Good question! Here’s how I think about it: to describe a classical probability distribution over n-bit strings, you also need 2n parameters. But no one worries too much about that in the classical case. Why not? Because the 2n classical computational paths will never interfere with each other — and therefore, you can always imagine (if you want) that only one of the paths is “really” there. In the quantum case, that option is no longer open to you.
In short, interference and exponentiality are just two different sides of the same elephant!
Comment #11 January 15th, 2007 at 2:12 am
Scott, this is very, very helpful and cool. Thanks for peeling away the mystification & crusty old experiments and motivating (not just describing) QM from a mathematical perspective.
Re God’s preference for p = 2 over p = 1: stochastic but non-invertible matrices can destroy information, whereas unitary matrices are automatically invertible, so it seems like with p = 2 we get the full freedom of movement in transforming systems while still keeping a ‘paper trail’. (I admit that conservation of information seems less intuitively necessary than conservation of mass or energy to me, and as a result in thinking about physics I want to somehow understand info as a ‘substance’… but that’s just me.)
I’m still trying to figure whether the Haar property you mentioned is also some kind of intuitive conservation-of-info law.
Comment #12 January 15th, 2007 at 2:35 am
Thanks, Andy!
it seems like with p = 2 we get the full freedom of movement in transforming systems while still keeping a ‘paper trail’.
You should definitely check out Lucien Hardy’s paper — you just anticipated one of his main ideas.
I’m still trying to figure whether the Haar property you mentioned is also some kind of intuitive conservation-of-info law.
If you find an intuitive meaning for the Haar property, let me know! I still don’t have one, except that it makes some calculations easier.
Comment #13 January 15th, 2007 at 10:10 am
You used operating systems to explain quantum mechanics? Not cool.
I liked how you gave a paradoxical twist to “Experiments are necessary”. Perhaps they are necessary because armchair mathematicians use Occam’s razor. Nature doesn’t.
Comment #14 January 15th, 2007 at 10:25 am
Or because armchair mathematicians don’t use Occam’s Razor as well as nature does…
Comment #15 January 15th, 2007 at 2:48 pm
An interesting reference for the further reading section is Mermin, N. David. 2003. From Cbits to Qbits: Teaching computer scientists quantum mechanics, Am. J. Phys. 71, 23 (http://dx.doi.org/10.1119/1.1522741)
He cites a “disgruntled quantum optician”, saying: “Where’s h-bar? Where is h-bar?!”
Comment #16 January 15th, 2007 at 2:54 pm
Scott, your lecture was very good (IMHO). It might interest your students to know, that its approach “quantum mechanics is about lists of complex numbers” is reasonably well-aligned with the way we are starting to teach quantum mechanics to engineering students (syllabus here).
To boil it down to a catechism in the style of William of Occam:
(1) Quantum mechanics is all about lists of complex numbers.
(2) However, it is very bad form to ever look at these lists.
(3) Which is fortunate, because in most practical cases the lists are exponentially long (so long, that we can’t even store them).
(4) Therefore, the single most important aspect of these lists is that they can be algorithmically compressed with good fidelity.
(5) The single most important tool in this compression, and therefore the single most useful fundamental law of nature, is informatic invariance (as indexed under “theorem: unitary freedom in the operator-sum representation” in Nielsen and Chuang).
(6) The defining competency of quantum system engineering is the ability to integrate these physical and mathematical principles in the model-based design and HWIL simulation of large-dimension quantum systems.
(7) The defining mathematical challenge of quantum system engineering is model order reduction on large-dimension complex state spaces, in service of reliable model-based design, and efficient HWIL simulation.
Deliberately, the above quantum principles are a bit “over the top” in their exclusive focus on engineering concerns, but isn’t this true of any catechism?
With regard to the broader implications of this point of view, a very stimulating resource for information theory students is a recent special issue of Critical Review which focuses on “The nature of belief systems” (vol 18, no. 1–3, see e.g. P. E. Converse, p. 300):
“The world is large, information about it seems infinite, and even the most capacious minds must stringently limit their acquisition of information to amtters that interest them either in the abstract or, more centrally, that they find otherwise useful to have on hand. Beyond this point, information costs are not worth paying, and ignorance is rational. … the big question this leaves is whether we might expect some secular trend of improvement … the obvious hope has long resided in the advance of education in the population, but one can imagine other developments as well.”
For quantum system engineers, “imagine other developments” surely includes model-based quantum system design, which we regard as an enterprise not only for creating new quantum technologies, but also, for building healthy and strategically important social and economic alliances.
To sum up, the emerging modern analog of William of Occam’s medieval scholasticism might be called quantum informatic scholasticism: the principle that information theory in general, and large-scale quantum simulations in particular, can and should help address the urgent informatic challenges of modern society.
Comment #17 January 15th, 2007 at 5:28 pm
Scott,
how do you understand Wick rotation, which basically moves you from quantum theory to (classical) thermodynamics and back ?
Comment #18 January 15th, 2007 at 5:32 pm
Hi, will you be talking about category theory, about all those toposes, or how do they call them, in your lectures?
Comment #19 January 15th, 2007 at 7:18 pm
how do you understand Wick rotation, which basically moves you from quantum theory to (classical) thermodynamics and back ?
Wick rotation always seemed to me like a mathematical trick (akin to many other tricks for using complex numbers to simplify calculations involving real numbers). But if someone wants to defend the view that it has a more fundamental meaning, I’d be extremely interested to hear from them.
Comment #20 January 15th, 2007 at 7:20 pm
Hi, will you be talking about category theory, about all those toposes, or how do they call them, in your lectures?
No.
Comment #21 January 15th, 2007 at 7:40 pm
> akin to many other tricks for using complex numbers to simplify calculations involving real numbers
but in this case it seems to be the other way around;
you rotate from complex amplitudes to real Boltzmann probabilities to (define and) calculate expectation values…
Comment #22 January 15th, 2007 at 7:53 pm
> if someone wants to defend the view that it has a more fundamental meaning
I don’t know if Stephen Hawking reads your blog, but as far as I know he thinks that the Euclidean sector is more ‘fundamental’ than the Lorentz sector.
Comment #23 January 15th, 2007 at 8:14 pm
but in this case it seems to be the other way around;
you rotate from complex amplitudes to real Boltzmann probabilities to (define and) calculate expectation values…
OK, point taken — I was thinking about a different use of Wick rotation, to transform a real Minkowski space into a complex Euclidean one.
I’ve never understood the use of Wick rotation that you mention, but I’ve asked many physicists about it over the years. My question always boiled down to some variant of the following: if you really can translate any quantum problem into a classical thermodynamics problem, then why couldn’t you exploit that, for example, to simulate Shor’s algorithm in P? The answer I usually got was that Wick rotation only works in certain special cases that are not that interesting for quantum computing — which confirmed my view of it as a mathematical trick.
Again, if someone who actually knows this stuff wants to clarify, it would be deeply appreciated.
I don’t know if Stephen Hawking reads your blog, but as far as I know he thinks that the Euclidean sector is more ‘fundamental’ than the Lorentz sector.
Yes, he does think something like that, but apparently it’s a very controversial view — if he were being deliberately provocative, it wouldn’t be the only time.
Comment #24 January 15th, 2007 at 8:54 pm
> if you really can translate any quantum problem into a classical thermodynamics problem, then why couldn’t you exploit that
Wick rotation of a simple 1-particle Schroedinger equ. should give you a diffusion equation, i.e. a system of N classical particles, with N -> infty.
Perhaps this is the reason why one cannot exploit this.
Just a naive hunch …
Comment #25 January 15th, 2007 at 10:53 pm
John, you’ve told us a lot about your philosophy of QSE; can you point to a projected technological development that will be QSE’s proving-grounds for the larger world? Is QSE ‘about’ quantum computing, nanotechnology, or other more well-known projects?
Comment #26 January 16th, 2007 at 12:13 am
To take up Scott and Wolfgang’s conversation of why isn’t Schrodinger’s Equation more often solved as an analytic continuation of the diffusion equation:
1) The main reason is that analytic continuation is an ill-posed problem in the numerical analysis sense—the accuracy necessary in the diffusion equation solution grows superpolynomially with the accuracy desired for the Schrodinger Equation solution. Intuitively, this is because all the higher frequency oscillatory components in a solution to the Schrodinger equation will become extremely rapidly decaying exponentials in a diffusion equation solution. To see this most starkly, consider an a component to your Schrodinger equation solution whose frequency tends to infinity. For the sake of making the starkest possible example, say furthermore this component has a very large magnitude. Indeed, it may dominate the Schrodinger equation solution. Nevertheless the decay rate of its analytically continued counterpart in the diffusion equation tends to infinity, and so this vital component is almost invisible as you solve the diffusion equation.
Of course, very often in practical situations one does have an energy bound / bandwidth limit. Nevertheless, analytic continuation is still numerically dicey generically. If you really care about what’s the optimal classical algorithm for analytic continuation from a given set of sample points and a promised bandwidth limit, look at the works of Russian numerical analyst A.M. Fedotov.
The one case where this ill-posedness doesn’t matter terribly is if you only care about ground state properties of your quantum system (as is often the case in, say, zero-temperature phase transitions). Then, the slowest decaying exponential in the diffusion equation solution is all you’ll care about anyway.
(This may be the origin of Hawking’s statement that he thinks “Euclidean Quantum Gravity”—i.e., quantum gravity with imaginary-time aka diffusion-like aka Wiener path integrals—is more fundamental than “Lorentzian Quantum Gravity”—i.e., quantum gravity with real-time aka Schrodinger-like aka Feynman path integrals. It may simply be that the things Hawking most wants to calculate can be treated with Wiener path integrals. Additionally, Wiener integrals *actually exist in an straightforward and rigorous mathematical sense* unlike Feynman integrals, which many people would say only exist formally as an analytic continuation of the Wiener integrals.)
2) The mapping between quantum mechanics / Schrodinger evolution and classical statistical mechanics / diffusion is not always possible. Quantum mechanics has plenty of cases (e.g., Heisenberg models, where the Berry phases of the SU(2) spins are quite important) where the appropriate analytic continuation doesn’t lead to nice real-valued decaying exponentials but still complex exponentials. (See, for example, the Heisenberg Model chapters in Sachdev’s book Quantum Phase Transitions.)
All the best with the job hunt, Scott.
Comment #27 January 16th, 2007 at 1:24 am
For Gen Zhang and Scott: For a bit more on the information theoretic basis of “limitation principles”, see the discussions here and especially the papers of Ariel Caticha.
Comment #28 January 16th, 2007 at 2:12 am
# Andy Says: Can you point to a projected technological development that will be QSE’s proving-grounds for the larger world?
Our own group’s near-term QSE goal is to realistically predict quantum spin diffusion in the ultra-strong magnetic gradients that are characteristic of magnetic resonance force microscopy, for purposes of atomic resolution biomicroscopy. In practice, this means simulating several hundred interacting quantum spins (preferably several thousand).
It turns out that our quantum biomicroscopy goals share common informatic ground with many other scientific disciplines that are becoming steadily more ambitious in the pursuit of large-scale quantum simulation capability. These increasingly ambitious quantum disciplines include (to name a few) quantum chemistry, condensed matter physics, gravity-wave observation, VLSI design, lattice gauge theory, and spintronics.
There is an emerging sense (IMHO) that all of these disciplines are “climbing the same mountain”, that is, we are all practicing quantum model order reduction, on large-dimension systems, with aggressive computer help, in pursuit of both fundamental scientific knowledge and practical engineering applications.
It is our sense that the mathematical structure of this mountain can be appreciated equally from geometric, algebraic, informatic, and cryptographic points of view (we like the geometric view best, but this may be because it is the one we understand least).
As far as engineering is concerned, the practical implications are greatest if all of the preceding scientific and engineering disciplines make very substantial progress together. We can then begin to envision a world with thousands of desktop-scale atomic-resolution quantum biomicroscopes, which are systematically observing all biological molecules, of all organisms, in situ in cryogenically frozen specimens, then computing the functional properties of these molecules not ab initio, but using the observed biostructures as starting points for quantum functional simulations.
Needless to say, this project’s demand for computing power and information storage would be effectively unbounded: that’s where the quantum condensed matter physics, materials science, and spintronic engineering comes in.
These are great dreams, and they are fun and challenging to work on, but we’re a very long way from achieving them. Our QSE Group thinks it’s becoming evident likely uuuhhh … there’s-a-chance-at-least plausible that there are no quantum or informatic showstoppers, though. 🙂
We’ve taught an informal seminar on this topic the past two years—the “UW Spinometers Seminar.” Only now are we beginning to feel that we can envision a reasonable science and engineering roadmap for the complete program. So if you’re in Seattle, please stop by and contribute.
Comment #29 January 16th, 2007 at 3:45 am
thanks! that is ambitious.
Comment #30 January 16th, 2007 at 3:46 am
Thanks so much, Bill! That was amazingly clear.
Comment #31 January 16th, 2007 at 4:03 am
BTW, in bringing up Fermat’s Last Theorem, has the thought crossed your mind that there might a (more) elementary proof hidden somewhere in the connection with the QM-motivated consideration of p-norms? From the Wikipedia entry:
… The final, correct proof uses the standard constructions of modern algebraic geometry, which involve the category of schemes.
Because Wiles’s proof relies mainly on techniques developed in the twentieth century, most mathematicians agree that Wiles’s proof is not the same as Fermat’s proof. Some mathematicians believe that Fermat did not actually prove the theorem or that his proof was flawed like other early attempts. However, there are other mathematicians who believe that Fermat really did prove the theorem with seventeenth-century techniques. Although Andrew Wiles has already proved that the theorem is true, some mathematicians who believe that Fermat did prove the theorem continue to search for an elementary proof.
(Actually, I thought hardly anybody believed Fermat actually had a proof, but never mind…)
Comment #32 January 16th, 2007 at 4:49 am
Regarding “Fermat’s original proof”: no, he didn’t have one. There’s a smoking gun, which almost always gets ignored in this debate: after writing his famous margin note, Fermat repeatedly talked about the n=3 and n=4 case, but never again about the general case.
(Layperson: “You mean he thought he had a proof, but he didn’t?”
Mathematician: “Dude.”)
No doubt there are simpler proofs than Wiles found, but were there a dramatically simpler proof, it would’ve been found already.
Comment #33 January 16th, 2007 at 2:39 pm
As an example of how easily analytic continuation can get you into trouble, here is a story problem.
Physicist Albert Optimist is trying to calculate Cosh[x] (in Mathematica notation). Upon discovering an integral expressions for Cosh[x], and evaluating it by the method of stationary phase, he obtains the leading expression Cosh[x] ∼Exp[x]/2, and he verifies that his expression is highly accurate for x = 3/2 Pi, having a relative error of only 0.00008.
Hugely pleased, Albert publishes a paper asserting, by analytic continuation, that Cosh[I 3/2 Pi]∼-I/2 to high accuracy. The correct answer is, of course, zero.
Where did Albert go wrong in his analytic continuation?
Comment #34 January 16th, 2007 at 3:25 pm
# Andy Says: Thanks! [The goals of quantum science and engineering] are ambitious.
Looking ahead to Scott’s next post, you might justly have criticized our engineering group for having a faith-based belief that science and technology can be deployed in service of “freedom, security, education, and enterprise ” (per the syllabus).
You might justly have asked, what guarantees can you offer that quantum science and technology will not be deployed in service of “oppression, terror, mind-control, and hegemony”?
Our QSE Group has an answer to this, but it’s a highly imperfect answer. Namely, we have deliberately embraced open models of research, system engineering, and equity, in order to expose ourselves us to the Madisonian checks and balances of public scrutiny, a free-market economy, and democratic elections.
These checks and balances admittedly can be only a partial remedy to faith-based belief in our own rationality and morality. 🙂
Comment #35 January 16th, 2007 at 11:02 pm
Thanks so much for this lecture. This may be the first time ever, when I steal a teaching idea, that I do it with attribution.
Bill’s comment was helpful too.
Comment #36 January 17th, 2007 at 3:50 am
Hi Scott,
I hopped over here from the general abstract nonsense cafe, and really (complexly?) enjoyed this lecture on the origin of quantum mechanics. If you’re up for a light read on how to get quantum mechanics from information theory and complex probabilities, I wrote up this simple minded paper on it a few months ago:
http://arxiv.org/abs/physics/0605068
It exactly parallels the derivation of the probability distribution of a canonical ensemble, with a twist.
Best,
Garrett
Comment #37 January 18th, 2007 at 12:17 am
Garrett,
Compare your paper—especially its general outlook—with Entropic Dynamics (gr-qc/0109068), and the more recent gr-qc/0508108, plus other papers by the same author on quantum theory, statistical mechanics, and Bayesian inference.
Comment #38 January 18th, 2007 at 1:53 am
A paper perhaps worth commenting on in the context of this post: Complex numbers and symmetries in quantum mechanics, and a nonlinear superposition principle for Wigner functions
From the abstract: … It is concluded that the use of complex numbers in quantum mechanics can be regarded as a computational device to simplify calculations, as in all other applications of mathematics to physical phenomena.
Comment #39 January 18th, 2007 at 12:02 pm
Chris W.: Thanks for the paper links… the work is interesting, but the pessimist in me thinks it too good to be that easy.
Scott: What I really want is one coherent theory that accounts for how information about a physical system may be extracted given the physical laws that govern it. Then we can concentrate on the non-information parts of physics (maybe such as the electron mass, etc.); I guess because I’m a physicist primarily, I want to be able to cleanly say “this is necessary because of maths and logical thinking” and so get to the “real” physics. A man can dream, can’t he? :p