More on the TR interview April 6, 2007
Posted by Geordie in General.trackback
Back from choking some folks out. Gots ta represent.
OK in this second installment of Geordie’s Easter Weekend Vent-a-thon, I’d like to offer some food for thought related to Scott Aaronson’s latest blog post. Specifically I’d like to take him to task on his rationalization of why he is so crusty, the most recent examples of which are:
1. I asked Geordie Rose (the founder of D-Wave and sometime commenter on this blog) twice for actual information about the speedup D-Wave claimed to be seeing over classical algorithms, and he never provided any.
I don’t remember actually ever receiving this request from Scott, so I apologize for not being timely in my response. For the record, here is what I have said, in some of the posts here, several interviews, and the demo itself: (A) Orion is roughly 100x slower than state of the art algorithms running on a $1000 PC for solution of small Maximum Independent Set problems, and (B) the only way scaling can be extracted is empirically, and we can’t build big enough systems (yet) to answer scaling questions.
2. Instead of answering my and others’ technical questions, D-Wave decided to attack academic science itself. Here’s what Ed Martin, the CEO of D-Wave, told an interviewer from ITworld: “Businesses aren’t too fascinated about the details of quantum mechanics, but academics have their own axes to grind. I can assure you that our VCs look at us a lot closer than the government looks at the academics who win research grants.” The track record of companies that engage in this sort of behavior is not good.
I can’t see how you can argue that we haven’t tried to answer technical questions. I go out of my way to answer any questions that are asked. If you have any let me know, I’ll answer them if I can.
Casting Herb’s (not Ed’s-there’s something ironic there) statements as attacks on academic science is ridiculous. The above statement has been taken WAY out of context. The original question was how our investors do due diligence on the company without any peer reviewed publications, which is a fair question. Herb’s answer–which is a true statement, whether or not you like it–is that financing a company like this puts us under levels of scrutiny far beyond the norm, either for a start-up company or a big research grant. Herb’s statement isn’t an attack on academic science. It’s that the bar we have to get over to raise cash is higher than it is for other start-ups or academic groups.
I don’t know what you mean by that ominous last statement. You mean like Intel, Microsoft, IBM, GE?
3. I read article after article claiming that quantum computers can solve NP-complete problems in polynomial time. I reflected on the fact that a single one of these articles will probably reach more people than every quantum complexity paper ever written.
This is probably true, although only 50 people in the world understand what you just said. And note that I have never said that, and in fact go out of my way to state a point of view that is very similar to Scott’s.
4. It became clear, both from published interviews and from talking to Jason, that D-Wave was doing essentially nothing to correct journalists’ misconceptions about what sorts of problems are believed to be efficiently solvable by quantum computers.
While I personally find questions about efficiently solvable problems fascinating, these issues are remote from what we are actually doing here.
This is worth emphasizing, because I thought it was obvious, but it turns out alot of people don’t get this. Most of the poorly thought out comments related to what we’re trying to do have come from theoretical computer scientists, who assume that the things they hold dear are likewise treasured by everyone else. Because they worship efficiency, they have assumed that’s the objective of our projects, when I have repeatedly said it’s not.
Here is what I care about: (A) getting to the same level of accuracy as state of the art heuristics in less time and/or (B) given an allotment of time, produce a more accurate solution than state of the art heuristics, for high-value discrete optimization problems that people actually care about.
When people ask what the systems we’re building are for, I tell them that they are for solving discrete optimization problems (which they are). For someone for whom complexity theory is the fulcrum of the universe, this might be interpreted as a statement that we plan to exactly solve all discrete optimization problems, efficiently. For most people who have to deal with these types of problems in real life, the questions arising have a slightly different flavor: “Can you beat our simulated annealing approach?”, which seems like a lot more intelligent question.
[...] (4/6): Geordie Rose has responded to me. A few responses to his [...]
“only 50 people in the whole world understand what you just said”.
Are you kidding me? anybody with an appreciation for some basic math can work out the nessecary theorems in a couple weeks of full time calculation. Now this doesnt mean that one is deeply entrenched at the bleeding edge front of the field, but really its not that hard to “get it” if you put your brain to the matter, you know? Just because the masses want to agglomerate their priase on a few celebrated researchers rather then the thousands of people who have read the core books regarding quantum computing (a commonly touched on undergraduate subject these days accross the world by the way, whether one likes to think so or not) doesnt mean that people dont understand what an NP hard problem entails and how one goes about (not) solving it. If you have a ‘toy’ machine that works, then forget about defending yourself and insulting peoples intelligence and just go about scaling the damn thing. Negative corporate image will really just go away really fast once you offer greedy corporations massive speedups (money) and your pundits will eat their ‘useful’ theory based phd’s with ketchup. it seems rather you are concentrated on image which suggests something alternative.
Helpful Hinter: By saying that it’s easy to understand complexity theory and quantum computation and how they are related with some basic math you are helping to prove my point. I have spent enough time communicating these matters to a wide variety of folks to know your core assertion above is incorrect.
There are a lot of subtle issues that are very relevant to explaining what we are doing, including instance dependence, worst-case vs. average case scaling, etc.; alot of them aren’t even about QM/QC.
Here’s a question for you, see if you can answer it with basic math: Given an AQC operating on average case Two-D Ising model in a magnetic field problems in the sweep speed regime midway between the adiabatic and the Landau-Zener limit, what is the computational scaling? Bonus points: Do it for sweep speed as a general function of time.
The only part of your post I agree with is that the proof is ultimately in the pudding. However on the way to this end we need to engage end-users, and this requires that we tell people what we are doing. If someone-in a widely read article-says something that just ain’t true, I see value in presenting my argument as to why those people are wrong.
What is Orion frequency? 1KHz? 1MHz? 1GHz? or 1THz?
could ever quantum computer simulate universe if QC realy would be so powerfull like in teory? I think no.
To drug research dont necessary to have quantum computer sufficient (enough) and conventional computer, maybe just need more power (thousends petaFLOPS). Whats about qountum proccess simulation, who need it? It is all the same not exacly like in real world.
A littele philosophy: What if the universe made that the all “God power” concentrate in only of us Univese?
Hi Geordie,
I’ve been thinking about the D-Wave claims for a while now, and have a few questions on the algorithmic side (for now I’ll assume you’ve managed to build a QC that maintains coherency throughout its operation, and is hence actually operating as a QC):
1.) What algorithm are you using to obtain the speedup for discrete optimization? Is it essentially an adiabatic version of Grover’s algorithm? Or have you developed a new (unpublished) quantum algorithm that uses some hitherto undiscovered mechanism to outperform classical algorithms?
2.) If you’re using a Grover-like algorithm to obtain your speedup (or rather, your planned speedup), you can at best hope for a quadratic speedup against an equivalent classical algorithm. If this is the case you may be able to outperform the best current heuristics-based optimization programs. However, I can’t see how a “mere” quadratic speedup can likely be economical. Let’s say you build a machine that can solve an instance of some problem in 1 second, and that same problem takes 5 seconds to solve on a 100-node cluster. How do you know that your QC is going to be a more economical solution than just buying another 400 nodes for the classical cluster? (Obviously this argument makes plenty of assumptions, for e.g. about the scaling of current state-of-the-art optimization algorithms on clusters…
I’d be interested to hear your thoughts on these issues.
Regards,
Joe
How has be found the universe ? In universe space is a lot of globules, that is truly elementar and it size is 10^(-50). All universe is made out of this globules. This globules is very very very close each over, and this globules spining in dance with over globules, mading up increadible combination, and so involved that globules combination restrict new laws of some more big combinatons maded up from above combinations. More new and bigger combinations become for example fotons or quarks or elektrons or somthing like what. So the all universe is maded with globules, which dont have any fields and between globules no friction, so they make a lots diferent and unice combination, thats after gives to us quantum and later classic phisics. So nobody can simulate globules, nobody!
Hi Joe,
1. There are several different algorithms that we have run so far. The system itself allows the qubit biases, coupler strengths, and single-qubit barrier heights to be independently controlled. Thinking about the system like Grover search is not the right mental picture, because in (adiabatic) Grover search you’re looking for one state (which is “right”), whereas in the 2D Ising model in a magnetic field the answers are ranked worst–>best as energies decrease. Also in the adiabatic grover search the types of states that the system evolves through don’t look like the states of our system.
One of the algorithms we’ve developed, which I particularly like going forward as the system scales up, we haven’t published yet. We probably will though.
2. The types of problem we’re trying to solve have structure which can be exploited classically to make the scaling “more favorable”. For example, the best classical algorithms for Maximum Independent Set have worst case scaling like O(2^{0.2N}). If you were to take an MIS problem and directly try to solve it with something quadratic, you might get O(2^{0.5N}) which is worse! One of the things that has been clear for a long time is that novel ideas for integrating what a QC does into the best classical algorithms is necessary for using a machine which might only give a quadratic speed-up. If you could get a quadratic speed-up on the best known classical algorithms (which requires new algorithms), that would satisfy our objectives (faster & same accuracy or same time & more accurate).
Another point to keep in mind on the “economical” side: these machines consume almost no power and are very easy to program. I think there are compelling benefits to using these things even if the brute strength performance was comparable to (or maybe even worse than) large clusters.
Also I would mention that I believe that trying to predict how a real QC will actually scale is very hard. We take the attitude of “built it, measure it, see what happens, fix it, build it, measure it, see what happens”, etc.
Hope this helps!
I realy dont believe in quantum computer sucses, except that quantum computation maybe can give efective power by combyning with superconductors.
does realy adiabatic quantum computer is worse than normal quantum computer with gates? Why so mane sciesciests from all worl want to built quantum computer, but you say that quantum computer in any case can not break RSA code? Does they are so stupid? Optimists, he?
What is diferent between Shor’s faktorization algoritm and Grover’s algoritm? Simple: Grover’s algoritm give answer with better probability than Shor’s faktorization algoritm. If Shor’s algoritm gives answer with probability N, then Grovers algoritm gives answer with (log N)^1.5 better probability.
I agree with Helpful Hinter, both about the broadness of the audience that understands the basic concepts of NP-complete and about your image-before-research sort of presence. Geordie, the difference between you and IBM researchers is that IBM researchers tend to come across more as researchers concerned about science rather than businessmen concerned about image. To give you the benefit of the doubt, you are from a much smaller company, and so to raise funding is much different and you are forced to be concerned with the image. Even still, you don’t seem to revert back to the scientist type when you get more involved in the science, like with all these online discussions, where it is primarily scientists, not investors whom you address. Also, to paraphrase bill nye’s mantra, you’ve made extraordinary claims which demand extraordinary evidence; while some of the evidence you have presented appears extraordinary, none of it is conclusively so.
Geordie,
RE -”For the record, here is what I have said, in some of the posts here, several interviews, and the demo itself: (A) Orion is roughly 100x slower than state of the art algorithms running on a $1000 PC for solution of small Maximum Independent Set problems, and (B) the only way scaling can be extracted is empirically, and we can’t build big enough systems (yet) to answer scaling questions.”
I’d encourage you to get more specific in quantifying what you have both in results and error tolerance{bounds of accuracy and systems/ chip reproducibility of tested “passing” chips].
You seem to skip out on quantifying & benchmarking [not as intellectually appealing as NP complete and related algorithmic arguments], as if lack of preparation now will not have technical ramifications later in understanding the much more difficult scaled (and noisier) needed large arrays for real markets.
If your present crutch is only stating “empirical results later are the only test”, you hardly know now, what you need to succeed in implementation of the hoped for competitive larger product.
Characterizing both performance metrics quantitatively, error tolerances, and reproducibility even in the present technology - by comparing 3 systems equivalence of results, will later prove a critical need.
Wrestling does not count here, as brute force empty arguments will do little to address the harsh realities of the intended performance marketplace.
Scott is far more correct than you care to admit to.
Haha, that surname guy is so funny
Hi Mark,
We do a lot of internal benchmarking of the sort you’re referring to. I agree that it is very important to do this. Having an empirically driven design cycle requires capture and analysis of as much data as we can.
You seem to be equating what we publicly release with what we internally generate. You must understand that there’s a difference.
By the way I don’t think Scott has been advocating having us increase the volume and analysis of our internal data. I don’t understand your last point. His main issue is that he wants either (a) public dissemination of that data or (b) that we shut up.
While I sympathize with his point of view, I don’t think either approach makes sense for a start-up.
cody: As much as I like Bill Nye’s fashion sense, “extraordinary claims require extraordinary evidence” is quite a bit older than the science guy. Here’s some reading:
http://www.findarticles.com/p/articles/mi_m2843/is_2_29/ai_n13628918
Re. your comment that I come across more like a businessman than a scientist: Considering that this is a business, I guess this is a compliment? Thanks?
Thank you for the response, I discovered shortly after posting that Bill Nye was a student of Carl Sagan, and that it was he in fact who popularized the phrase. I had never even heard of Marcello Truzzi, and I have never read much about Laplace, nor Hume, although I would like to (plus I’m from a Nye sort of generation, rather than Sagan), but it is fun to know the evolution of the idea now.
Additionally, the buisnessman comment was neither meant as compliment nor insult; I simply meant to highlight what appears to me as the cause of much skepticism towards your company. You can take it however you please.