Quantum Computing Since Democritus Lecture 21: Ask Me Anything
In the final Democritus installment, I entertain students’ questions about everything from derandomization to the “complexity class for creativity” to the future of religion. (In this edited version, I omitted questions that seemed too technical, which surprisingly was almost half of them.) Thanks to all the readers who’ve stuck with me to this point, to the students for a fantastic semester (if they still remember it) as well as their scribing help, to Chris Granade for further scribing, and to Waterloo’s Institute for Quantum Computing for letting me get away with this. I hope you’ve enjoyed it, and only wish I’d kept my end of the bargain by getting these notes done a year earlier.
A question for the floor: some publishers have expressed interest in adapting the Democritus material into book form. Would any of you actually shell out money for that?
Follow
Comment #1 September 2nd, 2008 at 12:13 am
Yes, because then I could cite you in a philosophy paper without the embarrassment of using a URL instead of a book title.
Comment #2 September 2nd, 2008 at 12:34 am
Carl, but that doesn’t mean you’ll buy the book. =)
Comment #3 September 2nd, 2008 at 12:35 am
I would certainly buy a book like that – without knowing more about what other resources are out there, it seems to fill an important gap (for example, as comprehensive as it is, even the Nielsen & Chuang book doesn’t really dive into the same complexity and/or philosophical issues)
Comment #4 September 2nd, 2008 at 12:39 am
On the information in a black hole not being lost: By analogy, does this mean that no information should be lost when inflation causes a star to go outside of my observable universe? Or do the reasons for information not being lost in the black hole case not apply to the expansion of the universe?
Comment #5 September 2nd, 2008 at 12:39 am
Well, even if I don’t personally buy it, I’ll get it on inter-library loan, so someone will.
Comment #6 September 2nd, 2008 at 1:06 am
Aw, man, I really want to see those technical questions now! :-/
As for whether I’d shell out money for a Democritus book: TOTALLY, and I’d badger half my scientifically-inclined friends to do the same. (Particularly if it’s not, like, $80).
Comment #7 September 2nd, 2008 at 1:29 am
I’ve heard one problem with Dawkin’s book is that it mostly just says why a lot of pro-religion arguments are wrong. Which is like giving algorithms for solving one specific instance of SAT.
Comment #8 September 2nd, 2008 at 1:30 am
Incidentally, to answer the question: I would definitely buy it and even give it as a present.
Comment #9 September 2nd, 2008 at 2:00 am
I think I will request my university library to buy that book.
Comment #10 September 2nd, 2008 at 3:32 am
I would buy it. I’ll imagine it would hit the middle ground between too-technical-way-over-my head and not-technical-enough-give-me-formulas-damn-it, making it just what I am looking for right now..
Comment #11 September 2nd, 2008 at 3:47 am
Yes, but then again, I’m not sure how much my opinion counts for on this matter…
Comment #12 September 2nd, 2008 at 4:02 am
“Would any of you actually shell out money for that?”
Absolutely. I’ve read all of the posted lectures (thanks again to Scott for taking the time to put them up), but I still want an actual book on the shelf.
Comment #13 September 2nd, 2008 at 5:49 am
I’d buy the book if it weren’t too expensive, I guess. The lectures are sort of mixed; none are “bad” but the middle and later ones go off into sort of random topics. I do like this last one, which is the most random of them all. Here’s a religious question for you: could it be that these deity characters actually exist, but they’re not natural at all, they just have access to devices like CTC’s that they can use as pspace oracles? Maybe they left some technological artifacts in Atlantis or R’lyeh?
And a silly P vs NP question: are most folks convinced that not only P!=NP, but also NP-hard problems actually require exponential time, rather than some subexponential function that’s still superpolynomial? By the way did you see the survey that GASARCH did a while back, where he asked a bunch of researchers what they thought of the P vs NP problem? I was amazed at some of the answers and I liked Knuth’s the best.
Comment #14 September 2nd, 2008 at 5:49 am
Typo: not natural => not supernatural
Comment #15 September 2nd, 2008 at 6:15 am
Absolutely – it’s easier to read things on the page than on the screen. As long as it wasn’t ludicrously priced and there was a paperback version
Comment #16 September 2nd, 2008 at 6:37 am
BTW, Scott (or anyone), do you have any opinion of this page and the paper it links to? The statement “As is well known, the absence of algorithmic solutions [to undecidable problems] is no obstacle when the requirements do not make a solution unique. A notable example is generating strings of linear Kolmogorov complexity, e.g., those that cannot be compressed to half their length. Algorithms fail, but a set of dice does a perfect job!” makes it sound like proving any good derandomization theorems may be very difficult, as difficult as P vs NP itself.
Comment #17 September 2nd, 2008 at 6:53 am
asdf: Interesting point, but I think the questions are quite different. It’s clear that randomness helps for generating “truly random strings.” The question with derandomization is whether it also helps for solving decision problems. A pseudorandom generator doesn’t work for the first problem—almost by definition!—but we believe it helps a great deal for the second. One reason is that, to solve the second problem, all the pseudorandom numbers need to do is be indistinguishable from true random numbers by any polynomial-time algorithm.
Comment #18 September 2nd, 2008 at 7:07 am
On the information in a black hole not being lost: By analogy, does this mean that no information should be lost when inflation causes a star to go outside of my observable universe?
Carl: It’s an excellent question, and I’ll have to defer to experts for a full answer. However, note that as a star recedes past your observable universe, you’ll simply see that as signals from the star taking asymptotically longer to reach you—i.e., as the star getting “stuck on your cosmological horizon.” So, that would suggest that maybe the answer is yes.
Comment #19 September 2nd, 2008 at 7:10 am
asdf: Yes, most people are convinced that NP-complete problems require exponential time. Yes, I saw GASARCH’s survey. Yes, maybe the traditional deities are PSPACE oracles—but if so, then they’re also going to need some fairly impressive I/O devices, for tasks like sea-parting and loaf/fish duplication.
Comment #20 September 2nd, 2008 at 7:59 am
I’m no one important in particular, but I’d also definitely buy the book.
Comment #21 September 2nd, 2008 at 8:07 am
So, if we study the CMB, all of the information from the bits of the universe that used to be in view are still out there? If so, wouldn’t that tell us that the universe is finite, since if it were infinite, all that radiation would light up the sky (vanishingly small number X infinity = infinity)? That would be a nice thing to know.
Comment #22 September 2nd, 2008 at 9:23 am
Scott, thanks. Clearly the parting of the Red Sea so that Moses and his followers could walk across it in their sandals was an example of a Shoe/Shore separator…
Comment #23 September 2nd, 2008 at 9:25 am
Personally, I’d love to own that book.
Comment #24 September 2nd, 2008 at 10:26 am
anonymous @Dawkins:
This review says that’s a problem only with the second half of the book.
Comment #25 September 2nd, 2008 at 10:50 am
Scott, this was a wonderful series of lectures … please allow me join in the general chorus of “thank you”.
Here is a question that relates to a common and generic assertion in the QIT literature along the lines “Digital simulations of large scale quantum many-body Hamiltonians are essentially hopeless on classical computers”.
The preceding quote is from a forthcoming Rev. Mod. Phys. article (arxiv: 0707.1889) that echoes a belief that has been widely held in the QIT community ever since Feynman’s 1982 article Simulating Physics with Computers, with the result that similar statements appear in many QIT textbooks, articles, and lectures.
Scott, from a QIT perspective, is this belief true? And if it is true, what QIT loophole(s) are the quantum chemists and condensed matter physicists exploiting to create their extraordinarily accurate large-scale simulations?
This question has a practical point: continued remarkable advances in quantum simulation capability and QIT theory are providing increasingly strong evidence that the question: ‘Can large scale quantum systems be simulated with classical resources?’, has an answer that is far richer than simply ‘yes’ or ‘no’ … to the point these advances are creating jobs for young quantum researchers.
That is a practical reason why a “Shtetl Optimized” perspective on this fundamentally important question would be *very* welcome!
Comment #26 September 2nd, 2008 at 1:08 pm
Yes of course. It has a potential to be a great book. (And also I’d be happy to read earlier versions and try making helpful comments on them.)
Comment #27 September 2nd, 2008 at 2:58 pm
Would buy if reasonably priced, borrow if not.
Comment #28 September 2nd, 2008 at 3:46 pm
If it is not incredibly expensive, I would buy it, also as a present for some like-minded friends.
Comment #29 September 2nd, 2008 at 4:46 pm
To agree with Gil—and for the benefit of the numerous eagerly bidding publishers who no doubt read Shtetl Optimized—our UW QSE Group surely will buy Scott’s book as a welcome addition to our laboratory’s Library of Subversive Literature.
Any book that contains new and interesting ideas (whether technical or not) is a candidate, and it’s 100% certain that any book written by Scott will qualify.
Comment #30 September 2nd, 2008 at 4:58 pm
Wonderful final chapter. Feynman also taught “Physics X” which was like that every day.
“irrationality can be supremely rational, because it’s the only way of proving to someone else that you’re committed to something. Like if someone shows up at your doorstep and asks for $100, you’re much more likely to give it to him if his eyes are bloodshot and he looks really irrational–you don’t know what he’s going to do!”
Dr. George Hockney (FermiLab to UCLA postdoc in Lattice Gauge Theory to JPL Quantum Computing and General Relativity) considers that President George W. Bush’s greatest strength. Bin Laden didn’t think he’d retaliate for 9/11. Boom, we’re in Afghanistan. Saddam didn’t think we’d go back into Iraq. Boom, we’re in Baghdad for a terabuck’s worth of chaos. Iran doesn’t think we’d nuke their nuclear capability — but they just can’t be sure.
Whose eyes are more bloodshot, Bush’s or Putin’s?
Given your new residence, you have by now been told about escalation between Boston automobile drivers, right? Each pretends more and more blatantly not to see the other, and drive more and more recklessly, until one ups the ante by tearing off the steering wheel and throwing it out onto the street.
Hello, Sarah Palin!
As I’ve pointed out before, there is no complete rational answer to the meta-question: “Why be rational?”
Comment #31 September 2nd, 2008 at 5:06 pm
Would tell the University library to buy it, surely.
Thanks a lot for the lectures, Scott.
Comment #32 September 2nd, 2008 at 7:04 pm
Would definitely buy the book; the Democritus lectures make quantum computing and physics concepts very accessible to people with traditional computer science backgrounds.
Comment #33 September 2nd, 2008 at 7:56 pm
I would buy it, assuming it was sufficiently fleshed out and popularized.
Comment #34 September 2nd, 2008 at 8:14 pm
Your lecture notes would make an excellent book! But if you were to expand it into a book, would you try to make it more of a textbook (with sections, subsections, exercises and examples) or something along the lines of Richard Feynman’s books (more like a set of science essays)?
Comment #35 September 2nd, 2008 at 8:36 pm
Scott, this question is inspired by one asked by Harvey Friedman on the FOM mailing list a while back. If you had access to a PSPACE oracle for a day, what would you do with it? Let’s say you can give it 1 query per hour, so 24 total queries. What would you ask it? And how would you know if the answers it gave you were right?
Comment #36 September 2nd, 2008 at 8:52 pm
I would like to buy it, but it’s either your book or my medicines.
Comment #37 September 2nd, 2008 at 9:30 pm
I would buy three copies—one for me, one for each of my sons (4 and 9 yrs). These lectures are the best example I’ve seen of why there should be institutions of higher learning. (No disrespect intended to my former profs.)
Comment #38 September 2nd, 2008 at 10:01 pm
If you had access to a PSPACE oracle for a day, what would you do with it? Let’s say you can give it 1 query per hour, so 24 total queries. What would you ask it? And how would you know if the answers it gave you were right?
Well, can the oracle provide multi-bit outputs (i.e. is it an FPSPACE oracle)? If so, then I might first ask for a proof of P≠NP, then for a proof of Goldbach’s conjecture, then for a small circuit that describes historical stock market data. I’d know the answers are right because these are NP (or at worst, PNP) search problems. I’d put out a request to the scientific and mathematical communities for cool things to do with the remaining 21 queries.
If the oracle only allowed Boolean queries, then I guess I’d just ask about the truth or falsehood of various interesting mathematical statements (as well as things like whether White or Black has the win in chess). I wouldn’t know that the answers were correct, except under the assumption that I was actually querying a PSPACE oracle (and not some impostor thereof). Given more queries, I could force the oracle to prove its answers to me (using the IP=PSPACE theorem, or just self-reducibility for NP queries). But that would require a number of queries that grows linearly with the problem size, certainly more than 24 for any interesting problem.
Comment #39 September 2nd, 2008 at 11:24 pm
Thanks, cool answer. Good point about IP=PSPACE and getting proofs out. Yes I meant boolean queries, but I guess IP=PSPACE makes increasing the number of queries to (say) a few hundred makes the question more interesting. I just didn’t want it to be a huge number.
In Harvey Friedman’s version, you got something that claimed to be a Pi01 oracle: you get 1000 queries and for each one, you put in any Turing machine description up to 100 quadruples, and the oracle purports to tell you whether that TM halts (on empty input I guess). Part of the problem was to propose ways of distinguishing a real halting oracle wth an imposter.
(After a couple of minutes searching): OK, I found Friedman’s original post: http://www.cs.nyu.edu/pipermail/fom/2004-February/007934.html
There are some followup posts scattered through the FOM archive from around that period.
Comment #40 September 3rd, 2008 at 8:52 am
In the answer to the question about the complexity class of creativity you have compared human’s vs. machine’s theorem proving. Would you describe why this comparison is true? How can compare human intelligence with AI since we don’t know exactly how the brain works to solve a certain problem? Maybe there is an oracle, say our emotion or the sixth sense, which someday will help us prove any theorem! Maybe the massive parallel processing system of the brain is the reason of its powerfulness in certain problems and the reason that we are still not able to have an algorithm to prove any theorem is the imperfection in our accessibility to our memory! Maybe if could attach a chip to access certain bits of our memory efficiently, we could solve NP-complete problems by our own brains! Until know, I want to claim that it would be faulty to compare human and machine intelligence and judge about the complexity class of creativity. Nevertheless, I also believe that the human rice will never solve any NP-complete problem because of the Gödel’s Incompleteness and Russell’s paradox! You see that classical computers function based on classical laws of physics. Quantum computers, that are known to be able to solve at least factoring probably more efficient than classical computers, function based on the laws of physics that are able to describe more natural phenomena (quantum mechanics)! I guess if some day we want to have a sort of computers that is able to solve NP-complete problems we have to have the Theory of Everything! I believe that we will not be able to find the real Everything’s Theory and “know God’s thoughts”, because our minds are subset of the nature and no subset can cover its superset!
Comment #41 September 3rd, 2008 at 10:03 am
I would buy it.
Comment #42 September 3rd, 2008 at 10:37 am
On the information in a black hole not being lost: By analogy, does this mean that no information should be lost when inflation causes a star to go outside of my observable universe?
We can still wait for the experts, but in the meantime let me try… just because information is no longer accessible to us doesn’t mean there is information loss. All those “I Love Lucy” episodes traveling away from earth at the speed of light cannot be retrieved either… In other words, there is nothing mysterious about information loss in an open system (like our cosmological horizon). So, for black holes, you could just say the information is stored behind the horizon. The thing that makes information loss a paradox in black holes is the fact that it evaporates, so you could ask where is the information stored after the black hole is gone (or whether a Planckian remnant is likely to store macroscopic amount of information, etc.).
Comment #43 September 3rd, 2008 at 5:17 pm
With the black hole discussion, I’m certainly no expert either, but I figured I’d point out:
Scott’s bit about the information taking asymptotically longer to reach you, something similar is true in the case of black holes; from outside the event horizon objects falling in take infinitely long to do so, with the wavelength of light being shifted to lower and lower frequencies. (A wikipedian once told me that after 2-3 days the light emitted would have a wavelength of >80,000 km.)
As far as I can tell, this is a well accepted conceptual principle of black hole physics, and I have never once heard it discussed in relation to the information paradox or with respect to black hole evaporation, (which I would think complicates the matter—pun!).
To me, this is all way too speculative to come to any definitely conclusions about yet.
I saw Hawking on a BBC special about the whole debate, saying that his result was so beautiful and simple that it had to be right, and I find that surprisingly naïve, comparable to believing orbits must be perfect circles because it is a simpler equation. So I remain very skeptical of our current black hole theories.
Comment #44 September 3rd, 2008 at 6:42 pm
I would definitively buy such a book.
My girlfriend is unlikely though.
Comment #45 September 3rd, 2008 at 10:07 pm
Thanks Scott! (Or should I thank W?) Ironically since I bugged you so much about publishing the rest of your lectures my life has become so busy I haven’t made the time to read any of your lectures since the recent surge. Instead I’ve printed them off so I could read them in book form.
It doesn’t matter whether I would buy your book or not. It only matters that you have something to say that is worthy of a book. Choose a publihser that doesn’t make you dumb it down, or at least include a technical appendix to each chapter. Find an agent who can book you on lots of early morning drive-time radio shows for telephone interviews, not just NPR. And take full advantage of the episode with the Australian models.
Comment #46 September 3rd, 2008 at 11:58 pm
In this essay, Ann Druyan recounts Sagan’s contribution to combating creationism:
I only bring this up because I feel that we, (the informed), have some sort of duty to combat the ignorance of the uninformed. Though I suppose there will always be the unswayable. Maybe I will refocus my efforts on searching for rational replacements for the social roles of religion, that is after all a decent point.
Also, I would buy the book.
Comment #47 September 4th, 2008 at 12:51 am
I would definitely buy that book. It makes me sad that I haven’t had time to read all the lectures, and I would be a lot less lazy if it was in book form.
Comment #48 September 4th, 2008 at 5:42 am
If it’s at all reasonably priced I would definitely buy the Democritus book.
Comment #49 September 4th, 2008 at 12:21 pm
In general agreement with comments #33 & #34, I doubt if I would buy it if it consisted of just the raw PDF’s slapped together, but if it were expanded somewhat with diagrams, a glossary, more examples, etc., I would pay up to, say, $30 for it. Okay, $40 if there were a lot of new material.
(Can you have it out by Christmas? I have a nephew who is going into computer science.)
Comment #50 September 5th, 2008 at 5:40 am
Yes I would, largely because I pay much more attention to the printed word so would be able to understand more.
Comment #51 September 5th, 2008 at 8:11 am
You mean he didn’t insult the very idea of religion, and then ask for people to give him consecrated hosts to “desecrate”? Why didn’t anybody think about this before?
Comment #52 September 5th, 2008 at 10:43 am
Thanks for publishing all these lectures, Scott. Those of us that took the course can read these and reminisce.
However, why’d you go and cut the technical questions? I can see collating them separately, but heck, it provides a decent insight into the class that this was taught to.
Comment #53 September 5th, 2008 at 2:10 pm
I’d buy the book, Scott.
Comment #54 September 5th, 2008 at 3:24 pm
Hmmm … the QIT blogo-sphere seems to be falling somewhat into the doldrums.
So on the topic of books, who among Shtetl Optimized readers has happened upon Norbert Wiener’s novel The Tempter?
I would post a link, but there seems to be very little discussion of Wiener’s novel on the web. Which is surprising, as Wiener’s book is rather a good read.
Quite a few of the topics that Wiener discusses are broadly relevant to modern QIT. In particular, Wiener’s novel attempts to construct (reasonably successfully IMHO) a social narrative that dovetails with research in control theory and cognition.
Does QIT afford similar opportunities and scope? Here’s a chance for Shtetl Optimized readers to make blogging history! 🙂
Comment #55 September 6th, 2008 at 1:42 am
Yes, I would buy it, ebook or book, paperback or hardback!
Comment #56 September 6th, 2008 at 2:06 am
Scott,
I don’t know how to prove P ne NP. Please show me. Thanks.
MI