One of the most amusing things about writing a blog is that people you’ve never met form an impression about you from your blabberings, and then, often, when they actually meet you they are astounded that you aren’t “an old grumpy guy” or whatever image they had in their mind. So, in order to confuse you even more, here are some things which I’ve been reading and thinking about and doing while not working on efficient quantum algorithms for the hidden subgroup problem.
Continue reading “Woke Up, Got Out of Bed, Dragged a Comb Across my Head”
Ski Lift Conversations
The man on the lift chair at Stephen’s Pass asks me my occupation. Professor, I tell him, at the University of Washington.
Oh, he offers, My daughter is a fourth generation Husky. I was in the class of 1972. Or, well I would have been if I’d graduated, but I knew what I wanted to do didn’t need a degree. If I’d wanted to work for IBM or Honeywell or something, then I guess it would matter.
Seattle, he continues scratching some snow from his mustache, used to be such a great city. But now, the traffic is crazy. My wife and I went on a trip and couldn’t find a city more messed up than Seattle.
Interesting, I tell him, hoping that exactly my lack of interest might change the topic of conversation. So what do you do?
I’m retire now, but I used to be developer.
The Fremont Lenin Stole Huck's Votes!
Mike Huckabee calls the state of Washington the Soveit Union. Of course, this is old news to anyone who has been to Fremont:
Must Pass Texas
As a native Californian, my sworn enemy is the state of Texas. Thus it gives me great pleasure to see that the state of Washington is tied with Texas in venture capital funding. Soon, Seattle, will rule the world! Okay, maybe not. But I love Oren Etzioni’s comment on comparing Silicon Valley to Seattle:
Mr. Etzioni says Seattle has at least one advantage over its storied counterpart in California. “People aren’t distracted by too much sunshine,” he said. “They sit in their offices or garages and get creative.”
A Many Worlds Puzzle of a Different Kind
Fortune has put out its list of the top 100 companies to work for. The Google Monster is number one. Washington state does pretty good, as it is in a tie for fourth in the total number of companies on the list with headquarters in the state. (Per capita it comes in third, losing to Delaware and D.C.)
Looking through their article on “10 fascinating Googlers” I found Wei-Hwa Huang. Hey, he was in my class at Caltech! Indeed Wei-Hwa was responsible for one of my favorite stories about the many-worlds interpretation of quantum theory. Huh?
Continue reading “A Many Worlds Puzzle of a Different Kind”
Seattle Contradiction: Geek City USA and Bachelors Production
From the magazine Seattle Metropolitan, comes the article “Smartest city ever: 50 ways Seattle will change the world.” I hope the claim is true, but like all magazine articles from rags denoted entirely to a city, the lens is more than a little biased.
Continue reading “Seattle Contradiction: Geek City USA and Bachelors Production”
2007 MacArthur Awards
MacArthur awards for 2007 have been announced. Seattle scores two, Yoky Matsuoka (right here in my own department!) and Mark Roth at the Fred Hutchinson Cancer Research Center. My old alma mater (“nourishing mother?”) Caltech received two awards, and my grad school alma mater Berkeley received one.
I think I am begining to understand why I have an inferiority complex.
Google In My Backyard
Cool, Google is opening R&D research space in Fremont, a neighborhood just down the hill from our house. If I were young and hip and wanting to live in a great area and work for a crazy company, I’d certainly want to be in those offices! Hey Google: interested in quantum computing? 🙂
The NP-complete Dog and Pony Show Comes to Seattle
Scott’s coming to town:
CSE Colloquium, 04/12/2007 3:30 pm, EE-105
Talk: The Limits of Quantum Computers
Speaker: Scott Aaronson (University of Waterloo)
Abstract: In the popular imagination, quantum computers would be almost magical devices, able to “solve impossible problems in an instant” by trying exponentially many solutions in parallel. In this talk, I’ll describe four results in quantum computing theory that directly challenge this view.
First, I’ll show that any quantum algorithm to decide whether a function f:[n]->[n] is one-to-one or two-to-one needs to query the function at least n^{1/5} times. This provides strong evidence that collision-resistant hash functions, and hence secure electronic commerce, would still be possible in a world with quantum computers.
Second, I’ll show that in the “black-box” or “oracle” model that we know how to analyze, quantum computers could not solve NP-complete problems in polynomial time, even with the help of nonuniform “quantum advice states.”
Third, I’ll show that quantum computers need exponential time to find local optima — and surprisingly, that the ideas used to prove this result also yield new classical lower bounds for the same problem.
Finally, I’ll show how to do “pretty-good quantum state tomography” using a number of measurements that increases only linearly, not exponentially, with the number of qubits. This illustrates how one can sometimes turn the limitations of quantum computers on their head, and use them to develop new techniques for experimentalists.
No quantum computing background will be assumed.
Since no quantum computing background is assumed, I may even be able to follow this one!
Talk Next Week
For local Seattlites the following shameless self promotion message 🙂 Next Tuesday at 4pm I’m giving a talk in the Physics department (C421 Physics/Astronomy Building) for the Condensed Matter and Atomic (CMA) Physics Seminar. The title of the talk is “When Physics and Computer Science Collide: A Cross Cultural Extravaganza” and the abstract is
In 1994 Peter Shor discovered that computers operating according to quantum principles could efficiently factor integers and hence break many modern cryptosystems. Since this time researchers from disciplines–physics, computer science, chemistry, and mathematics–have been engaged in building an entirely new discipline now known as quantum information science. Being a highly interdisciplinary endeavor, quantum information science requires not just mastery of physics or of computer science, but an ability to take insights from both fields across the cultural divide. In this talk I will discuss how physicists can contribute to the computer science side of quantum computing and how computer scientists can contribute to the physics side of quantum computing via a series of vignettes taken from research in my group here at UW.