PHYS771 Quantum Computing Since Democritus
That, for better or worse, is the name of a course I’m teaching this semester at the University of Waterloo. I’m going to post all of the lecture notes online, so that you too can enjoy an e-learning cyber-experience in my virtual classroom, even if you live as far away as Toronto. I’ve already posted Lecture 1, “Atoms and the Void.” Coming up next: Lecture 2.
Follow
Comment #1 September 14th, 2006 at 8:37 am
Hey, it seems pretty good. I’m more distant than Toronto, but I’ll give a try.
Comment #2 September 14th, 2006 at 9:13 am
Excellent!
Comment #3 September 14th, 2006 at 9:18 am
A nice alternate formulation of the problem that Richard Cleve immediately solved is as follows:
Does there exist an open subset S of [0,1] with boundary B where the measure of B is greater than the measure of S?
Comment #4 September 14th, 2006 at 10:46 am
Nice lecture. If I remember correctly, another argument that Democritus had for atoms was that we can smell things from a distance. He interpreted this as a hint that microscopic pieces were breaking off and reaching our noses.
Comment #5 September 14th, 2006 at 10:55 am
He certainly had a nose for this sort of thing. (Har. Har. Har.)
Comment #6 September 14th, 2006 at 2:03 pm
I wasn’t expecting to a reference to the Continuum Hypothesis in the lecture.
Comment #7 September 14th, 2006 at 5:50 pm
You’re using _The Emperor’s New Mind_? Penrose’s IQ is probably triple mine, and his contributions are stunning (II love the Penrose tiling and quasicrystals), but I read TENM when it came out and was unsatisfied. That was a long time ago, so the details have faded, but my recollection is that his argument came down to the notion that there is something unphysical about consciousness that makes it a unique property of meat. Am I off base? Perhaps I need to reread it.
A variant on the puzzle: Cleve’s solution puts one rational number in each interval. What happens if you insist that each interval contain more than one rational number? Is the total length of the intervals still finite, and can it still be driven to zero?
Comment #8 September 14th, 2006 at 5:52 pm
I love it. Thank you so much for posting these notes, I look forward to more!
Comment #9 September 14th, 2006 at 6:30 pm
rdv – Each interval already contains countably many rational numbers.
Comment #10 September 14th, 2006 at 10:42 pm
Are you now officially a Professor? I like your argument about philosophers acting like vultures:) Recently (before reading this entry) I read similar expression about philosophers by Richard Feynman in the book “The Character of Physical Law”.
Comment #11 September 14th, 2006 at 11:44 pm
Sometime I would like to hear you meditate out loud on the question of what the atomism of space and time, as opposed to the atomism of matter in space and time, is supposed to mean. It seems to me that this is a key question; if spacetime at bottom is discrete, it manages to be that while sustaining an extraordinarily convincing illusion of continuity. Somehow I think there is a bit more to this than just “yeah, well, the Planck length is really, really small”.
I have in mind something like the idea that the notion of length is something we impose on a combinatorial discretium, as part of mapping it onto a manifold. There is huge arbitrariness in this—the “nodes” of the discretium are not really embedded in anything—so the manifold comes to seem more real than the discretium.*
I’d better stop now…
(* BTW, my use of this word has nothing to do with certain uses of it in discussions of the string theory landscape.)
Comment #12 September 15th, 2006 at 1:33 am
My immediate instinct with your harder puzzle question is ‘obviously not’, but there isn’t an obvious way to show that using diagonalization. I have a feeling it may be one of those AC absurdities, especially given that you’re giving it in the context of bitching about philosophical problems with the continuum.
Comment #13 September 15th, 2006 at 4:28 am
This is how far I got on the latter puzzle. I need to go to sleep now, but I’ll try to keep going tomorrow.
Suppose we have a digraph with uncountably-many nodes, such that each node has only countably-many direct successors, and given any pair of nodes, at least one points to the other.
We can draw some more arrows from each node X to all of the nodes Y which can be reached from X in finitely-many steps.
Clearly, the new graph still satisfies our requirement that there only be countably-many direct successors, but now there are no indirect successors.
Now for any x, we let L(x) be the set of nodes y such that x and y both point to each other. L(x) is a subset of the set of
nodes which x points to, so it is countable. Now for any y in L(x), L(y)=L(x), because there are no indirect successors. So now we can partition our graph into these L-sets, generating yet another graph. This new graph still satisfies all of our original criteria, and has the additional property that no two nodes point to each other.
So we can reduce the problem to the case where no two nodes both point to each other and there are no indirect successors, i.e. this is a total-order relation on an uncountable set. So we just need to figure out if it is possible to totally-order an uncountable set such that each number is greater than only countably-many numbers.
Comment #14 September 15th, 2006 at 6:00 am
Nagesh:
Are you now officially a Professor?
No.
Comment #15 September 15th, 2006 at 6:04 am
rdv: Yes, we’ll be using a “textbook” whose central argument is (in my opinion) flat-out wrong! I chose The Emperor’s New Mind not because I agree with it, but because it’s a landmark of science writing as well as an excellent resource for many of the math and physics topics we’ll be discussing.
Comment #16 September 15th, 2006 at 6:07 am
Also, because Penrose doesn’t harp too much on his wrong ideas in that book — as he would later do, disastrously, in Shadows of the Mind (before brilliantly recovering with The Road to Reality).
Comment #17 September 15th, 2006 at 6:12 am
So we just need to figure out if it is possible to totally-order an uncountable set such that each number is greater than only countably-many numbers.
Hmm, good question! 🙂 (When I post the next lecture, you’ll see just how deep a question it really is…)
Comment #18 September 15th, 2006 at 6:25 am
Another good example of a philosopher scouting territory for math, science, and engineering is Leibniz’ Moral Calculus.
The Moral Calculus was a dismal failure the first time around, but aren’t we now beginning to understand better the conjoined roots—in complexity theory, information theory, cognitive science, and evolutionary biology—of that initial failure?
Leibniz: There are two famous labyrinths where our reason very often goes astray. One concerns the great question of the free and the necessary, above all in the production and the origin of Evil. The other consists in the discussion of continuity, and of the indivisibles which appear to be the elements thereof, and where the consideration of the infinite must enter in.
Scott, your first lecture did a good job of covering the second point. You might remind your students that many famous mathematicians have taken an equal interest in the first point, and that modern complexity theory (game theory, evolutionary theory, information theory, etc.) is casting considerable new light on these issues.
Then refer them to the Kochen-Specker-Conway Theorems!
Comment #19 September 15th, 2006 at 9:28 am
Wow.
Comment #20 September 15th, 2006 at 5:49 pm
As usual, you have inspired me to think about the post-Eighteenth century distinction between science and philosophy.
It is interesting that the best candidate for inventor of quantum computation, Feynman, was such a critic of philosophy.
We normally think that the more that we know, the more we can do. If we know how to milk a cow, then there is something we can do that we otherwise couldn’t, namely that we can milk a cow. Feynman liked knowing things, and implicitly in how the man lived his life (I worked on the finding aids at the AIP for Feynman’s interviews a few years years ago) he is seen as a person who valued DOING things (picking locks, for example). He lived in a world as a professional scientist in which there were all kinds of things that no one knew yet (the time when, as Dirac said, “second-rate men could do first-rate work”), and discovering those things let him be part of the performance of spectacular feats (the defeat of Japan comes to mind).
Quantum computation seems to require the programmer to approach the system believing that if he knows certain determinate values of the system, then there are fewer things that he can do — there are certain algorithms that he cannot use. While there may be some other algorithm that could give him the power he wants — (but he can’t prove that it doesn’t exist) — his knowledge of the state of the system (if there were to be one) precludes use of the quantum algorithms.
Now, any good philosopher will certainly note that I have conflated our intuition about knowing-how (to milk a cow) and knowing that (a particle prepared in a certain way is in a certain determinate state before it is measured). I did this deliberately. I suspect that part of the reason that it seems so odd that ignorance leads to ability (and that, for the pragmatic quantum scientist, ignorance is something we need to reason about in designing algorithms) is this conflation, which was seen by Gilbert Ryle back in the 50’s in his _Concept of Mind_, as responsible for a lot of other philosophical confusions.
Comment #21 September 15th, 2006 at 6:16 pm
It is interesting that the best candidate for inventor of quantum computation, Feynman, was such a critic of philosophy.
I think he was a critic of philosophers, not philosophy.
Let’s guess: The existence of the map S is independent of ZF+AC?
Comment #22 September 15th, 2006 at 6:32 pm
Hi Drew,
It is interesting that the best candidate for inventor of quantum computation, Feynman, was such a critic of philosophy.
I’m not sure I agree that Feynman is the best candidate for inventor of quantum computing. Like many others at that time, he was obsessed with the thermodynamics issues; he didn’t seem to realize that the crucial issue is asymptotic complexity.
We normally think that the more that we know, the more we can do.
Besides quantum mechanics, a second counterexample to that thesis is college students getting drunk to shed their inhibitions.
Comment #23 September 16th, 2006 at 2:06 am
In my view, Feynman can be credited as an inventor of quantum computation. His paper was the beginning of a powerful progression of papers:
Feynman -> Deutsch -> Bernstein-Vazirani -> Simon -> Shor
Even if he was distracted by thermodynamics, he was thinking in the right direction philosophically. (Even though he hated philosophy! Feynman could be viewed as an antidote to the bad side of philosophy, as quantum information theory can.)
Comment #24 September 19th, 2006 at 2:34 am
Greg, you wouldn’t put Benioff in that primary chain? Of course, we could go on and on…
I was in Feynman’s class on “Potentialities and Limitations of Computing Machines” in 1985-6 (the Challenger year), and was very excited by his talk on reversible computing (a couple of friends and I built a small billiard-ball gate for a project), but I don’t recall any discussion of what we today call quantum computing. I seem to recall that we read “There’s Plenty of Room at the Bottom”, but not his contemporary papers on QC.
And if you think he hated philosophy, check out “The Meaning of It All”. He thinks about essentially the core problems of philosophy, but I have to admit I was whelmed by that particular book/set of lectures.
There is a good quote by Feynman somewhere about the humanities in general that goes something like, “The theoretical broadening gained by having [those topics] on campus is offset by the general dippiness of the people who study such things.” Of course, that didn’t stop him from drawing and painting, playing music and doing theater, and reading and writing poetry with Jenijoy La Belle (who, I believe, is the source of the line that Feynman was “the sexiest man alive”).
Comment #25 September 19th, 2006 at 4:17 am
rdv: I, too, was deeply whelmed by The Meaning of It All.
Regarding Feynman’s “hypocritical” interest in music, theater, etc: obviously, if you just do these things to get laid, then it isn’t dippy!
Comment #26 September 19th, 2006 at 9:25 pm
Let’s guess: The existence of the map S is independent of ZF+AC?
Hah, I win.
Comment #27 September 20th, 2006 at 1:23 am
Hah, I win.
And without even a proof.
Comment #28 September 20th, 2006 at 3:41 am
And without even a proof.
Realistically, what’s the probability that I guess the right answer without a proof?
Comment #29 September 20th, 2006 at 4:20 am
Presumably less than 1 (the probability of guessing the right answer conditioned on having a proof). 🙂