Quantum-Effect-Demonstrating Beef
Update (May 25): See my Q&A about D-Wave’s new announcement at Forbes.com.
Update (May 26): See also this very helpful Quora post by Dave Bacon, who says mostly the same things I did (though it always sounds better when he says it!)
Clearly, there hasn’t been enough controversy on Shtetl-Optimized this past week. But I have just the thing to fix that: a new D-Wave post!
For three days, people have been sending me the news by land, sea, and air that D-Wave just published a paper in Nature, describing evidence for quantum annealing behavior in a system of eight superconducting flux qubits. The paper itself is behind a paywall, but the more detailed Electronic Supplementary Material is available for free (see also D-Wave’s blog post). As usual, my readers apparently expect me to render an instantaneous opinion.
But for the first time in the history of major D-Wave announcements, I’m unable to do so. For D-Wave is finally doing the very thing that I and others have been begging them to do for years: that is, directly addressing the question of whether their systems actually exploit quantum effects, or just perform classical simulated annealing. In the new work, they apply an annealing operation to eight coupled qubits arranged in a 1D chain, then plot the probability of a particular basis state as a function of time, by running the experiment over and over and stopping it at various intermediate points. They then look at the dependence of the probability-versus-time curve on a third parameter, the temperature, and claim that they can explain the curve’s temperature dependence by a numerical simulation that assumes quantum mechanics, but not by one that assumes classical simulated annealing.
To be clear, an eight-qubit spin chain with a quantum-mechanical temperature dependence is still a very long way from anything commercially useful (and it’s notable that, now that D-Wave has happily joined the ruling-out-the-null-hypothesis club, we’re down from 128 qubits back to 8). This paper also makes no claims to demonstrate entanglement, which is almost certainly necessary for any interesting quantum speedup, and which has been verified in other superconducting qubit experiments (e.g., the Schoelkopf Lab‘s at Yale), but as far as I know still not in D-Wave’s. Even so, after four years of the quantum computing community being told to review a restaurant based solely on its ice water and table settings, I’m delighted that D-Wave has finally brought an appetizer. Expert readers who’ve actually tasted the appetizer are urged, in the strongest terms, to share their analysis in the comments section. I’m looking forward to our least-uninteresting D-Wave discussion ever.
But first, let me anticipate the question that at least one commenter will ask (I mean you, rrtucci). No, I don’t have any regrets about pouring cold water on D-Wave’s previous announcements, because as far as I can tell, I was right! For years, D-Wave trumpeted “quantum computing demonstrations” that didn’t demonstrate anything of the kind; tried the research community’s patience with hype and irrelevant side claims; and persistently dodged the central question of how it knew it was doing quantum computing rather than classical simulated annealing. So when people asked me about it, that’s exactly what I told them. Now, whether because it took the skeptics’ criticisms to heart, or for whatever other reasons, D-Wave has done a real experiment that deserves the careful scrutiny it will receive. I just call the shots as they’re fired.
As some of you might be aware, I’m a theoretical computer scientist, not a physicist (much less an experimentalist). So in previous posts, the only reason I even presumed to comment on experimental matters is that D-Wave made it easy for me! My “expert analysis” mostly just consisted of pointing out, over and over, that D-Wave hadn’t yet brought the QEDB (Quantum-Effect-Demonstrating Beef)—and that, until they did so, there seemed to be little reason even to discuss the other issues that D-Wave’s marketing materials and the press were both spending 95% of their time on. Now that a slice of QEDB (or something that looks like one, anyway) is on the table, I think there’s at least as much need as ever for critical evaluation of D-Wave’s claims from the quantum computing research community, but I no longer see Shtetl-Optimized filling that need. So I hereby announce my retirement as Chief D-Wave Skeptic, a job that I never wanted in the first place. New applicants for this rewarding position are urged to apply in the comments section; background in experimental physics a must.
Follow
Comment #1 May 15th, 2011 at 4:12 pm
Don’t take this personally Scott but the most interesting thing in this post was the fact that you claim you were unable to read the D-Wave article because it was behind a paywall. But how can you say with a straight face that MIT doesn’t have a subscription to NATURE, one of the preeminent science journals on the planet? Such a claim simply doesn’t make sense–much like D-Wave’s early press releases. All of this leads me to wonder whether you actually did read the article, got scared by its results, and tried to manufacture a reason why you don’t comment on it. Now please understand that I don’t work at D-Wave, don’t have friends there, and am not an investor in the company. Still, I’m sure your readership will agree that your story is more than a little suspicious.
Comment #2 May 15th, 2011 at 4:19 pm
I’m not sure I get your point about entanglement. Would you agree that, if their quantum model correctly describes reality, then there is entanglement within the 8 qbits?
Comment #3 May 15th, 2011 at 4:34 pm
All of this leads me to wonder whether you actually did read the article, got scared by its results, and tried to manufacture a reason why you don’t comment on it.
Or, even more sinister … is it conceivable that I was traveling, and forgot how to get into the MIT firewall remotely? Or that I despise paywalls, and refuse to go to out of my way (or spend a dime) to access papers that are hidden behind them? 🙂
In any case:
1. I do have the original article now, and it confirms what I understood from the Supplementary Material (which is basically just a longer version of the article).
2. If I were “scared,” why on earth would I have written this post?
Comment #4 May 15th, 2011 at 4:44 pm
Simple mind #2: Good question; maybe someone can clarify that for us!
If the noise in the system were sufficiently high (and in D-Wave’s setups, it generally is high), I think it would be possible to observe a “signature of quantum tunneling” without entanglement ever being there. For example, given a state of the form
(1-ε)I + ερt,
one could “observe quantum tunneling” in the ρt component, yet if ε is sufficiently close to 0 then we know the state can’t be entangled. On the other hand, if the noise were low enough, then it’s conceivable that the signature D-Wave is measuring would already be enough to imply entanglement—I don’t know. (I was kinda hoping the paper would address this issue directly.)
Comment #5 May 15th, 2011 at 4:50 pm
@Ward Littel
No need to go paranoid, but indeed this is interesting. I didn’t know MIT dare to face Nature Publishing Group. Allow me to applaude 🙂
http://en.wikipedia.org/wiki/Serials_crisis
Comment #6 May 15th, 2011 at 5:05 pm
Scott,
Can you quantify what you mean by “in D-Wave’s setups, [the noise] generally is high?” That seems to be a pretty bold statement that you should be able to support.
Comment #7 May 15th, 2011 at 5:10 pm
Oops -MIT’s not fighting finally ^^
Interesting point Scott. I would be glad to read rrtucci or another physician adressing that.
Comment #8 May 15th, 2011 at 5:23 pm
Greg J.: D-Wave’s whole engineering philosophy, which they themselves stressed from the beginning, has centered around putting together a bunch of qubits with decoherence rates that are much higher than “traditional” QC researchers would consider acceptable. Having said that, I don’t know what the decoherence rates were in this particular experiment, or how close the state was to pure—hopefully someone will be able to clarify that for us.
Comment #9 May 15th, 2011 at 11:49 pm
Hi Scott. Nice Post. Please excuse my occasionally annoying comments.
Comment #10 May 16th, 2011 at 12:43 am
Hi,
I’m really confused as to where this myth about D-Wave’s qubits being noisy comes from. The qubits have amongst the lowest values for 1/f flux noise ever reported in the literature.
See for example: Experimental Demonstration of a Robust and Scalable Flux Qubit R. Harris et al. – Physical Review B 81, 134510 (2010)
Quote:
“While noise is not the central focus of this article, we nonetheless present experimental evidence that, despite its physical size and relative complexity, the observed flux noise in this flux qubit is comparable to the quietest such devices reported upon in the literature to date.”
Values close to 1 microPhi0 per sqrt Hz at 1Hz are reported in this study. That’s a pretty low noise level for RF-SQUID based flux qubits.
Comment #11 May 16th, 2011 at 1:56 am
Dear Scott,
Many thanks for your very nice post!
I was curious about one comment that you made:
> This paper also makes no claims to demonstrate entanglement,
> which is almost certainly necessary for any interesting quantum
> speedup, and …
It is certainly true that a quantum computer whose state is a *product* throughout a quantum computation is no more powerful than a classical computer.
But, as far as I’m aware, it is an open problem to prove that a quantum computer whose state is mixed and remains *separable* throughout a computation has the same computational power as a classical computer. In this setting
the gates to be applied during such a circuit need to be entangling but the state of the quantum computer is promised to be separable throughout.
Or perhaps this has been proven in the meantime? I would be very interested if progress has been made on this conjecture…!
Comment #12 May 16th, 2011 at 6:34 am
Tobias: Whether separable-mixed-state quantum computers can be efficiently simulated classically is absolutely still an open problem! Indeed, I know of zero progress on it over the last 12 years (!). (As it happens, I just highlighted that problem on Friday, at a talk I gave at Perimeter about subclasses and superclasses of BQP.)
However, it’s certainly the case that we don’t know anything useful that can be done by a separable-mixed-state quantum computer (indeed, my own conjecture is that it can be simulated in BPP).
This is exactly why I said entanglement is “almost certainly necessary” (perhaps I should have said: “necessary for implementing any known quantum algorithm”), not “provably necessary.”
Comment #13 May 16th, 2011 at 8:22 am
I assume “The Territory Around BQP: Results and Open Problems” (PIRSA:10050096) is the talk at Perimeter you mentioned, yes?
Comment #14 May 16th, 2011 at 9:02 am
Scott,
Their work was accepted by Nature and I bet that their system works quantum mechanically rather than classically.
MI
Comment #15 May 16th, 2011 at 9:20 am
idiot: I didn’t say otherwise!
However, it’s important for people to understand that publication in Nature is not some sort of “certificate of importance, originality, and correctness”—there have been quantum information papers in Nature that I know were crap. Rather, it’s a certificate that the editors and reviewers thought this paper was interesting enough to merit attention from the broader scientific community—and in this case, I completely agree with them.
Comment #16 May 16th, 2011 at 12:00 pm
@Suz:
It’s from people’s tendency to favour information that confirms their preconceptions or hypotheses regardless of whether the information is true. People believed, based on lack of information, that D-Wave’s chips were classical, and naturally, whether consciously or unconsciously, fabricated information to support their hypothesis. Without any information, people would have immediately realized that no conclusion can be made, but with fictional information, even after the fictional information is revealed to be fictional, people still continue to hold onto the conclusion formed based on the fictional information.
It’s an extremely common psychological effect, one of which scientists should try to remain aware in order to ensure they follow the scientific method. It can make evaluating work difficult for all parties: a worker may consider certain information irrelevant and leave it unsaid, and an evaluator may similarly consider certain information presented irrelevant and ignore it, preferring instead information fitting desired or preconceived beliefs, whether conscious or unconscious.
Comment #17 May 16th, 2011 at 12:45 pm
Scott,
Re: comment #12… last I checked, I thought that DQC1 was (1) not known/believed to be within BPP, and (2) proven to be achievable with no entanglement at all. Mind you, I’m not up to date on this, so I’m happy to be corrected.
(Slightly more detail for those who would like it: DQC1 is the complexity class of problems that can be solved by a quantum computer with 1 perfectly clean qubit and N maximally mixed (but perfectly controllable) qubits. It basically contains one problem: “Estimate whether the trace of the unitary matrix corresponding to an N-qubit circuit is O(1) or not.” And, iirc, you can do this even if the “clean” qubit has enough noise to ensure that there is no entanglement between any subsets of qubits.)
Comment #18 May 16th, 2011 at 12:51 pm
Suz and Neil: Granted, it could be my profound psychological biases, biases the D-Wave folks have always been blessedly free of… 🙂
Or, it could also be that Geordie himself, when he visited MIT and when a bunch of us had dinner with him at QIP2010 in Zurich, talked extensively about the large noise issue—and about why, in contrast to the academic approach (of first decreasing the noise below the known fault-tolerance thresholds), D-Wave’s approach was to string together a large number of qubits that were well above the threshold and see what happened.
Now, it’s possible that the facts, the philosophy, or both have changed over the last year and a half, or just that we mean completely different things by “large error”—but if so, you could just tell me about that instead of psychoanalyzing me.
(It’s funny, I was feeling like I did a pretty heroic job of “overcoming bias” in this post! Given the sheer number of overblown D-Wave claims in the past, I would have been entirely justified to assume that the latest claim would be likewise overblown. Instead, I looked at it and thought: hey, there’s really something here! And I said so immediately. Don’t I even get a cookie?)
Comment #19 May 16th, 2011 at 12:55 pm
Ah, my apologies for not clarifying: I’m not accusing Scott or any other specific person of anything that could be interpreted as sinister or unwise, just people in general. My comment would be very hypocritical if I was, since I’m not about to spend the ton of time it’d take to hunt down all related text and make a detailed analysis. I suppose my comment was still slightly hypocritical, since it’s a convenient and simple explanation, and I haven’t evaluated the plausibility of all possibilities.
Comment #20 May 16th, 2011 at 12:57 pm
Neil: Thanks for the clarification!
Comment #21 May 16th, 2011 at 1:02 pm
Oh, and you beat me to replying to my own comment. Oh well. My apologies again.
You certainly did update your opinion based on new information, which is to be commended and encouraged. It seems like on other fronts, there’s a huge surge of people out there not updating their opinions on many contentious issues of our time… or maybe the media is just portraying it that way. 😉
Comment #22 May 16th, 2011 at 1:27 pm
Robin #17: I’m pretty sure your claim (2)—that DQC1 is achievable with no entanglement at all—is false, although it’s true that a DQC1 circuit never generates a large amount of entanglement. Googling turned up this PhD thesis by Animesh Datta, which does a wonderful job of exploring these issues.
I agree with your claim (1).
Comment #23 May 16th, 2011 at 3:14 pm
The 128 qubits are still on sale!
http://www.dwavesys.com/en/products-services.html
Comment #24 May 16th, 2011 at 5:37 pm
@Suz
>The qubits have amongst the lowest values for 1/f flux noise ever reported in the literature.
On pure logical grounds, this could be true and the noise high 🙂
Do you have some insights that it’s low enough to let D-wave find solution to some hard approximation problems? If yes, would you mind to explain what level of noise you would consider harmfull, and how to compute this boundary?
@Scott
>we’re down from 128 qubits back to 8
Is it completly fair to say that? I mean, basically there are classically computing the behavior of their machine, then looking if it fits real data. If they were trying to compute classically the behavior of a 128 qbits system, they would ran into some problem yeah?
More generally, how would you prove yourself that your believed-100000-qbits-annealing-machine actually behave well (“annealing” as in “Shor is not a solution”)? Shoud one believe that quantum computers are known to be able
to solve NP-complete problems in polynomial time or there exists other means?
Comment #25 May 16th, 2011 at 7:05 pm
Scott,
Mea culpa. You’re right — I was operating on a garbled recollection of a several-years-ago talk by Animesh. I conflated “No entanglement between qubit 1 and the rest, and no entanglement among the rest” with “No entanglement.” But his thesis clearly explains why that’s wrong. And they give mildly compelling arguments for the conjecture that entanglement can always be achieved with some unitary even for low polarization.
Sigh. The question of whether separable computations can be classically simulated has been open way too long. Even for concordant evolutions, Bryan Eastin’s nice construction fails (nontrivially) for qudits. It irritates me no end that I can’t even formulate a convincing hunch about the answer to this [binary] question!
Comment #26 May 16th, 2011 at 9:14 pm
We are deep into 2011 now, and D-wave is still at 128 qbits. Hardly the 1000 plus predicted by D-wave for 2008.
Give Scott a break, D-wave has made many bold statements and offered little proof. Now D-wave had given a fragment of proof Scott is willing to step back and let the physicists have a go.
People got emotional about this because they wanted this to be true and Scott was the Grinch telling everyone to hold onto their wallet until some proof was given.
Comment #27 May 17th, 2011 at 4:57 am
By mixed seperable states, are we talking about states with quantum discord or entirely classical states? This is a debate I hear sometimes, which I am still not sure I understand fully. Surely, if they have no entanglement (which as far as I can tell hasn’t been proved either way) that puts them at roughly the same ground as NMR which is quite contentious ground to be on. At the same time, computational power is something that is fairly new to me so I could be entirely wrong.
Comment #28 May 17th, 2011 at 5:13 am
Katherine: I wasn’t talking at all about discord; by a separable mixed state, we mean simply a mixture of product states.
A crucial point is that the states in liquid NMR are not merely separable, but separable because they’re extremely close to the maximally mixed state. By contrast, here we’re talking about states that can be very far from maximally mixed, just as long as they remain separable.
Comment #29 May 17th, 2011 at 11:16 am
This is a nice new D-wave post. I found the earlier skeptical posts about D-wave quite interesting. Initially the skeptical approach towards D-wave was based on reasonable gut-feeling and then a large array of concerns. Some of these concerns were not particularly convincing and applied to almost every attempt, commercial or academic, to build a quantum computer. (E.g. my cellphone is more powerful than a D-wave machine…) But some other concerns were more to the point.
One remarkable thing about D-wave is that it created this technology of chips where traditional semiconductors are replaced by superconductors (I hope I got it correct) and it led to much research conducted in the company itself and a large number of academic papers studying the physics of these gadgets.
One basic question that is related to what D-wave is trying to do now (which is quite related to my own research interest) is the question if superior computational power of quantum computers requires quantum error correction. This is a very interesting question and putting it on a formal ground is not at all an easy task.
Regarding seperable-mixed-state-quantum-computation, I wonder what is the precise formal statement of your conjecture, Scott. I remember that there are ways to simulate a universal quantum computer with a quantum computer so that the state at all times is the maximally mixed state (with some side classical computer); (I think that by a careful analysis one can discover where the entanglement is hiding though.)
Overall, even if one regards, as I do, creating a computationally superior quantum computers to be unplausible, one cannot ignore the fact that the idea of computationally superior quantum computers gave us an excellent ride for our money. Maybe this will also be the case in commercial related endeavors.
Comment #30 May 17th, 2011 at 1:42 pm
Scott said
“If the noise in the system were sufficiently high (and in D-Wave’s setups, it generally is high), I think it would be possible to observe a “signature of quantum tunneling” without entanglement ever being there. For example, given a state of the form
(1-ε)I + ερt,
one could “observe quantum tunneling” in the ρt component, yet if ε is sufficiently close to 0 then we know the state can’t be entangled. On the other hand, if the noise were low enough, then it’s conceivable that the signature D-Wave is measuring would already be enough to imply entanglement—I don’t know. (I was kinda hoping the paper would address this issue directly.)”
I was thinking about this. What confuses me is that I would like to believe that
(1) separable state => exactly zero tunneling
(2) separable state not entangled
Why do I say this? Because a separable state is essentially classical, and classical systems can’t tunnel through walls, ever. So then if they see tunneling, their state must be slightly entangled?
Comment #31 May 17th, 2011 at 1:48 pm
In (2) I meant
(2)state separable iff state is not entangled
Comment #32 May 17th, 2011 at 5:20 pm
Okay, maybe separable but non-diagonal density matrices can have non-classical properties like the ability to tunnel even though they have no entanglement. But I find it hard to believe that a property as non-classical as tunneling doesn’t allow you to calculate faster (with more favorable time complexity). It’s like saying that Superman’s X-ray vision doesn’t give him a more favorable time complexity compared with my myopic vision.
Comment #33 May 17th, 2011 at 8:14 pm
rrtucci, thx for adressing the question.
Reading next post, it seems likely that sampling nonadaptive linear optic requieres Superman power too. Do you believe this property would allow to calculate faster?
Comment #34 May 17th, 2011 at 11:17 pm
Gil: Here is one way to make your question well-posed. Fix a model of quantum circuits and suppose that each gate experiences noise at rate p. For p sufficiently close to 0, the threshold theorem of fault-tolerant quantum computing states that the model is equivalent to BQP. For p sufficiently close to 1, the model should be contained in BPP. You can then ask whether at any intermediate values of p, we obtain any classes intermediate between BPP and BQP.
As for separable-mixed-state computations: the standard form of the question is to ask whether one can simulate BQP on a quantum computer that is guaranteed to remain in a separable state throughout its computation for any choice of input.
Comment #35 May 18th, 2011 at 12:21 am
Simple Mind:
Yes. Linear optics configured as prescribed by Scott can sample “faster” than classical. That’s what Scott has proven (starting from some very plausible assumptions).
Comment #36 May 18th, 2011 at 12:33 am
Dear Aram, right! Looking at the noise level is certainly one way to think about it. (It is an appealing guess that you will not witness intermediate complexity classes and that there will be a sharp threshold behavior between BPP and BQP. But perhaps the class described by log depth quantum circuits will genuinly enter the picture.)
My question is somewhat different. Consider a process of the kind proposed by D-wave. Here we do not see any apparatus for implementing fault tolerance and quantum error correction. You can ask if such a system can lead to computational speed up even for a fixed small level of noise.
(Indeed this is one of the concerns expressed about D-wave.)
You can pose this question specifically to the type of annealing processes proposed by D-wave and you can ask it in a greater generality. So the question is what is the computational power of quantum processes that do not apply quantum error-correcion. (Even for a small level of noise.) As I said to formally describe what we mean by “not apply quantum error-correction” is not so easy.
Comment #37 May 18th, 2011 at 7:00 am
rrtucci,
That was not the question. I said myself that sampling NALO is likely faster using NALO than any classical means.
The question was: do you believe this property would allow to calculate faster anything else but sampling non adaptive linear optic?
I’m asking because I don’t get what makes you automatically believe that tunneling is a property that allow to compute faster anything else but tunneling.
Comment #38 May 18th, 2011 at 9:45 am
Simple mind said,
“I’m asking because I don’t get what makes you automatically believe that tunneling is a property that allow to compute faster anything else but tunneling.”
Here is a very simplistic explanation that might help justify rrtucci’s hunch about tunneling:
In the quantum annealing setup, tunneling is believed to provide the opportunity for getting out of local minima in cases where thermal annealing is facing failure. An example of such a situation is a very tall but thin potential barrier–imagine two low energy states with a few high energy states in between. The goal is to get from one low energy state to the other. In that case simulated annealing would likely not be able to muster enough thermal kick to jump over the barrier. However, if the Hamming distance between the low-energy states is not too large (the barrier is thin), then the corresponding significant tunneling amplitude could let you get through to the other side.
Comment #39 May 18th, 2011 at 2:19 pm
Vasil, this is the most convincing answer I ever read about quantum annealing being able to deal with situations for which classical computation would likely fail.
That’s not the same as solving all NP-hard instances, because it won’t deal with situations for which the minimum is surrounded by tick barriers. However I agree being able to pass through high-but-thin barriers may well be usefull for a large class of real-life applications.
So, thanks for your insight 😉
Comment #40 May 19th, 2011 at 4:18 pm
rrtucci (#30): You may have already answered your own question — “[I]f they see tunneling, their state must be slightly entangled?”to your satisfaction. But, if not…
…there are two problems with that reasoning (and any known answer, at this point!). The first is that we do not have any single criterion for what makes something “quantum”. Hardcore quantum optics guys call any system in a non-Gaussian state “quantum” — and some even consider squeezed Gaussian light to be “quantum”. At the other end, many foundations folk reserve “quantum” for experiments that demonstrate contextuality. There are several well-defined intermediate conditions, including entanglement.
Point is, we still have no farking idea which of these conditions is the secret sauce for computational speedup. It’s probably not even as simple as that — DQC1 is less powerful than BQP, so there may well be one condition enabling “speedup to DQC1 U BPP” and another condition enabling “speedup to BQP”. And maybe neither of those conditions is “there must be entanglement”! So tunneling could be incomparable to entanglement.
The second problem is that tunneling is a wholly dynamical phenomenon — you detect it by seeing a forbidden transition between classical states, between two different times. Entanglement, on the other hand, is a static property of a state. So they really are incomparable. Dualities between static and dynamic aspects of QM are fun to play with, and we know some things (notably, the Jamiolkowski isomorphism, and the relationship between Leggett-Garg inequalities and Bell inequalities), but we don’t really understand it. I don’t believe anybody has managed to draw a connection between entanglement (static) and tunneling (dynamic)… although maybe it can be done!
Comment #41 May 19th, 2011 at 4:27 pm
Gil (#36): That is, indeed, a great question.
The problem is, we need to precisely define what is quantum error correction. Not just a sufficient definition (“An implementation of the Aliferis-Preskill scheme for fault tolerance, using Bacon-Shor codes, is sufficient for QEC”), but a precise one.
Why? Because otherwise we can’t be sure that a given physical system isn’t implementing some form of QEC all by itself! It’s not as crazy an idea as it sounds — Preskill and Lloyd have both publicly speculated that the universe might be doing something of the sort, and there’s a lot of interest in topological self-correcting memories (which currently appear to work only in 4D space).
Much more plausible is the idea that the natural thermal dynamics of certain systems implements a limited form of QEC. Not enough to run Shor’s algorithm… but enough for that system to robustly “compute” aspects of its own dynamics that can’t be simulated by a classical computer. The Fermi-Hubbard model is a great candidate, simply because we can’t figure out how to simulate it. And this, of course, is the motivation behind work on “quantum simulators”.
The one thing that you absolutely need for this is non-unitality — a.k.a. cooling. If the system’s evolution is noisy and unital, it ain’t gonna compute anything in the long run. But, fortunately, cooling is pretty ubiquitous in nature.
Comment #42 May 20th, 2011 at 8:32 am
The fact is that D-Wave simply isolated itself from the rest of the QC community by making a lot of bogus statements about QC and putting up smoke and mirrors. When I was at QIP 2009, I saw very little interest in D-Wave one way or the other, except at one dinner after drinks had been poured. Does that mean that they will never say anything useful in the future? Of course it doesn’t mean that. Of course they could be useful again. If they published in Nature, then plainly the research community is ready to listen.
Scott is of course correct (from one point of view) as to the crux of the matter: Whether, let’s call them, dwits (D-Wave bits) are truly qubits, or merely bits, or something else. Whether they have 8 or 128 dwits is not the point, because even 8 good qubits would be a big achievement.
Comment #43 May 20th, 2011 at 5:54 pm
Hi Greg, I’m new to this story, can you point me to something specific that dwave said that you think are bogus? Also isn’t qip just for theoretical computer scientists? It’s not hard to see why they wouldn’t care that much about a machine?
Comment #44 May 21st, 2011 at 1:50 pm
Curious programmer – One particularly dubious moment for me was the “quantum Soduku” stunt. It looked entirely like smoke and mirrors to me. At the time, they said that their quantum computer had 16 qubits. Now, qubits cannot store any more classical information than 16 bits (Nayak’s theorem), which is to say, you can store at most one Unicode digit with 16 bits or qubits. I couldn’t think of any meaningful sense in which such a tiny computer could solve a Sudoku. D-Wave never helped answer that question as far as I know.
But you should understand that there were a lot of other bizarre displays and remarks and this is just one example.
As for QIP, no it’s not just for theoretical computer scientists. Every year they include experimental talks, moreover many of the theorists are physicists. Moreover many of the theorists there have a strong interest in actual quantum computers even if they do theory themselves — theory is not nearly as interesting when it has no connection to experiment.
Comment #45 May 21st, 2011 at 7:11 pm
Hi Greg, sudoku can be written as constraint satisfaction which is defined over booleans, which to could solve using a solver restricted to k booleans for any k by using breadth-first search? In other words you fix some variables and then optimize over some other subset and iterate? That seems to match what dwave says they have?
That example seems to me to be pretty clearly “ok” ie not bogus or weird. Do you have any other examples? Re qip I looked at the last ones attendance list and there were no experimental physicists?
Comment #46 May 22nd, 2011 at 3:43 pm
Dear Robin (#41), thanks for the interesting comments.
Hre are some comments:
“…we need to precisely define what is quantum error correction.” I absolutely agree.
“…we can’t be sure that a given physical system isn’t implementing some form of QEC all by itself! It’s not as crazy an idea as it sounds — Preskill and Lloyd have both publicly speculated that the universe might be doing something of the sort,”
I am not sure about what is Preskill and Lloyd’s suggestion precisely (will be happy to know) but I am aware of some related ideas. This is certainly very interesting direction. There is a proposal (by Hayden and Preskill) that certain quantum states are relevant to black holes. More precisely certain highly entangled states (unitary t-design) that can be created by quantum fault tolerance (which approximate in a certain sense “generic” states which are computationally unfeasible) may account for some phenomena regarding information and black holes.
There may be an alternative way to have a similar explanation without assuming natural implementation of quantum error correction, by regarding two (or more) non-interacting quantum computers with the same underlying Hilbert space (but different tensor product structures).
(Of course it is also possible (while highly speculative) that states that cannot be approached by any “quantum computer” w.r.t. any tensor product structure also exists naturally.)
“Much more plausible is the idea that the natural thermal dynamics of certain systems implements a limited form of QEC. Not enough to run Shor’s algorithm… but enough for that system to robustly “compute” aspects of its own dynamics that can’t be simulated by a classical computer.”
Yes, this possibility can be regarded as the initial rationale of Feynman for the existence of computationally superior QC. (I am not sure about the “not enough to run Shor’s algorithm” part, as the computation of rather simple system’s own dynamics may be BQP complete.)
“The Fermi-Hubbard model is a great candidate, simply because we can’t figure out how to simulate it. And this, of course, is the motivation behind work on “quantum simulators”.”
I will be happy to have some references.
“The one thing that you absolutely need for this is non-unitality — a.k.a. cooling.”
Right! (Curiously, it may be the case that reversible noisy QC still allows polynomial time factoring.)
Comment #47 May 23rd, 2011 at 1:10 am
Curious programmer: Yes, it’s true, you could divide the variables of the “constraint optimization” so that a classical computer does 99% of the work, and then goes out of its way to let the 16 dwits (or alleged qubits) do the other 1% of the work. If you actually plug in the values of “n” and “k” in your description, that is what it would mean. Is that what they meant by a “quantum solver”? A solver that’s 1% quantum? That point has not been explained.
Anyway, since you want other statements, there was the statement that they had unveiled “the world’s first commercially viable quantum computer”. Clearly, their 16-dwit device was not commercially viable, and four years later they are still trying to prove that it’s quantum.
Comment #48 May 23rd, 2011 at 4:31 am
On the other hand, there is one slogan on the D-Wave site that I’m tempted to agree with, even though I’m not entirely sure what it means: “We have a problem with impossible.”
Comment #49 May 26th, 2011 at 6:46 pm
Fyi on their system sale:
http://blogs.forbes.com/alexknapp/2011/05/25/d-wave-sells-quantum-computer-to-lockheed-martin/
Comment #50 May 26th, 2011 at 7:40 pm
D-Wave apparently sold their first system to Lockheed.
http://www.dwavesys.com/en/pressreleases.html#lm_2011
Gigi
Comment #51 May 27th, 2011 at 12:34 pm
The news that D-Wave sold something to Lockheed Martin has been bouncing around with a “see, that proves it” sort of tone. But obviously, a sale by itself doesn’t necessarily prove anything. To the extent that the research community cares about D-Wave, it would want to know whether their “quantum” computers are actually quantum in any useful sense. Or, failing that, whether they are quantum in any viable sense. The paper in Nature analyzes the second question.
But selling one to Lockheed Martin? It’s a company with 132,000 employees. So it would be nice to know, at a bare minimum, which of them made this purchase and why. Then those interested could begin to consider whether it was a good idea.
Comment #52 May 27th, 2011 at 11:23 pm
Thanks for the link to my Quora answer. Even as I dequantize I’m glad there will be the Optimizer to keep me up to date on D-wave (because isn’t that the main reason you blog?)
In related news to D-wave’s paper and computer sale, this paper has some damn good coherence times for superconducting qubits http://arxiv.org/abs/1105.4652
Comment #53 May 27th, 2011 at 11:30 pm
Greg, you don’t seem to be thinking clearly about this subject. It sounds like you have some sort of personal vendetta. Do you? While I can understand why you’re not familiar with the way a company like lockheed makes strategic partnerships, its hard to believe that you don’t understand basic local search algorithms. You’re not doing people who are trying to understand what’s actually going on any favors. If you really want to give useful advice that’s great but stick to facts and not opinions especially in areas you clearly know nothing about. Just my 2 pesos. Sorry if this was a little harsh just trying to improve signal to noise in the blogosphere.
Comment #54 May 28th, 2011 at 10:25 am
Is it known outside of D-Wave and Lockheed whether the 128-qubit machine implements Hadamard gates? Can it truly be called a “universal” quantum computer it not? If so, what kind of practical problems could be solved faster on a 128-qubit machine than a modern classic computer? (I only have a superficial layman’s understanding of this, please excuse me if my questions make no sense.)
Comment #55 May 28th, 2011 at 12:09 pm
Good for you, Scott. Ever since reading Bernard D’espagnat in a 1979 SA article I’ve found this to be a fascinating subject. Does the speed potential compensate for it being probabilistic? And aren’t we dependent on the speed of our electronic oscillators and error correction routines to communicate the results of quantum calculations to a human observer. Not to mention the exquisite sensitivity that these devices might be vulnerable to.
Comment #56 May 28th, 2011 at 1:26 pm
Now I am an engineering, and as such I may have a different perspective. But I would say the prove is in the pudding: does this D-Wave thing have any of the magical properties of a quantum computer? Can it factorise two primes faster than a desktop PC? Can it give a suboptimal solution to some optimisation problem faster than a genetic algorithm? And if so, it is also faster than an analog computer (with noise)?
Since D-Wave should know their device best, and since they want to sell it, I would expect them to demonstrate its usefulness. That is just good engineering judgement: ask the vendor to demonstrate their product.
The theoretical debate is interesting – and it could explain why or why not D-Wave can deliver this proof. But for the question of whether this is value for money or not it is not necessarily critical.
Comment #57 May 28th, 2011 at 2:00 pm
Thomas: D-Wave says explicitly that they have no interest in factoring, and as far as I know, they have yet to publish a convincing controlled comparison of their adiabatic optimization against classical simulated annealing. Yet every time they announce something, I get deluged by comments asking for a reaction, and hardly anyone seems satisfied with the commonsense, engineering, “proof is in the pudding,” “burden of proof is on them” answer that you suggest. So that’s why attention necessarily shifts to what you call the “theoretical debate.”
Comment #58 May 28th, 2011 at 2:36 pm
Scott: I see – and I do not envy your position at all. People ask you to explain why it does not work, or even proof that it does not work, without you having access to the device?
I guess the other question is whether D-Wave has potential. I think analog computers could be quite good at certain problems, especially finding suboptimal solutions. With quantum effects, it may be even better. But if you have to argue for years whether it shows quantum effects or not, than it does not seem to be a very good quantum computer :-).
Well, that’s my position as someone who understands very little about quantum computing.
Comment #59 May 29th, 2011 at 3:10 pm
Hi everyone, If you are interested, I wrote up my vague, woolly thoughts about D-Wave in my blog:
To Build a Fire
Comment #60 May 30th, 2011 at 12:06 pm
@Dave Bacon
Wow! Thx for pointing it 😉
Comment #61 May 31st, 2011 at 6:40 am
According to photos on the web, the D-Wave One is an impressive Kaaba-like black box about ten feet tall.
Rumor has it that there is a cat inside the box, waiting to be measured.
Comment #62 May 31st, 2011 at 12:29 pm
More in NatureNews: http://www.nature.com/news/2011/110531/full/474018a.html
Comment #63 May 31st, 2011 at 1:08 pm
Zeeya Merali in Nature News stubbornly sits on the fence between D-Wave and Scott, its involuntary adversary. She even mentioned my pet summary of D-wave, 16 dwits and Sudoku. But she missed the fact that, according to Nayak’s theorem, even a perfect 16-qubit device wouldn’t be able to solve more than a tiny fraction of a Sudoku.
One tiny piece of new information is revealed: A Lockheed Martin spokesman, Thad Madden, says that “the company” spent more than a year evaluating the D-Wave One. That’s great, but it doesn’t explain who at Lockheed Martin is involved; it certainly wasn’t Madden himself. Okay, it also mentions “cyber-physical systems”, which could be a useful keyword.
Comment #64 May 31st, 2011 at 2:25 pm
It seems that “cyber-physical systems” is a slogan that means, essentially, robotics. See for instance this PowerPoint by someone at Lockheed named Gary Hafen. The gist of the PowerPoint seems to be that Lockheed-style robotics — for jets, satellites, and wheeled military robots — is really complicated. The last page of the PowerPoint, before the snazzy logo, mentions “quantum information sciences” as a technology needing research, I guess for cyber-physical systems.
I don’t know if it’s Gary Hafen in particular, but it looks like there is a movement afoot to refer to robotics (or distributed robotics) as cyber-physical systems, and that someone at Lockheed wants to think outside of the box by buying from D-Wave.
Comment #65 May 31st, 2011 at 5:55 pm
Vasil,
> if the Hamming distance between the low-energy states is not too large (the barrier is thin), then the corresponding significant tunneling amplitude could let you get through to the other side.
In what way is this better than redesigning your physical system so that the barrier has lower energy and is easier to climb over classically? I’m not sure what’s specifically ‘quantum’ about your explanation.
Comment #66 May 31st, 2011 at 10:15 pm
Dan P,
Could you please elaborate? I am not sure I understand what you mean.
Comment #67 June 1st, 2011 at 10:36 am
Vasil,
You’re saying that quantum tunnelling gives a way to get from one local minimum to another when there is a hill between. But there are classical means to get over hills, eg. pump more energy into the system. Why is tunnelling a better way to get from one minimum to another than classical paths?
Comment #68 June 1st, 2011 at 1:08 pm
Dan P,
Sure, I agree there exist all kinds of heuristics, but they all have their failure scenarios, no doubt about that.
All I am saying is that for any particular failure case of a classical heuristic, quantum tunneling offers you a qualitatively different resource that may help eliminate or alleviate the failure.
Beyond numerical studies of very small sizes, it is currently unknown how significant that help really is, but at least what has been seen is pretty encouraging.
Comment #69 June 2nd, 2011 at 9:26 am
Vasil,
Thanks for the answer. I think you summarise my feelings: it looks just like another heuristic you can apply to tweak the landscape in annealing. It’d be cool if it resulted in some big improvement – but I really can’t see any a priori reason why it’d be better than other annealing heuristics – just different.
Comment #70 June 2nd, 2011 at 3:49 pm
On the other hand, Dan P, the capacity to quantum tunnel is a “heuristic” that doesn’t exist in the classical world, just like Superman’s X ray vision doesn’t exist in the classical world. Does this mean that you
“really can’t see any a priori reason why”
Superman would
“be better than other annealing heuristics – just different.”
at fighting supervillains?
Comment #71 June 3rd, 2011 at 4:44 am
Scott, the only reason you became the face of the D-Wave Skepticism Movement is that you, more than any, provided clear, simple arguments for why we have too little information from D-Wave and should remain skeptical until we have reason to believe otherwise, which is a scientist’s duty. I think the majority of the scientific community see your posts on D-Wave and think, “what he said.”
But apologies for leaving you to lead the fight against the “yay”-sayers largely alone. 😉
Comment #72 June 3rd, 2011 at 6:43 am
Interesting discussion. As far as I know, there is provenly no free lunch when it comes to search heuristics optimizing over arbitrary fitness landscapes, see http://www.no-free-lunch.org/ and http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
For all the reasons that the No Free Lunch Theorem for Search and Optimization tells us, I can quite confidently say that with quantum annealing it should be no different. It could really provide great speedups by exploring common structures of certain instances, but, on the average of all possible problem instances and objective functions, it should make no better than any competent classical heuristic.
Ok, I can accept a huge speedup due to the parallel nature of QC, but that’s all. I doubt it can explore the search space with more competence than any classical algorithm over arbitrary fitness landscapes.
Comment #73 June 3rd, 2011 at 9:56 am
Carlos: Alas, the “No Free Lunch Theorem” is both obvious and of little relevance to the issue at hand, since there’s an extremely natural subclass of fitness landscapes that encompasses the ones we care about: namely, those with succinct (polynomial-size) descriptions! And as soon as you realize that those are the landscapes we care about, there’s no way to avoid the P vs. NP and NP vs. BQP questions.
(Incidentally, the quantum analogue of “No Free Lunch” would simply state the optimality of Grover’s algorithm for unstructured search.)
Comment #74 June 9th, 2011 at 1:05 pm
FYI in case you didn’t know, the no free lunch theorem is due to Bill Macready who runs dwaves algorithms group.
Comment #75 August 12th, 2011 at 1:32 am
Dear Scott,
I think there is an obvious way to test D-wave’s commercial quantum computer: whether a quantum algorithm can be performed efficiently on it. e.g. given a 30 digit number, if it can be factorized efficiently on the D-wave’s commercial quantum computer. are there such a demonstration? Thanks!
Comment #76 September 5th, 2011 at 9:56 pm
Ummm…. I don’t understand why people care so much about whether D-Wave’s system is getting a boost from quantum mechanical effects or not. In my humble opinion, all that matters is can the machine do what it was designed to do? Can it perform the calculations they say it can? Lockheed will soon find out. If it can, then who cares? I am not in a position to judge D-Wave, but I do agree with them on one point. Just because for over a decade researchers believed a quantum computer HAD to behave a certain way, does not mean there aren’t other ways to exploit quantum effects to achieve computing abilities that classical systems either do not have or are very slow at performing.
Comment #77 February 21st, 2012 at 7:34 pm
[…] spite of my announcement almost a year ago that I was retiring as Chief D-Wave Skeptic, I thought it would be fitting to give Shtetl-Optimized […]
Comment #78 March 21st, 2012 at 2:56 am
[…] of D-Wave’s claims is much of what Scott Aaronson has wrote about them. See for example https://scottaaronson-production.mystagingwebsite.com/?p=639, https://scottaaronson-production.mystagingwebsite.com/?p=198 although interestingly after he visited D-Wave’s […]
Comment #79 October 4th, 2012 at 12:55 pm
[…] Scott talked about a justification of Dwave quantumness in Nature in 2011 […]
Comment #80 October 4th, 2012 at 2:43 pm
[…] there yet.” A fierce critic of D-Wave in the years following its 2007 demo, Aaronson softened his stance last year after the company’s Nature paper showing quantum effects. “In the past there was an […]
Comment #81 October 5th, 2012 at 5:55 pm
[…] it's there yet." A fierce critic of D-Wave in the years following its 2007 demo, Aaronson softened his stance last year after the company's Nature paper showing quantum effects. "In the past there was an enormous […]
Comment #82 October 7th, 2012 at 1:25 pm
[…] became transparent that a D-Wave chips were demonstrating some quantum effects. Professor Aarson blogged on a development, somewhat softening his […]
Comment #83 October 9th, 2012 at 11:04 am
[…] founder of Amazon.com, recipients of a large fraction of my salary). Despite having officially retired as Chief D-Wave Skeptic, I posted a comment on Tom Simonite’s article in MIT Technology […]
Comment #84 May 16th, 2013 at 12:41 pm
[…] years ago almost to the day, I announced my retirement as Chief D-Wave Skeptic. But—as many readers predicted at the time—recent events (and the contents of my […]
Comment #85 May 18th, 2013 at 10:21 am
[…] years ago almost to the day, I announced my retirement as Chief D-Wave Skeptic. But—as many readers predicted at the time—recent events (and the contents of my inbox!) have […]