The quantum-complexity bathroom reader
A reader named Lewis K. wrote in to ask for a “brief list of required reading for someone with a normal CS degree under his belt who wants to be taken to the research front in quantum complexity.” Alright then:
[Deutsch] [Bernstein-Vazirani] [BBBV] [Simon] [Shor] [Grover] [BBHT] [BBCMW] [Ambainis] [Watrous] [ANTV] [Fortnow-Rogers] [Abrams-Lloyd] [Childs et al.] [DMV] [EHK] [BJK] [Gottesman] [KKR] [Marriott-Watrous]
(Sprinkle in some textbooks, survey articles, and course lecture notes to taste.)
Commenters will boil me alive for leaving out huge swaths of the field, and they’ll be right. I’ve merely listed some papers that had a definite impact on how I, personally, attack problems. But hey, I’m the one you asked. So print ’em out, take ’em to the toilet, and sit there for a long time. When you’re finished, you won’t be at the “research front” — for that you obviously have to read my papers — but hopefully you’ll have seen enough to visit the big bad arXiv on your own. Happy Hadamards!
Follow
Comment #1 September 6th, 2006 at 5:15 pm
I think there’s a clear need for a good textbook on quantum computing written by/for computer scientists. The Nielsen/Chuang book is ok (though I would not say great), but clearly written from a physics perspective.
Any volunteers? =)
Comment #2 September 6th, 2006 at 5:19 pm
Scott’s reading-list is arguably suboptimal from a game theory point of view!
For students of one-sigma ability or less (which by definition is 84.1% of students) the optimal strategy is obviously to seek out research areas in which there is less competition, not more.
The optimal strategy for most students, therefore, is to study the agnotology of your professors. What topics have your professors chosen not to know?
Then, as the Spanish saying has it: “If they give you ruled paper, write the other way!”
Comment #3 September 6th, 2006 at 6:36 pm
>Sprinkle in some textbooks
I’m reading that. I’m loving the book but hating QC.
I hope someone one day proves QC is unreliabe, and classical computing will inherit the Earth!
Comment #4 September 6th, 2006 at 10:02 pm
John, my own research strategy is:
Orient yourself in the direction of maximum confusion.
rrtucci
Comment #5 September 6th, 2006 at 10:31 pm
I think you just want me to get hemorroids.
Comment #6 September 6th, 2006 at 11:20 pm
the optimal strategy is obviously to seek out research areas in which there is less competition, not more.
Or as Paul Graham says in his essay Hackers and Painters:
Number one, research must be original — and as anyone who has written a PhD dissertation knows, the way to be sure that you’re exploring virgin territory is to to stake out a piece of ground that no one wants.
Comment #7 September 6th, 2006 at 11:39 pm
rrtucci sez: My own research strategy is: Orient yourself in the direction of maximum confusion.
Nice! Very similar in spirit to Dan Rugar’s maxim: “Go into the laboratory and make mistakes as fast as you can.”
Also similar to Ursula LeGuin’s “Inspiration more often accompanies composition than precedes it”.
These getting-started strategies work well for theory too. Just pick any (simple) problem, and work on it (in every variation you can think of) until you understand it backwards and forwards.
Comment #8 September 8th, 2006 at 9:26 am
It’s hard to believe that there are so few posts on such an important subject as a reading list.
I seem to recall that Ulam’s autobiography Adventures of a Mathematician describes Fermi (?) and von Neumann (?) arguing over the informatic topology of human knowledge.
Fermi envisioned the advance of human knowledge as a closed subset of a compact (spherical) manifold. In the Fermi worldview, the set of knowledge is destined to grow until it covers the whole sphere of knowledge, at which point, the job of math and science is done.
In contrast, von Neumann envisioned human knowledge as a subset of an open (infinite) set of potential knowledge. In the von Neumann worldview, the advance of human knowledge is destined to continue forever.
Or maybe I have Fermi’s and von Neumann’s positions reversed … but that doesn’t matter.
The point is that neither Fermi nor von Neumann envisioned that human knowledge might evolve a fractal informatic geometry — a set of knowledge with finite volume, yet near-infinite perimeter length.
With more than a million peer-reviewed articles now appearing each year, there is considerable empirical evidence in support of this non-reductionist view of the math and science frontier. To paraphrase Haldane “God must have loved complexity classes … and beetles … and galaxies … because he made so many of them.”
What does this imply for reading lists? Here’s the least agnotological list I know; it amounts to a practical course in nation-building. This list reflects–better than any other list I know–what poet Paula Gunn Allen called “the great survival sweepstakes of our time.”
This survival sweepstakes, in which we all have a ticket, is founded upon the very real possibility that the modern science and technology enterprise may undergo a collapse (see, e.g., the case histories of Tainter or Diamond).
Forestalling this collapse is, obviously, a very considerable challenge for humanity — a challenge worthy of study, and arguably a very reasonable career choice.
Comment #9 September 10th, 2006 at 7:56 am
“Number one, research must be original and as anyone who has written a PhD dissertation knows, the way to be sure that you’re exploring virgin territory is to to stake out a piece of ground that no one wants.”
Hmm, but assuming that one is at the same time a teacher, not only a researcher, and assuming that a number of one’s students are abler than their teacher (although less knowledgeable), wouldn’t it be better for the sake of science, that the less able researcher still choose the most important research area (as perceived at the current time) in order to better help his students, even though he isn’t good enough to make an important contribution himself?