D-Wave Easter Spectacular
Look, I promise this will be the last D-Wave post in a while. But there have been two developments that, as Planet Earth’s primary D-Wave skepticism clearinghouse, I feel a duty to report.
First, Jason Pontin’s article in the Sunday New York Times has appeared. It’s not perfect, but to get in a description of quantum computing that was even somewhat accurate required a long, word-by-word and phrase-by-phrase battle with the editors of the business section.
Second, Umesh Vazirani sent me a document summarizing the skeptical case against D-Wave, which anyone coming to this blog from the Tech Review or New York Times might find helpful. (Hey, as long as you’re here, stick around for a bit!) I’ve posted Umesh’s criticisms below.
Finally, Happy Easter from all of us here in the shtetl!
Reasons To Be Skeptical About D-Wave’s Claims
by Guest Blogger Umesh Vazirani
1. An Unconvincing Demo: D-wave’s demo consisted of a computer in a box that could solve simple problems. We have no way of knowing whether the computer in the box was an ordinary classical computer or a quantum computer. For the problem the computer solves — finding ground states for 16 bit Ising problems — a classical computer would work just as quickly. This demo is the only public evidence D-wave has presented in support of its claims.
2. A Physics Breakthrough?: Achieving 16 coherent superconducting quantum bits would be quite a breakthrough. Physicists working on superconducting qubits have not been able to achieve more than two coherent quantum bits in the lab. In the absence of evidence from D-Wave that their 16 qubits are coherent, scientists are understandably skeptical. If D-Wave’s qubits are not coherent, as many scientists suspect, their computer would be classical, not quantum. This would still be consistent with the results of the demo, since the decohering qubits would act like classical random bits, and the adiabatic computer would act like a classical computer implementing simulated annealing, which would be quite fast for a small 16 bit Ising problem. It is possible to test the quantum states of D-Wave’s computer for coherence, but Geordie Rose’s statements suggest that no such tests have been made.
3. Claims of Big Algorithmic Breakthrough Without Evidence: 16-bit quantum computers are useless from a practical standpoint because they can only solve very small problems that could just as easily be solved using a classical computer. Thus, D-Wave’s demo, even if it really was a quantum computer, will only be practically useful if the technology will scale to the larger problems that cannot be solved with a classical computer. Unless D-Wave has made a major algorithmic breakthrough as well as a major practical one, however, D-Wave’s computer, even if implemented with thousands of qubits, will not provide a speedup over classical computers. D-Wave does not implement a general purpose quantum computer, only one that can implement adiabatic optimization. They wish to use it to solve the Ising model, which is thought to be beyond the reach of classical computers, but there is no known efficient algorithm for solving the Ising model using this adiabatic approach. It is possible to achieve a quadratic speedup for unstructured search problems using adiabatic optimization, but that result requires an ability to tune the rate of the adiabatic process — something which appears to researchers to be extremely hard if not impossible for the Ising problem. Geordie Rose’s public statements suggest that he doesn’t understand this issue, which makes computer scientists skeptical that any breakthrough has been made.
To summarize: For D-Wave to achieve a practically useful quantum computer using their technology, they would have to have made a breakthrough in physics, as well as a breakthrough in the design of their algorithm. Scientists are skeptical both because D-Wave has failed to provide any supporting evidence, and also because their public statements suggest a lack of understanding of the issues involved.
You might ask why researchers are putting so much energy into debunking the D-Wave hype. One reason is that QC researchers feel a responsibility to the public to not overhype quantum computers. Quantum computing is an exciting field that has caught the imagination of the public. This is a good thing. But if the quantum computing effort starts to mingle fact with fiction, then the entire effort loses its credibility.
Another reason is that D-Wave’s unsupported claims are undermining the efforts of the researchers who are working very hard on these problems. It’s as if there was a new biotech company claiming to be at the brink of a revolutionary cure for cancer. If it is true, it is great, but if it’s not, then it undermines the efforts of the legitimate cancer researchers.
Follow
Comment #1 April 7th, 2007 at 7:56 pm
This would still be be consistent with the results of the demo
At the moment, I do not see that it is consistent with the demo. The demo solved Sudokus. How do you do that in any meaningful way with only 16 Ising bits or qubits?
I don’t quite know that the Sudoku solver was fake. What I can say is that I can’t think of a meaningful use of 16 Ising qubits for this problem. Can anyone else? I am not convinced by Scott’s answer of “who knows?”, if he means that we can’t know without an explanation from Rose. Scott, would you still give that answer if it was 2 qubits instead of 16?
BTW, Scott, Umesh’s nice guest post would look even better with a bit more formatting, i.e., paragraph breaks before the numbers.
Comment #2 April 7th, 2007 at 8:06 pm
Greg, maybe the problem was to complete a Sudoku puzzle that was already partly filled in? I don’t know and, to tell the truth, I don’t really care.
Sorry about the formatting — WordPress is unbelievably horrible that way (it actually rewrites your HTML and screws up the paragraph breaks). It’s fixed now.
Comment #3 April 7th, 2007 at 8:21 pm
Greg, maybe the problem was to complete a Sudoku puzzle that was already partly filled in?
You’re saying, maybe they had 9 x 9 Sudokus with 75 squares filled in and the Orion only provided the last 6? Yes, then it might have been a real demo of 16 qubits. Somehow I doubt that the Sudokus looked that lame. Maybe one of the reporters can say what the Sudokus looked like.
I am really struggling with Umesh’s statement, “We have no way of knowing whether the computer in the box was an ordinary classical computer or a quantum computer.” Suppose that I “demonstrated” a quantum computer with 5 qubits that can factor 60-digit numbers. Would you or Umesh then say that you have no way to know whether I used a classical computer? Of course you would have a way to know!
Comment #4 April 7th, 2007 at 9:29 pm
Greg, you can see for yourself here.
Comment #5 April 7th, 2007 at 9:32 pm
Umesh’s document is an excellent summary of the important reasons for skepticism regarding D-wave. The first two points are the most crucial.
I suppose we can now wait and see if in two years D-wave will achieve a much larger hundreds-qubits device as promised.
Comment #6 April 7th, 2007 at 9:57 pm
“And the quantum computer spits out the answer. There it is.”
A computer with 16 Ising qubits spits out an answer with 54 digits from 1 to 9. Truly amazing. It would be interesting to interview the people at D-Wave who did the Sudoku solver.
Comment #7 April 7th, 2007 at 9:59 pm
hi greg, hi scott, hi all!
i’ve been thinking about the sudoku solver all the time since i’ve seen this video [1].
so apparently we learn two lessons, one theoretical and one experimental.
theoretical: a 9×9 sudoku problem seems to fit into a 16 ising qubit setup, so you can represent one of the 6,670,903,752,021,072,936,960 possible solutions [2] with a 16 qubit setup (by the way, 2^16=65,536).
experimental: if you push the ‘quantum solver’ button, it takes five seconds
* to send the problem over the internet to the superconducting quantum computer
* to adjust the setup to the constraints of the received sudoku problem
* to run the adiabatic algorithm and
* to send the results back to the demonstration
so – four seconds later – you can generate a NEW sudoku problem and repeat the complete procedure in another five seconds.
links
[1] http://www.youtube.com/watch?v=VQul2asgXbw
[2] http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
Comment #8 April 7th, 2007 at 10:08 pm
theoretical: a 9×9 sudoku problem seems to fit into a 16 ising qubit setup.
This theoretical lesson is mathematically false by Nayak’s theorem (1999). 16 qubits cannot hold more than 16 bits. 6,670,903,752,021,072,936,960 > 65,536, so it’s impossible.
Comment #9 April 7th, 2007 at 10:22 pm
“And the quantum computer spits out the answer. There it is.”
“It’s green!” [1]
Unfortunately, the official video doesn’t show the SudoQ GUI…
[1] http://www.dwavesys.com/event-video.php
Comment #10 April 7th, 2007 at 10:50 pm
Scott, the ny times article misquotes your statement about roast beef sandwiches, as you originally said solving optimization problems, and the ny times article just said “problem-solving”, which led me to the following calculation.
If we assume this is correct, thats 473 Calories (with cheese, not my preference). According to this, adults need 100W. So our sandwich of 4.73×10^5 cal = 1.98×10^6 J could run the body for about 5 and a half hours. Then if we also assume this is correct, (I think this is the biggest assumption yet), then the sandwich provides about 1.98×10^18 operations, which is pretty impressive. Not a bad upper bound for a sandwich.
Comment #11 April 7th, 2007 at 11:14 pm
Thanks, Cody! However, there’s a gap in your analysis: if you look closely, the calorie estimate was specifically for a roast-beef sandwich with cheese. Furthermore, it’s known that with a 16-qubit computer like D-Wave’s, there’s no point in doing more than ~216 = 65,536 operations. Combining these facts with your result, and assuming that a roast-beef sandwich without cheese is not more useful than D-Wave’s machine, we deduce that in a typical roast-beef sandwich with cheese, at most a
65,536 / (1.98×1018) ~ 3.31×10-14
fraction of the calories can come from the bread and roast-beef: all the rest comes from the cheese. So next time you hanker for roast-beef at your neighborhood deli, ask for no cheese — it won’t only make your rabbi happy, but also your CS professor and your dietician.
Comment #12 April 7th, 2007 at 11:29 pm
Plus I don’t like cheese much anyway—makes up for my lack of a rabbi…
…and CS professor, and dietician come to think of it.
Comment #13 April 7th, 2007 at 11:35 pm
In the context of the way the articles quote you, I had imagined two other problem solving applications of the sandwich as well: the first was the direct application of the sandwich to solve the classical hunger problem, and the second was to use the sandwhich as payment to an expert who could solve more specific problems for you, (note that the utility of this is directly related to the chosen expert’s relation to the first problem: hunger). In either case, the sandwich appears at least as powerful as the D-Wave machine.
Comment #14 April 7th, 2007 at 11:44 pm
Excellent observation, Cody! However, one should remember that the reduction also works in the other direction: with its 16-bit machine, D-Wave managed to solve the problem of raising $44m in venture capital, which at $5 per sandwich works out to 8.8 million roast-beef sandwiches, which would presumably solve the classical hunger problem as well.
Comment #15 April 8th, 2007 at 12:01 am
Ha ha ha ha, that is great!
Comment #16 April 8th, 2007 at 5:10 am
some random comments
* For anyone who doesn’t have a Flash plug-in and would like to see the sudoku solver, there is a SudoQ photo on Flickr.
* Furthermore, it’s known that with a 16-qubit computer like D-Wave’s, there’s no point in doing more than ~2^16 = 65,536 operations.
In case of D-Wave, wasn’t it more like 64,000 calculations simultaneously (according to CBS and The Telegraph)? 😉
* The February 2007 issue of Technology Review (German edition) quoted Geordie Rose: “the current test calculations take a millisecond and deliver the correct result in 90 percent of all cases” (“Die derzeitigen Testrechnungen dauern eine Millisekunde und liefern in 90 Prozent der Fälle das korrekte Ergebnis”, TR02/07, ‘Mimosenhafte Superrechner’, by Ralf Krauter)
Comment #17 April 8th, 2007 at 5:12 am
i’ve found two d-wave related papers on quantum adiabatic computation.
“simulated quantum computation of molecular energies”
quant-ph/0604193, 10.1126/science.1113479
geordie rose emphasized in his interview with HPCwire that quantum simulation is ‘the main application where “exponential” improvements occur using quantum computers over classical ones’. i wonder why this important subject wasn’t mentioned at the orion demonstration?
“thermally assisted adiabatic quantum computation”
cond-mat/0609332
it seems that the statements concerning the speed-up have been altered between the first and the second version of this pre-print.
the first version of this preprint stated that TAQC ‘can provide O(\sqrt{N}) scaling for the unstructured search problem, with no a priori knowledge of the energy spectrum, in the absence of quantum error correction, and in the presence of an Ohmic thermal environment’. the conclusion ‘the effects of thermalization […] are benign’ is also missing..
Comment #18 April 8th, 2007 at 5:56 am
Congratulations on getting into the NYT, Scott! I expected you’d be in there some day, never figured it’d be the “business” section though…
-anonymous layperson
Comment #19 April 8th, 2007 at 6:43 am
Scott says: D-Wave managed to solve the problem of raising $44m in venture capital …
Now we’re tiptoeing up to a challenging question: how strong, really, is the business case for QIT?
Regardless of what people on this forum may believe, what the business community sees is the case made in the NYT.
Comment #20 April 8th, 2007 at 9:02 am
Please don’t feel you need this to be your last D-Wave post in a while. I’m finding this all very interesting, informative, and exciting, and I’m sure many of your readers feel the same way. When there’s something on the topic to report, please report it!
You’re fulfilling a key role for an academic — providing skepticism for the public on matters that require non-trivial knowledge of the underlying science. It’s good for the public, and good for our field. Thank you.
Comment #21 April 8th, 2007 at 1:49 pm
@Scott or Umesh
In #2 when referring to 16 coherent qubits is Umesh referring to 16 maximally coupled/entangled qubits? For example, each qubit coupled/entangled with every other qubit and not coupled to the environment? Because the Orion chip only has nearest neighbor and next nearest neighbor coupling as stated in the demo. Is the sticking point here a difference in the definition of qubits (i.e. maximally entangled vs partially entangled)? Also, what is the way to check coherence between superconducting qubits? Is it just to see if they can be prepared/measured in an entangled state? Just curious. I think I am currently understanding coherence/coupling/entanglement as synonyms, which maybe an error on my part.
Also in #3, in regards to tuning the rate of the adaibatic process, doesn’t the fact that the couplings between the qubits are tunable, in effect, allow you to control the rate (to a certain precision) of going from one ground state to the other? Or am I misunderstanding something?
Thanks in advance for your response.
Comment #22 April 8th, 2007 at 3:03 pm
Chris: Nothing Umesh said depends directly on the details of the architecture (nearest-neighbor, etc). By “16 coherent qubits,” I think he just meant 16 qubits in a state close enough to a pure state that one can start doing genuine quantum computations.
In particular, we know that if the qubits are noisier than a certain threshold, then genuine quantum computation is impossible — in the sense that any computation you can do can be simulated efficiently by a classical computer. And D-Wave hasn’t released any evidence whatsoever to indicate which side of that threshold they’re on.
There are lots of ways to check whether qubits are in a coherent state, and yes, some of them involve directly testing for entanglement, which is known to disappear if the qubits are sufficiently noisy. Other tests could involve quantum state tomography, or doing a quantum computation that would only work if the qubits were close to coherent. I have no idea which tests are best suited to superconducting qubits (as opposed to other kinds of qubits).
Yes, the fact the qubits are tunable does let you control the rate of the adiabatic algorithm. I think Umesh’s point was that, to get a Grover speedup for structured search problems, you apparently have to control the rate in a way that depends on the particular problem instance — and given a problem instance, we don’t know of an efficient way to compute the right rate for that instance.
Comment #23 April 8th, 2007 at 3:18 pm
Because the Orion chip only has nearest neighbor and next nearest neighbor coupling as stated in the demo.
If they were nearly perfect qubits, then nearest neighbor coupling would in principle be enough to achieve any entanglement you please with all 16 qubits.
Is the sticking point here a difference in the definition of qubits
The sticking point is the difference between great, low-noise qubits, and sucky qubits that are so noisy that they aren’t really qubits at all, they are just bits. It is true that slightly noisy qubits can support some entanglement, just not quite as much as perfect qubits. However, if the qubits are noisy beyond a certain threshold, then the entanglement is gone entirely.
More precisely, entanglement is an extended form of correlation. A noisy quantum state that can be constructed using only classical correlation is called separable. The separable states are a region inside all of the states. They have a boundary, the barely separable states. Beyond that boundary, the states are “more correlated than is classicaly possible”; they are inseparable or entangled. Noise restricts the possible states of the qubits more and more to the middle. If there is enough noise, then the reachable states are entirely inside the separable region, which means therefore that there is no entanglement at all.
Scott, Umesh, and I have found different grounds for skepticism of what D-Wave is doing. Scott emphasizes that Rose has made hash of complexity theory, even though complexity theory is fundamental to understanding why quantum computing is important. (In fact, Rose did not mind quoting Scott on that, as long as it sounded good for him.) Umesh endorses Scott’s objection, and adds to that the objection that there is no evidence that D-Wave’s qubits are any better than anyone else’s superconducting qubits, and therefore not nearly good enough for any of their claims.
I endorse both Umesh’s objection and Scott’s objection. But at the moment, I have another objection. The most memorable part of the D-Wave demo was their Sudoku “quantum solver”. I do not see how you can solve Sudokus with just 16 qubits, much less 16 Ising qubits. If there is no way to do this, then their Sudoku demo was either substantially fake or entirely fake. It a basic question of trust that is arguably preliminary to a discussion of complexity theory or noise. Complexity theory and noise are hard topics for which you could just say that they haven’t learned enough theory. But they do know how they solved the Sudokus, they just haven’t told anyone else.
I don’t know how they solved the Sudokus either. Maybe there is a legitimate method. Let me ask anyone reading this: Is there a plausible way to solve Sudokus with 16 Ising qubits?
Comment #24 April 8th, 2007 at 3:23 pm
Scott said: Umesh’s point was that, to get a Grover speedup for structured search problems, you apparently have to control the rate in a way that depends on the particular problem instance — and given a problem instance, we don’t know of an efficient way to compute the right rate for that instance.
I don’t think that is what was meant. When minimizing an unstructured function with F(x)=0 for all but the target, which has F(target) = -1, we know what the optimal cooling schedule is, regardless of the specific target value. First you cool rather quickly, then you slow down considerably at some critical moment, after which you finish by going quickly again. When exactly that critical moment occurs only depends on the size N of the search space and the fact that there is only one minimum F(target) = -1. This way, one can find the target in time sqrt(N), and we know of course that that is also the best possible speed up for this problem.
Comment #25 April 8th, 2007 at 3:27 pm
OK then, can you elucidate what he meant?
Comment #26 April 8th, 2007 at 4:58 pm
Thanks again for the comments. I think I understand better now. Though I do have one more question I hope Greg can answer.
@Greg
So how is it that you can construct any 16 qubit entangled state with only nearest neighbor coupling? I’m having trouble grasping that.
Thanks again.
Comment #27 April 8th, 2007 at 5:05 pm
Chris, I can answer that question for you. If you have arbitrary nearest-neighbor coupling, you can use that to couple any two qubits, by
(1) repeatedly applying nearest-neighbor swap operations to move the qubits you want to couple next to each other,
(2) coupling them, and
(3) applying more swap operations to move the qubits back to their original locations.
Furthermore, it’s known that with two-qubit couplings, you can approximately apply any unitary operation (and hence prepare any state) — that follows from the Solovay-Kitaev Theorem.
Comment #28 April 8th, 2007 at 5:50 pm
Wow… thats pretty rad! And very easy to comprehend. Thanks again!
Chris
Comment #29 April 8th, 2007 at 6:07 pm
Greg said: I do not see how you can solve Sudokus with just 16 qubits, much less 16 Ising qubits
I was wonder why would the Ising qubits offer less computational power?
Comment #30 April 8th, 2007 at 6:41 pm
Why would the Ising qubits offer less computational power?
Because the computer only finds the minimum of an Ising Hamiltonian, so therefore any other problem would have to be recast as an Ising minimization problem with some loss of space efficiency.
Comment #31 April 8th, 2007 at 7:58 pm
OK then, can you elucidate what he meant?
I think that Umesh was referring to the fact that to get the quadratic speed-up for unstructured search problems using quantum adiabatic optimization, you have to be very precise in your control of the time evolution of the system. If you don’t have this precision, all bets are off.
More specifically, you have to be able to do the following (cf. Section 5 in arXiv:quant-ph/0206003):
Let H0 be the initial Hamiltonian and H1 the final Hamiltonian of your adiabatic algorithm. In the standard approach you interpolate between these two Hamiltonians using a time dependent Hamiltonian H(s) = (1-s)H0+sH1 where you go from s=0 to s=1 at such a rate that the system stays in its ground state, thus yielding a final state that minimizes the problem Hamiltonian H1. According to the adiabatic theorem, the right rate, at a given value s, is proportional to (roughly) the ‘inverse gap squared’ of the Hamiltonian H(s), where the gap is difference between the smallest two eigenvalues of H(s). The big question when analyzing quantum adiabatic computing is therefore almost always: “how big is my gap?”.
Okay. For an unstructured search problem over 2n=N items it is not hard to show that the gap equals gap(s) = (1+4(1-1/N)(s2-s))1/2. So, by going from s=0 to s=1 at a rate proportional to 1/gap(s)2 = 1/(1+4(1-1/N)(s2-s)), you obey the criteria of the adiabatic theorem and hence you find the correct minimum. If you integrate this rate 1/gap(s)2 between s=0 and s=1, you get a total delay proportional to N1/2, hence you have gotten yourself a quadratic speed-up. The practical problem is of course that for this approach to succeed, your control of the rate of evolution has to be really good, especially around the critical point s=1/2.
Comment #32 April 8th, 2007 at 8:12 pm
It seems that my sub and superscripts did not survive. It probably helps to know that in my previous email: H0=H_0, H1=H_1, 2n=2^n, (…)2=s^2 and (…)1/2=(…)^(1/2).
Comment #33 April 8th, 2007 at 11:56 pm
It is possible to test the quantum states of D-Wave’s computer for coherence, but Geordie Rose’s statements suggest that no such tests have been made
According to The Register Geordie Rose stated that D-Wave has ‘a large amount of supporting evidence that I am not going to release today because it is being submitted for peer review’.
Scientific American quoted him confirming plans to submit the results for peer review ‘at a major journal’. Also, the experts would be given ‘a chance to inspect the system’.
Comment #34 April 9th, 2007 at 1:14 am
‘a large amount of supporting evidence that I am not going to release today because it is being submitted for peer review’.
∃ arXiv
Comment #35 April 9th, 2007 at 1:30 am
Scottt says: In particular, we know that if the qubits are noisier than a certain threshold … then any computation you can do can be simulated efficiently by a classical computer.
Just as a clarifying remark, with regard to the devices of the above citation, if the gates are made noisy enough to allow classical simulation of the device, then the device’s performance is so crippled by that noise that the device cannot even simulate a classical computation—at least that’s what the article states.
Hopefully, there is a lot of room to improve this result!
If there is a more recent and powerful result, a citation would be very interesting and useful to me, and I suspect, to many.
Comment #36 April 9th, 2007 at 4:04 am
hi all!
scott, thank you very much for your blog! 🙂
i’ve some questions on quantum adiabatic computation…
quantum simulation
geordie rose stated on his blog about the orion processor that ‘the reason why we don’t think we can run quantum simulation […] in general is that X+Z+ZZ isn’t universal for BQP’
could someone please make some comments on this statement? what are the computational complexity classes for quantum simulation of quantum systems and classical simulation of quantum systems?
Ising model
an ability to tune the rate of the adiabatic process — something which appears to researchers to be extremely hard if not impossible for the Ising problem
are there some papers on the subject of quantum adiabatic computation and Ising model?
the robustness
the robustness of quantum adiabatic computation seems to be a much discussed topic… geordie rose stated on his blog that ‘AQC approach is naturally shielded from errors in a way that the gate model isn’t’.
are there some peer-reviewed results on quantum adiabatic error correction?
degenerated ground state
geordie rose stated on his blog that ‘the two theoretically degenerate solutions are each obtained roughly 50% of the time is evidence that the control we have over the machine language parameters is pretty good’.
so if the energy minimum of the final hamiltonian is twofold degenerated, the quantum adiabatic protocol drives the initial ground state into a quantum state which is a superposition of two corresponding basis states.
|psi_f> = 1/sqrt(2) ( |psi_min_1> + |psi_min_2> )
the projective measurement results each of this states |psi_min_i> with the probability prob_i=1/2. is this correct?
thanks!
Comment #37 April 9th, 2007 at 7:36 am
In general is that X+Z+ZZ isn’t universal for BQP.
Well actually the statement is that X+Z+ZZ probably isn’t universal for adiabatic quantum computation. Certainly if you have Hamiltonians with X,Z, and ZZ terms which you can turn on and off to produce quantum gates then this is universal (X and Z generate SU(2) and you only need any nontrivial interaction between two qubits to get universality once you have single qubit gates.) But in the adiabatic model you don’t get to apply these gates directly. And as of yet there is no proof of universality of these interactions with adiabatic quantum computation. Indeed there is even some evidence that quantum computations with these interactions is not universal because it turns out that Hamiltonians with these interactions are (or can always be easily transformed into) what are called a stoquastic Hamiltonians. There is evidence that stoquastic Hamiltonian’s are easier to simulate (and by easier I don’t mean easy!) Some of this evidence is in quant-ph/0611021.
Comment #38 April 9th, 2007 at 7:41 am
are there some papers on the subject of quantum adiabatic computation and Ising model?
Quite a few. A start is quant-ph/0108048. A more recent paper is quant-ph/0512170. However, this being said, I can pretty confidently tell you that as of this moment, no one knows how to make adiabatic quantum computation fault-tolerant (in either its original form for building quantum algorithms or in its newer incarnation as a universal quantum computer.)
Comment #39 April 9th, 2007 at 7:54 am
Greg Kuperberg, here is an elegant algorithm to solving a Sodoku with a 16 qubits quantum computer.
Comment #40 April 9th, 2007 at 9:57 am
hi dave!
thanks!
by the way, i thought you’ve been working on the subject of quantum adiabatic error correction? or am i confusing something?..
Comment #41 April 12th, 2007 at 1:29 am
http://scienceblogs.com/principles/2007/04/shtetl_of_the_times.php
# 3 | Jonathan Vos Post | April 11, 2007 11:37 AM
New York Times, April 1, 2008:
Roast Beef Sandwich Computer: DNA-based Quantum Computer In 2nd Round Venture Capital
After dazzling NASA with a demonstration that solved the Dark Energy-Dark Matter-Dark Entropy equations to 22 decimal points accuracy, the start-up Earlofsandwich.com demonstrated their prototype Roast Beef Sandwich Computer capabilities further.
It successfully applied hybrid DNA-Quantum computing technology to dazzling speeds in a set of benchmark tests:
(1) The 5-dimensional Sudoku Puzzle;
(2) computing human brain tomography based on horseradish peroxidase-stained neuron photographs;
(3) automated theorem proving of Geometry’s Ham Sandwich Theorem;
(4) Retrodiction of the “Pick a Number Win a Book” conundrum;
(5) Using Twistor Theory to determine the plotline of Bon Dylan’s “Tangled up in Blue”;
(6) Predicting the NCAA College Baketball rankings based on Gatorade extrapolation metrics;
(7) Using the Reagan Institute Trickle-down Econometric model to prove that there is a way out of Iraq, but it is not Godel-decidable;
(8) Spoofing the Google page-index algorithm to boost Scienceblogs to the #1 ranking in the world.
“This one doesn’t look like hype,” said Scott Aaronson, a theoretical computer scientist at the Institute for Quantum Computing at the University of Waterloo in Canada. “Previous Quantum Computer demos were suspect, based on the Penrose-Conway-Turing Loop Quantum Gravity surreal-number matrices.”
“Let’s see them top this in Bangalore” said a grizzled Silicon Valley Venture Capitalist.
Comment #42 April 12th, 2007 at 2:11 am
According to The Register Geordie Rose stated that D-Wave has ‘a large amount of supporting evidence that I am not going to release today because it is being submitted for peer review’.
According to CBC News Herb Martin (D-Wave CEO) stated that the company has not published its findings because they are seeking patents on their technology.
At the same time he announced that if there’s any scientists out there who want to take a look at what we’re doing, they would be our guest.
Comment #43 April 16th, 2007 at 1:08 pm
Hello,
Would you consider maybe taking a look at the Wikipedia entry on D-wave? The article on D-wave demonstrates such an utter lack of skepticism that I feel it constitutes a violation of NPOV. The whole thing reads like a slightly toned-down press release, and the only part that suggests there exists anywhere active skepticism the D-wave works is the following sentence, offered without citation:
What?
I do not think the current content needs to go away, but I think the wikipedia entry would benefit from the addition of a “criticism” section by someone familiar enough with the standing criticisms to state them fairly. Meanwhile the article links to “adiabatic quantum computation”, but no article by that name exists on wikipedia and there are standing requests on the Talk page for someone to explain exactly what this means. Basically the wikipedia coverage of this issue is badly in need of the kind of informed perspective that this blog discussion comprises…
Comment #44 April 16th, 2007 at 8:25 pm
Would you consider maybe taking a look at the Wikipedia entry on D-wave?
Greg? 🙂