The Blog of Scott Aaronson Quantum computers need ~√N queries to search a list of size N.
Accelerate covid vaccines and hold the November US election by mail!
"The Far Right is destroying the world, and the Far Left thinks it's my fault!"
When civilization's collapsing, sometimes there's nothing to do but math.
Yes, I’m blogging from outside Nairobi, where I’ve come to investigate the true circumstances of President Obama’s birth. Seriously, Dana and I are here to go on a safari for our belated honeymoon—for both of us, it’s our first non-work-related trip in many years. Needless to say, we both brought our laptops.
Like everyone else with an ounce of sense, I’m absolutely horrified by SOPA, and inspired by the way so many Internet companies and organizations have banded together to try to prevent the United States from moving in the direction of China and Iran.
Meanwhile, on the theme of open access to information on the web, check out a New York Times article by Thomas Lin about the open science movement. I’m quoted briefly toward the end.
Sorry for the light (nonexistent) blogging lately. I’ll be back after I’m done with the lions and hippos and so forth.
Wouldn’t Jeopardy! be better without those stupid buzzers? Even if the contestants just, y’know, took turns? In a game focused solely on question-answering (OK, OK, answer-questioning) rather than buzzing, Watson would still have done amazingly well and reflected credit on its developers, but the man/machine competition would have been much closer and much more interesting to watch. No one needs a repeated demonstration that computers have faster reaction times than humans.
Inspired by the timeline discussion: could something like Watson have been built in, say, 2000? If not, then which developments of the past decade played important roles?
Back when Deep Blue beat Kasparov, IBM made a big to-do about the central role played by its large, specially-designed mainframe with custom “chess chips”—but then it wasn’t long before programs like Deep Fritz running on desktop PCs produced similar (and today, probably superior) performance. How long before we can expect a computer Jeopardy! champion that fits behind the podium?
A month ago, Caltech hosted a daylong event called “TEDxCaltech / Feynman’s Vision: the Next 50 Years”, which was attended by about a thousand people. Celebrity participants included Stephen Hawking, Carl and Michelle Feynman (Carl told me he’s a fan of the blog—hi Carl!), and Ondar, a Tuvan throat-singer who pretty much stole the show.
Videos are finally being posted on YouTube; my talk is here. My goal was to cover the P versus NP question, quantum computing, conceptual issues in quantum mechanics, and Feynman’s relation to all three, while also cracking crude masturbation jokes (in a talk like this, one has to bring out the heavy humor cannons), and to finish in 15 minutes. I don’t know how well I succeeded—but if I die tomorrow, then at least Stephen Hawking was in the audience when I made my case for P and NP being as big a deal as anything in physics.
Two explanatory comments:
By far my most successful joke was a reference to “prime numbers, such as 3, 5, 1…” Before the lunch break, the emcee had told everyone to be back by 1:35, “which I’m sure you nerds will remember since it’s the first three prime numbers.”
Yeah, I know the current upper bound on the matrix multiplication exponent is 2.376, not 2.736! It was correct on the slides I submitted, but got transposed when the slides were converted into “TED format.”
If you think my talk stinks, my only defense is that showing up to give it was already an accomplishment: my flight (from Tel Aviv to LA through Newark) was canceled because of a snowstorm, so I arrived at Caltech exhausted and barely conscious, via a 36-hour alternate route through Frankfurt and London.
I have to confess that I was skeptical of this event’s entire premise. Richard Feynman was famous for his contempt of pomp and authority; would he really have enjoyed a heavily-scripted day extolling him as a secular saint? In the end, though, the quality of many of the talks made the event more than worthwhile for me, even without counting Ondar’s throat-singing as a “talk.” I particularly enjoyed the cosmology talk of fellow-blogger Sean Carroll (yo, Sean), the Feynman stories of Lenny Susskind, a demonstration of the mind-blowing WorldWide Telescope by Curtis Wong of Microsoft, and a “Who Wants to be a Millionaire?” parody skit put on by the three “black hole bettors” (John Preskill, Kip Thorne, and Hawking, the last of whom wheeled into the auditorium to thunderous applause and the opening fanfare of Thus Spake Zarathustra). I understand that all the talks will eventually be on YouTube here.
Thanks to Michael Roukes, Mary Sikora, John Preskill, Ann Harvey, and the other organizers for putting this thing together and for inviting me.
Follow