Customer X: Hi, D-wave? So, I hear that you have this computer that can be used to solve computationally hard problems. Oh, yes, sorry, should have said a quantum computer, my bad. Well, you know we’ve got this hard computational problem, [Editor: problem description deleted to protect identity of involved company.] So what do you think, can you solve this problem for me? Great! Let me put you in contact with my technical guy. Yes, I’ll wire the money to your account today.
Months later.
Customer X: Hi D-Wave, thanks for all your help with getting us set up to use your machine to solve these hard computational problems. We ran the adiabatic algorithm a few times, but it doesn’t seem to be working. Do you have any suggestions? Oh, try a different adiabatic annealing schedule, okay, I’ll pass this on to my technical guy. Thanks for your help. Is it still raining in Vancouver?
A day later.
Customer X: So we tried a new annealing schedule, but it didn’t seem to help. Well it helped on a few of our instances, but not all of them. Any suggestions? Okay I can hold. [Celine Dion music ensues for twenty minutes.] Right. Your tech guys suggest this particular annealing schedule. Great, we’ll try that! How’s the rain?
An hour later
Customer X: Well okay, so we tried that one and again it got a few more answers correct, but now it doesn’t work on the other instances. Can you tell me where that annealing schedule came from? Oh, I understand company secret. Okay can you send me another annealing schedule? Rain again? Sheesh, Noah would have loved Vancouver.
Days later, many annealing strategies shown not to work.
Customer X: So, um, I guess I should have asked this when we started, but what understanding do you have about the speed-ups guaranteed by your machine? I mean, certainly you have at least some evidence that the machine will be able to solve the instances that matter, right? Or at least tell me if my instances will be sped up on your computer? Hello? Hello?
[This blog post brought to you by the letter R and the quote “For now the adiabatic quantum optimizers have the upper hand.”]
Liquid Mountaineering
Hella! Huh? Meh. + "How Many Licks? Or, How to Estimate Damn Near Anything"
What prefix do you use for 1027? If Austin Sendak has his way, it will be ">hella (also Time article here.) The diameter of the observable universe is about one hellameter. As a fellow member of the club “people from Yreka, CA who do physics,” I strongly support Austin’s idea. Indeed it now tops my list of proposed prefix changes, a list that includes “tiny-” for 10-5 and my former front runner for 1027 “bronto-.”
But the real question is what do we call 10x when we don’t know x? I suggest the prefix “huh”. Examples: “My answer of about 5 huh-people wasn’t good enough to land me a job at McKinsey and Company.” “Einstein calculated that the cosmological constant was about huh inverse seconds squared.”
Another prefix that is needed is to express when you don’t really care what the hell the size is. For this I might suggest “meh.” Example: “The circumference of a African swallow’s leg is about mehmeters, thus rendering it incapable of carrying a coconut.”
Which reminds me. A while back I got a review copy of How Many Licks?: Or, How to Estimate Damn Near Anything
Cat Meets iPad
Quantum Hustles
Over at masteroftheuniverse, the master has posted a great list of prop bets. Among his bets is one that probably won’t work on many computer scientists (or it shouldn’t if they’ve had even a decent theory course) based upon the birthday problem. Sometimes the birthday problem is called the birthday paradox, but the problem is no more a paradox than the twin paradox is about twins. The birthday problem has to do with the probability that a set of randomly drawn people share a birthday. In other words, assuming that everyone in a group of N people has an equal probability of being born on a given day, what is the probability that at least two of these people share a birthday. Quite surprisingly, or at least surprising the first time you hear it, is that if N is 23, this probability is already greater than 50 percent. In computer science this type of process comes up all the time and is responsible for lots of square roots that one sees in running times of algorithms. The master’s blog post reminded me of a version of the birthday paradox that Wim van Dam once told me (if anyone knows its past history, please post a comment)…a quantum birthday paradox.
Here is the setup. Suppose that we are sampling from the set . In particular consider the situation, classically, where we are sampling from two distributions over this set, and . Both and are distributions which are on exactly N of the elements of and 0 on the rest of . I will guarantee you that either the distributions are equal, , or that when has weight on an element, then has weight 0. In other words, the probability vectors for these distributions are orthogonal, so I will denote this . So the problem is, given the ability to classically sample from these distributions, how many samples must one take to succeed in identifying which of these two cases, or , hold. One can easily see that this probability is like the birthday problem: by sampling from and one has to basically wait for a collision in order to determine that . Thus you can see that it would require about samples to distinguish these two cases. More specifically, to distinguish between these two cases with some constant probability, say a probability of 3/4, we need to sample times.
Okay so what does this have to do with a quantum birthday paradox. Well now consider the situation where instead being given two probability distributions and , one is given two quantum states, and , with the property that if you simply measure them in the computational basis you will obtain the classical distribution that behave like and . That is let and be superpositions over 2N computational basis states with the property that in this basis, they have exactly N amplitudes which are and N amplitudes which are zero. We are guaranteed that either or and the goal is, by using many copies of and to distinguish between these two cases. Now if one simply measures these states in the computational basis then one obtains probability distributions that are exactly like and . But this is the quantum world, so we don’t have to measure in this basis. So is there a basis that we can measure in which can lead to using less that copies of and to distinguish the two cases of versus ?
The answer is yes, indeed. Of course that’s the answer: why else would I be writing this blog post. In particular consider the fully symmetric or anti-symmetric subspaces of the two systems. In particular, define the states
if
if
and
if
These states form a complete basis for the two systems we are considering, with the states representing symmetric states and the states representing the anti-symmetric states. Suppose that on and we measure the above states. Now if , then we note that is symmetric under exchange of the two states subsystem. That is if we measure the above basis states we will only obtain basis states. If, on the other hand then it is straightforward to see that has support equally on symmetric and anti-symmetric states. In particular if
and
where , then we can expand as
From which we can see that we will obtain the symmetric and anti-symmetric states with equal probability.
Thus we have seen that by making a measurement which distinguishes between the symmetric and antisymmetric subspaces of our two systems, if we will only observe symmetric states and if we will observe symmetric states half the time and anti-symmetric states the other half the time. Thus we can reliably distinguish these two cases with a failure probability of for k repetitions of this setup. This is significantly better from the classical case! Indeed we have succeeded in distinguishing the states with probability 3/4 using only 2 repetitions of the setup. Thus we have gone from in the classical world to in the quantum world. Amazing! (Of course many will argue the setup is not fair: and yes I agree it is not fair when one side gets to use this powerful thing called quantum theory and the other side hides behind the computer science of the 20th century 🙂 ) Many of you will recognize that the above method for distinguishing states is nothing more than the quantum swap test.
So what is the moral of all this? Well, besides showing a cool case where quantum exponentially outperforms classical, it also tells you that you should be wary of quantum computers offering you bets. Indeed, I make it my own personal policy never to bet with quantum computers, and think that you should make it your policy as well.
Many Paths Interpretation of Scientific Careers
Items sharing a similar topic, meandered onto in the depths of a major outpouring of procrastination…
The path less traveled by Andrea Schweitzer (via @mattleifer) on a different way to have a career as a scientist. And for a description of one of the most successful scientists from quantum computing, an interview with Ignacio Cirac (sent to me by Daniel.) Somedays, however, one might wonder about all the time professors spend working and contemplate the idea of death by tenure track. Or if you care a lot about the notion of tenure versus non-tenure AND you don’t mind reading redstate.org, you can amuse yourself reading Glorious Leader Gap: More Evidence Our Pretentious President Was Never a Law School Professor. Equally depressing, but perhaps in a different form, is the state of the astronomy job market. For better options, you might try computer science (unless of course you’re going to start screaming about DEH TOOK OUR JRBS OVER CCCCs, in which case, go ahead rant, but please include at least one link to statistics in your rant.)
Painful Toy
It’s like Jackass for people who can wire stuff together (via @JoeAndrieu):
Happy Friday!
2010 Pi Day Contest
Scienceblogs and Serious Eats are teaming up this year for the 2010 Pi Day Bake-Off. I wonder if Mrs. Pontiff is up to defending her crown?
Steve Ballmer Talk at UW March 4, 2010
Today Microsoft CEO Steve Ballmer spoke at the University of Washington in the Microsoft Atrium of the Computer Science & Engineering department’s Paul Allen Center. As you can tell from that first sentence UW and Microsoft have long had very tight connections. Indeed, perhaps the smartest thing the UW has ever done was, when they caught two kids using their computers they didn’t call the police, but instead ended up giving them access to those computers. I like to think that all the benefit$ that UW has gotten from Microsoft are a great big karmic kickback for the enlightened sense of justice dished out by the UW.
Todd Bishop from Tech Flash provides good notes on what was in Ballmer’s talk. Ballmer was as I’ve heard: entertaining and loud. Our atrium is six stories high with walkways overlooking it which were all packed: “a hanging room only” crowd as it was called by Ballmer. The subject of his talk was “cloud computing” which makes about 25 percent of people roll their eyes, 25 percent get excited, and the remaining 50 percent look up in the sky and wonder where the computer is. His view was *ahem* the view of cloud computing from a high altitude: what it can be, could be, and should be. Microsoft, Ballmer claimed, has 70 percent of its 40K+ workforce somehow involved in the cloud and that number will reach 90 percent soon. This seems crazy high to me, but reading between the lines what it really said to me is that Microsoft has *ahem* inhaled the cloud and is pushing hard on the model of cloud computing.
But what I found most interesting was the contrast between Ballmer and Larry Ellison. If you haven’t seen Ellison’s rant on cloud computing here it is
Ellison belittles cloud computing, and rightly points out that in some sense cloud computing has been around for a long time. Ballmer, in his talk, says nearly the same thing. Paraphrasing he said something like “you could call the original internet back in 1969 the cloud.” He also said something to the effect that the word “cloud” may only have a short lifespan as a word describing this new technology. But what I found interesting was that Ballmer, while acknowledging the limits of the idea of cloud computing, also argued for a much more expansive view of this model. Indeed as opposed to Ellison, for which server farms equal cloud computing, Ballmer essentially argues for a version of “cloud computing” which is far broader than any definition you’ll find on wikipedia. What I love about this is that it is, in some ways, a great trick to create a brand out of cloud computing. Sure tech wags everywhere have their view of what is and is not new in the recent round of excitement about cloud computing. But the public doesn’t have any idea what this means. Love them or hate them, Microsoft clearly is pushing to move the “cloud” into an idea that consumers, while not understand one iota of how it works, want. Because everything Ballmer described, every technology they demoed, was “from the cloud”, Microsoft is pushing, essentially, a branding of the cloud. (Start snark. The scientist in you will, of course, revolt at such an idea, but fear not fellow scientist: you’re lack of ability to live with imprecision and incompleteness is what keeps your little area of expertise safe and sound and completely fire walled from being exploited to the useful outside world. End snark.)
So, while Ellison berates, Ballmer brands. Personally I suspect Ballmer’s got a better approach…even if Larry’s got the bigger yacht. But it will fun to watch the race, no matter what.
Singularity University GSP
The Singularity University is crazy. I like crazy. If I were a grad student with copious time on my hands (trust me, in comparison, you have copious time, dear GradStudent) I’d apply to attend the Singularity University summer school:
SU’s Graduate Studies Program (GSP) is a 10-week summer program (June 19 through August 28) located at NASA Ames Research Park in Silicon Valley. The program is for top graduate and postgraduate students worldwide to learn about the various exponentially growing cross-disciplinary technologies (biotechnology, nanotechnology, information technology, artificial intelligence, robotics, medicine, etc.). The inaugural 2009 class was limited to 40 students. The 2010 class will have a program size of approximately 80 students.
Note that unless next year’s class is 160 students, SU will be considered a failure (of the polynomial kind?)