Shtetl-Optimized

I just came from Brookhaven National Lab, where I gave my standard colloquium talk on the limits of quantum computers, and got driven around the RHIC accelerator ring by physicist Rob Pisarski. I knew the lab was big; what I hadn’t quite appreciated before getting there is that it’s an entire town, with its own police department, restaurants, etc. In many ways it looks like lots of small towns across America, except that this one’s primary business is smashing gold ions into each other at relativistic speeds and measuring properties of the resulting quark-gluon plasmas.

When I talk to physicists like the ones at BNL, they often find it faintly ridiculous that anyone would doubt quantum mechanics. But people certainly do — even when they don’t admit that that’s what they’re doing — when the alternative is accepting that integers are efficiently factorizable in the physical world. Which brings us to QCSD Lecture 14, on eleven skeptical objections to quantum computing and what can be said in response to them. And yeah, if you’ve been reading this blog for years, a lot of the material won’t be new to you. It’s just one more hunk of meat to throw into the tigers’ den.

Follow

A year and a half after the actual course, the remaining Democritus lecture notes are finally being transcribed and posted — thanks to my new summer student, Chris Granade. In Lecture 13, you can read about why QMA, QCMA, and BQP/qpoly are not merely complexity classes but battlefields, where competing visions of what quantum states really are face each other off in conflicts that we as theorists intentionally provoked. (Work with me here.)

Follow

After a ten-month hiatus, the Quantum Computing Since Democritus series sheepishly returns with Lecture 12, which explores how, over the past couple of decades, theoretical computer scientists have bent, twisted, and kneaded the concept of mathematical proof into strange and barely-recognizable forms. Read about proofs that don’t impart any knowledge beyond their own validity, proofs you can check by examining a few random symbols, and (for those who already know that stuff) proofs that certain interpretations of quantum mechanics would predict you can see over the course of your life, yet can’t hold in your mind at any individual time.

I apologize if this lecture isn’t as polished as some earlier ones — but while I’m working on this, I’m now also teaching a new course at MIT, 6.080/6.089 Great Ideas in Theoretical Computer Science. Barring unforeseen delays, the lecture notes for that course should be available by 2043.

Follow

After a week of brainbreaking labor, here it is at last: My Grand Statement on the Interpretation of Quantum Mechanics.

Granted, I don’t completely solve the mysteries of quantum mechanics in this lecture. I didn’t see any need to — since to judge from the quant-ph arXiv, those mysteries are solved at least twenty times a week. Instead I merely elucidate the mysteries, by examining two very different kinds of stories that people tell themselves to feel better about quantum mechanics: decoherence and hidden variables.

“But along the way,” you’re wondering, “will Scott also touch on the arrow of time, the Second Law of Thermodynamics, Bell’s Inequality, the Kochen-Specker Theorem, the preferred-basis problem, discrete vs. continuous Hilbert spaces, and even the Max-Flow/Min-Cut Theorem?” Man oh man, is someone in for a treat.

I assume that, like Lecture 9, this will be one of the most loved and hated lectures of the course. So bring it on, commenters. You think I can’t handle you?

Update (4/5): Peter Shor just posted a delightful comment that I thought I’d share here, in the hope of provoking more discussion.

Interpretations of quantum mechanics, unlike Gods, are not jealous, and thus it is safe to believe in more than one at the same time. So if the many-worlds interpretation makes it easier to think about the research you’re doing in April, and the Copenhagen interpretation makes it easier to think about the research you’re doing in June, the Copenhagen interpretation is not going to smite you for praying to the many-worlds interpretation. At least I hope it won’t, because otherwise I’m in big trouble.

Follow

You’ve eaten your polynomial-time meatloaf and your BQP brussels sprouts. So now please enjoy a special dessert lecture, which I didn’t even deliver in class except as a brief coda to Lecture 10. Watch me squander any remaining credibility, as I pontificate about Roger Penrose’s Gödel argument, strong AI, the No-Cloning Theorem, and whether or not the brain is a quantum computer. So gravitationally collapse your microtubules to the basis state |fun〉, because even a Turing machine could assent to the proposition that you’re in for a wild ride!

(Important Note: If you belong to a computer science department hiring committee, there is nothing whatsoever in this lecture that could possibly interest you.)

Follow

You’ve waited for weeks. You’ve pestered me for it. Now here it is.

For those who liked my Shor’s algorithm post but are ready for the next level: brace yourself for BQP ⊆ PP, Recursive Fourier Sampling, and so much more. And for dessert, a brief discussion of quantum computing and the many-worlds interpretation.

Suggestions and bugfixes welcome; I’ll continue revising over the next few days as time permits.

Follow

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

Psst … one-way functions? Pseudorandom generators? Lattices? RSA? Come and get ’em, in plaintext.

Gus Gutoski took notes for this “all about cryptography” lecture, and they were so good that I’ve posted them with only moderate editing and joke-reinsertion. I’ve thereby provided you, my readers, with the unique opportunity to experience my lecture as Gus himself experienced it — as if you actually were Gus, sitting in a real Waterloo classroom taking notes.

For those of you who feel the need to prepare yourselves for this experience, here’s a recap of all the lectures so far:

• Lecture 1 (9/12): Atoms and the Void
• Lecture 2 (9/14): Sets
• Lecture 3 (9/19): Gödel, Turing, and Friends
• Lecture 4 (9/21): Minds and Machines
• Lecture 5 (9/26): Paleocomplexity
• Lecture 6 (9/28): P, NP, and Friends
• Lecture 7 (10/3): Randomness
• Lecture 8 (10/5): Crypto

Update: Preparing these notes is a sh&tload of work for me. So dude — if you want me to keep doing it, please let me know in the comments section if you’re actually reading the notes and deriving any benefit therefrom. Constructive criticism would also be fantastic. Thanks very much!

Follow

Yes, less than a week after the course itself finished, a new set of lecture notes is finally here! The topic: randomness.

I’m writing this post from über-commenter Greg Kuperberg’s office at UC Davis, where I’m visiting for a few days to give a math colloquium. Greg has been trying to fill my thick skull with something called “t-cubature formulas,” and writing this post provides me with a much-needed break!

After Davis, I’ll be going to Berkeley for a couple weeks (not that I ever really left it), then my parents’ place in Pennsylvania for the holidays, then Caltech, then New Zealand (why the hell not?), then Australia for QIP, then back to Waterloo in February. Much more relaxing than last year’s trip — note that I won’t return from this one with an (additional) 2πi phase.

Follow

P, NP, and Friends. A whole undergraduate complexity course in one HTML file.

For those of you who already know this stuff: forgive me for boring you. For those who don’t: read, learn, and join the Enlightened.

Note: The comment section was down all day, but it’s back now. Google ought to be ashamed to be running something as rickety and unreliable as Blogger. Well, I guess you get what you pay for.

Follow