Quantum computing in the newz

Update (10/10).  In case anyone is interested, here’s a comment I posted over at Cosmic Variance, responding to a question about the relevance of Haroche and Wineland’s work for the interpretation of quantum mechanics.

The experiments of Haroche and Wineland, phenomenal as they are, have zero implications one way or the other for the MWI/Copenhagen debate (nor, for that matter, for third-party candidates like Bohm :-) ). In other words, while doing these experiments is a tremendous challenge requiring lots of new ideas, no sane proponent of any interpretation would have made predictions for their outcomes other than the ones that were observed. To do an experiment about which the proponents of different interpretations might conceivably diverge, it would be necessary to try to demonstrate quantum interference in a much, much larger system — for example, a brain or an artificially-intelligent quantum computer. And even then, the different interpretations arguably don’t make differing predictions about what the published results of such an experiment would be. If they differ at all, it’s in what they claim, or refuse to claim, about the experiences of the subject of the experiment, while the experiment is underway. But if quantum mechanics is right, then the subject would necessarily have forgotten those experiences by the end of the experiment — since otherwise, no interference could be observed!

So, yeah, barring any change to the framework of quantum mechanics itself, it seems likely that people will be arguing about its interpretation forever. Sorry about that. :-)


Where is he?  So many wild claims being leveled, so many opportunities to set the record straight, and yet he completely fails to respond.  Where’s the passion he showed just four years ago?  Doesn’t he realize that having the facts on his side isn’t enough, has never been enough?  It’s as if his mind is off somewhere else, or as if he’s tired of his role as a public communicator and no longer feels like performing it.  Is his silence part of some devious master plan?  Is he simply suffering from a lack of oxygen in the brain?  What’s going on?

Yeah, yeah, I know.  I should blog more.  I’ll have more coming soon, but for now, two big announcements related to quantum computing.

Today the 2012 Nobel Prize in Physics was awarded jointly to Serge Haroche and David Wineland, for “for ground-breaking experimental methods that enable measuring and manipulation of individual quantum systems.”  I’m not very familiar with Haroche’s work, but I’ve known of Wineland for a long time as possibly the top quantum computing experimentalist in the business, setting one record after another in trapped-ion experiments.  In awarding this prize, the Swedes have recognized the phenomenal advances in atomic, molecular, and optical physics that have already happened over the last two decades, largely motivated by the goal of building a scalable quantum computer (along with other, not entirely unrelated goals, like more accurate atomic clocks).  In so doing, they’ve given what’s arguably the first-ever “Nobel Prize for quantum computing research,” without violating their policy to reward only work that’s been directly confirmed by experiment.  Huge congratulations to Haroche and Wineland!!

In other quantum computing developments: yes, I’m aware of the latest news from D-Wave, which includes millions of dollars in new funding from Jeff Bezos (the 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 Review, and also sent the following email to a journalist.

I’m probably not a good person to comment on the “business” aspects of D-Wave.  They’ve been extremely successful raising money in the past, so it’s not surprising to me that they continue to be successful.  For me, three crucial points to keep in mind are:

(1) D-Wave still hasn’t demonstrated 2-qubit entanglement, which I see as one of the non-negotiable “sanity checks” for scalable quantum computing.  In other words: if you’re producing entanglement, then you might or might not be getting quantum speedups, but if you’re not producing entanglement, then our current understanding fails to explain how you could possibly be getting quantum speedups.

(2) Unfortunately, the fact that D-Wave’s machine solves some particular problem in some amount of time, and a specific classical computer running (say) simulated annealing took more time, is not (by itself) good evidence that D-Wave was achieving the speedup because of quantum effects.  Keep in mind that D-Wave has now spent ~$100 million and ~10 years of effort on a highly-optimized, special-purpose computer for solving one specific optimization problem.  So, as I like to put it, quantum effects could be playing the role of “the stone in a stone soup”: attracting interest, investment, talented people, etc. to build a device that performs quite well at its specialized task, but not ultimately because of quantum coherence in that device.

(3) The quantum algorithm on which D-Wave’s business model is based — namely, the quantum adiabatic algorithm — has the property that it “degrades gracefully” to classical simulated annealing when the decoherence rate goes up.  This, fundamentally, is the thing that makes it difficult to know what role, if any, quantum coherence is playing in the performance of their device.  If they were trying to use Shor’s algorithm to factor numbers, the situation would be much more clear-cut: a decoherent version of Shor’s algorithm just gives you random garbage.  But a decoherent version of the adiabatic algorithm still gives you a pretty good (but now essentially “classical”) algorithm, and that’s what makes it hard to understand what’s going on here.

As I’ve said before, I no longer feel like playing an adversarial role.  I really, genuinely hope D-Wave succeeds.  But the burden is on them to demonstrate that their device uses quantum effects to obtain a speedup, and they still haven’t met that burden.  When and if the situation changes, I’ll be happy to say so.  Until then, though, I seem to have the unenviable task of repeating the same observation over and over, for 6+ years, and confirming that, no, the latest sale, VC round, announcement of another “application” (which, once again, might or might not exploit quantum effects), etc., hasn’t changed the truth of that observation.

Best,
Scott

89 Responses to “Quantum computing in the newz”

  1. Curious Wavefunction Says:

    It’s interesting that this well-deserved prize went to Heroche and Wineland when so many predictions centered on another experimental quantum mechanics paradigm; the work of Aspect, Zeilinger and Clauser. I wonder if this just means that the committee was not as confident of their work.

  2. rrtucci Says:

    Pow. Take that Milner and String theory!

  3. Scott Says:

    Curious #1: I’ve long thought that a prize should go to Aspect, Zeilinger and Clauser for experimental demonstration of the Bell violations. Maybe it will eventually. (I also thought for a while that Valiant and Pearl should win Turing Awards, and that Perlmutter et al. should win a Nobel Prize for the dark energy, and those things HAPPENED! So obviously the committees must be listening to me. :-D )

  4. Another Scott Says:

    Scott. You are an amazing example of why people dislike academics. $100M to build a new type of computer is incredibly low. Each new generation of intel processor costs several billion to generate. Your comprehension of how the real world works is virtually nil.

    The “truth” is that dwave has build the world’s best superconducting foundry – something no-one had ever been able to achieve – in five years on a shoe string budget. They have built the only computing system ever attempted that uses quantum mechanics. And now they are beating 50 years and trillions of dollars of investment by both hardware and algorithm development 1-1. and you have the gall to continue to play the wounded high road scientist.

    What you really are is a fraud who poses as someone who understands what it takes to build machines in the real world, when in reality you do nothing but push symbols around for a living. your cognitive dissonance is truly amazing to behold.

    history is going to paint you as a giant assclown who was wrong and refused to admit it.

  5. Kuas Says:

    Ha! Rose gaining on you in the polls, absolutely crushing you in fundraising, and your cool professorial tone isn’t doing you any favors.

  6. Physics Nobel 2012 « Mostly physics Says:

    [...] Prize in Physics in 2012 goes to Serge Haroche and David Wineland for quantum optics research. One could argue the prize should had gone to Aspect, Zeilinger and Clauser for experimental demonstration of the [...]

  7. Scott Says:

    #4 (whose IP address, interestingly, is from Vancouver): I’ve let your comment appear, because it’s a perfect example of why I’ve all but stopped blogging over the past couple years. I cringed when Obama imploded at the debate, letting lie after lie after lie go unchallenged—I wished to god he would fight harder—but at the same time, I felt like I understood the psychology completely. “This is what you want?” he seemed to be saying. “An ‘economic plan’ based on first-grade arithmetic mistakes, together with a principled refusal to clear them up? Then fine, go ahead! Don’t let me stop you! I’m sick of boxing with phantoms, nailing Jello to a wall, trying to reason and compromise with people who reject the entire concepts of reason and compromise.”

    Look, I thought that I was bending over backwards with moderation in this post, saying nothing that even the most fervent D-Wave supporter could legitimately object to. I said that I really, genuinely hoped D-Wave succeeded, and I meant it. All I did was repeat certain obvious questions about the quantumness of D-Wave’s device that the D-Wave folks themselves acknowledged are central questions they’d like to answer and haven’t yet when I visited them in Burnaby. Yet I still get called a “fraud” and an “assclown” — in fact, the more moderate I am, the worse the insults seem to get.

    So sure, it’s perfectly plausible that you can get quantum speedups with no entanglement whatsoever. Sure, if computer A outperforms computer B at a particular Ising spin minimization problem, then the only possible explanation is that computer A is a quantum computer. Whatever you want. I’m going to go take a nap.

  8. Anon Says:

    Did you also mention that Lockheed Martin currently has their machine sitting at USC being characterized? I just thought the article implied that Lockheed where actually using the machine and that is a fairly misleading claim.

    I also believe that D-wave themselves only claim to have ZZ interaction and local unitaries. This seems odd to me (especially as I thought local unitaries would allow you to generate XX and YY but apparently not). The machine also seems to be primarily being used only for search. It is a shame that their research is being obscured by a publicity department which goes to a large effort to make misleading and often false claims. I think they probably have some interesting results but they are doing their level best to obscure that fact.

    Given how strong the publicity is with D-wave I wish this post to remain anonymous, please can you respect that.

  9. El-Coco Says:

    Hi Scott! Sorry people are beating up on you (but that’s no excuse to use profanity!). Just wondering if you’d ever thought of taking a sabbatical at D-wave. Bet you could help them out a lot and also end the feud. If you guys can patch things up then it offers hope for a world often polarized and unwilling to compromise!

  10. Curious programmer Says:

    Anon: I am always hearing about these “misleading and often false” claims, but when pressed to provide even a single example no-one has been able to. Can you buck the trend? Provide even one specific example of this?

  11. Scott Says:

    El-Coco #9: Fine, profanity removed. I already did visit D-Wave for a day of discussions and lab tours, and already did “end the feud”—or at least I thought I did, before people started attacking again! For academic and personal reasons, I won’t be able to do a sabbatical anywhere for at least a couple more years. In the meantime, though, while the D-Wave folks have already visited MIT several times, they’re more than welcome to spend a semester here and audit my course! :-D

  12. Mateus Says:

    Scott #7: Don’t feed the trolls. It’s the only way to kill them.

  13. Where in the (Blog) World Is Scott Aaronson? « oh tempo le tue piramidi Says:

    [...]  [...] Where’s the passion he showed just four years ago? Eccolo qui, Quantum computing in the newz, di sfuggita, come sempre ultimamente, a commentare il primo premio Nobel in assoluto per ricerche [...]

  14. Kenneth W. Regan Says:

    Re. your intro, maybe you need a Vice President who can go out and do the dirty work for you. Indeed, both targets have 4 letters beginning with R—it’s karma! :-)

  15. Vadim Says:

    Another Scott,

    When you say “They have built the only computing system ever attempted that uses quantum mechanics.” do you realize that *that’s* the crux of the question? If it was so obvious and (original) Scott was acting unconvinced, then you might have a point (though your way of making it still wouldn’t help the debate).

  16. kodlu Says:

    Hi Scott,

    What about this “breakthrough”, so far as I can tell it’s not really clear if the approach is scalable, and what about 200 microseconds of coherence time? Is that good enough?

    http://www.nature.com/nature/journal/v489/n7417/full/nature11449.html

    A single-atom electron spin qubit in silicon
    Nature 489, 541–545 (27 September 2012)

    A single atom is the prototypical quantum system, and a natural candidate for a quantum bit, or qubit—the elementary unit of a quantum computer. Atoms have been successfully used to store and process quantum information in electromagnetic traps, as well as in diamond through the use of the nitrogen–vacancy-centre point defect. Solid-state electrical devices possess great potential to scale up such demonstrations from few-qubit control to larger-scale quantum processors. Coherent control of spin qubits has been achieved in lithographically defined double quantum dots in both GaAs (refs 3–5) and Si (ref. 6). However, it is a formidable challenge to combine the electrical measurement capabilities of engineered nanostructures with the benefits inherent in atomic spin qubits. Here we demonstrate the coherent manipulation of an individual electron spin qubit bound to a phosphorus donor atom in natural silicon, measured electrically via single-shot read-out. We use electron spin resonance to drive Rabi oscillations, and a Hahn echo pulse sequence reveals a spin coherence time exceeding 200 µs. This time should be even longer in isotopically enriched 28Si samples. Combined with a device architecture that is compatible with modern integrated circuit technology, the electron spin of a single phosphorus atom in silicon should be an excellent platform on which to build a scalable quantum computer.

  17. Mitchell Porter Says:

    “Another Scott” #4 says “They have built the only computing system ever attempted that uses quantum mechanics.”

    But you can’t tell if it is quantum mechanics that did the work, or something else!

  18. Scott Says:

    kodlu #16: Dunno! The question, with quantum computing, typically involves issues like how the coherence time compares to the gate time, and whether the coherence time goes down as you add more qubits (because of crosstalk) … all of which affect the final thing you care about, namely, whether you can cross the threshold for quantum fault-tolerance.

  19. Roy G. Biv Says:

    “Where’s the passion he showed just four years ago?…It’s as if his mind is off somewhere else, or as if he’s tired of his role as a public communicator and no longer feels like performing it.”

    Don’t worry, Scott. Perhaps THIS guy/gal whom you prophesied about is on their way to share the workload?

    “A Prophet Will Arise”
    http://www.scottaaronson.com/blog/?p=19

    w.r.t D-Wave:

    Time to invoke the old adage: “When in doubt, go with the Scott.”

    Also, of what use could “symbol-pushing” be?

    All I know is that there was once this guy that pushed symbols to derive ‘E=mc^2′, among others, but if I recall correctly, they proved to be of little value, and he is to this day still considered to be a “giant assclown”.

  20. Aram Says:

    Did D-Wave built a “superconducting foundry”? I thought they bought their superconductors from an undisclosed location. Perhaps JPL?

  21. Miquel Says:

    Scott #3: Judea getting the Turing was HUGE, indeed :)

    Regarding D-Wave. Leaving aside whether or not people in the academia have a hard time getting off their high horses and look at “practical matters”, the facts are:

    1) D-Wave get a LOT of hype. See this Nature blog post here:

    http://blogs.nature.com/news/2012/08/d-wave-quantum-computer-solves-protein-folding-problem.html

    From the beginning of the article:

    [...]A quantum computer from the private company D-Wave, based in Burnaby, British Columbia, has solved the puzzle of how certain proteins fold.[...]

    This might sound as picking nits, but I have troubles with the wording. I think it should rather read like this:

    [...]A quantum computer from the private company D-Wave, based in Burnaby, British Columbia, *has been shown to be capable of solving* the puzzle of how certain proteins fold.[...]

    Ok, I might buy that the longer, more precise version sort of stoles the thunder of the whole thing. But the wording is a bit misleading.

    2) I do sincerely think it is remarkable that a computer with components that exploit quantum mechanics effects is able to solve *any* computational problem at all. But then we get to my main reservation about the whole project of quantum computation.

    Are we really computing – as in finding the answer of a decision problem and being able to show the answer to be right – or are we rather “simulating” – here we don’t get answers, but actually “outcomes” of a simulation.

    Quoting from (Perdomo-Ortiz, Dickson et al, 2012) on August Nature issue:
    [...]
    Even though the quantum device follows a quantum annealing protocol, the odds of measuring the ground state are not necessarily high. For example, in the 81 qubit experiment, only 13 out of 10,000 measurements yielded the desired solution. We attribute these low-percentages to the analog nature of the device and to precision limitations in the real values of the local fields and couplings among the qubits in the experimental setup. When compared to other problem implementations, physical problems such as lattice folding lack the structure of the Ramsey number problem
    [...]

    So, out of 10,000 runs or simulations, they get 13 “outcomes” which correspond with an “answer” to the protein folding problem instance they were trying to solve. Nothing is said about how long did it take to make those measurements, either. There was any kind of speed-up? That’s quite a meaningless question when one can’t be sure that the “protein folding computer” gives sound answers when the lever labelled as “Solve It!” is pulled.

    Let’s not forget either that in order to recognize those lucky outcomes, one needed to compute first the answer… that is solving a NP-hard problem with a classical computer :)

    Is this whole thing interesting from a practical perspective? Yes it is, but perhaps not for the purposes that D-Wave advertises it today. We’ll see that in twenty years, I guess.

    Certainly it’s an awesome showing of the capabilities of present-day nanotechnology and materials science. Another thing is to consider whether it has any practical consequences for Computer Science: from that point of view this whole thing is a bit “meh”.

    Is this whole thing interesting from a theoretical perspective? Damn, yes, it is.

    Does anybody remember that we know how to solve the TSP cajoling some yeasts on a Petri dish to do funky stuff? That was quite a thought-provoking result, at a “practical” level, because it shown to what degree is possible to manipulate tiny living organism to program it to conduct a quite complex tasks. Not really because it was more useful than TSP solvers implemented on classical computers.

    But there isn’t, as far as I know, any company selling any yeasts circus inside a huge black box for millions of dollars a pop, either…

  22. Uri Says:

    “Another Scott” #4 says “They have built the only computing system ever attempted that uses quantum mechanics.”

    Well, in a sense, all computing systems use quantum mechanics. If Another Scott has a spare 100 million, I have a great quantum calculator to sell him.

  23. Quantum Cash Registers? « Pink Iguana Says:

    [...] Aaronson, Shtetl-Optimized, Quantum Computing in the newz, here.  Today the 2012 Nobel Prize in Physics was awarded jointly to Serge Haroche and David Wineland, [...]

  24. NS Says:

    @Another Scott (Comment #4):
    Do you have anything to say about the technical points being raised in the current blog-post ?
    (Seems like you saw some part of the blog, some number (100M) and you had an emotional outburst, which was not aligned with the key topic of this blog post.)

    Also $100M might be a small amount for D-Wave, but that can not be a reason to make false claims.

  25. Alexander Says:

    Scott #3, may be interesting (if you have not read already): http://www.reuters.com/article/2012/09/19/us-science-nobel-predictions-idUSBRE88I06F20120919

  26. Daniel Lidar Says:

    Our team at USC has been hard at work characterizing D-Wave’s Rainier “DW1″ chip (108 functional qubits) since late last year. See http://www.isi.edu/research_groups/quantum_computing/home for some background. Experimental results attesting to quantum effects in the DW1 are being written up at this time.

    I’d like to briefly address Scott’s points:

    (1) Two-qubit entanglement: given what we know about the chip, there is virtually no doubt that entanglement can be generated during the adiabatic evolution from the transverse field to the final Ising Hamiltonian: ground state entanglement is a property of such Hamiltonians, and it not hard to come up with problems for which the gap is large enough that the system is in the ground state. It is a different matter to measure it given the limitations of the DW1, since only measurement in the computational basis is possible, at the very end of the evolution. And even if we were able to measure this entanglement, it’s not clear how much is required for a speedup.

    In this context it is also an interesting and independent question how relevant continuous entanglement measures are for quantum speedups (in the circuit model), given Van den Nest’s recent “Universal quantum computation with little entanglement” http://arxiv.org/abs/1204.3107. Any comments about its implications?

    (2) Special-purpose computer: without trying to nitpick the characterization of D-Wave’s machine as a “special-purpose computer for solving one specific optimization problem”, I’d like to stress that the DW1 is programmable, as its successors will be, and can be used to try to solve any quadratic unconstrained binary optimization (QUBO) problem that is embeddable on the chip’s Chimera connectivity graph. Here by “solve” I mean finding the ground state of the corresponding Ising model, and of course the coupling constants and the magnetic fields specifying the Ising problem—the “program”—can only be specified up to a certain precision (3 bits on the DW1, more on future generations). The QUBO class of problems is broad and includes many problems of practical interest, e.g., in machine learning. In fact it is NP-hard, though needless to say no one is promising an exponential speedup. However, the “embeddable on the chip” caveat is important: solving the embedding problem for a given optimization problem can be non-trivial. To sidestep the embedding issue we have been experimenting with random QUBO problems for many months at USC, and the DW1 is pretty good at finding the corresponding Ising ground states. Just how good is the subject of an upcoming paper.

    An area where contributions from computer science theory could make a big difference is in finding examples where QUBO problems provably yield a quantum speedup. I hope this challenge will be picked up by someone reading this blog.

    One might argue that special-purpose classical computers might do very well at solving the same class of QUBO optimization problems that D-Wave’s machines are designed to solve, if developed over 10 years and with a $10^8 budget. And it is likely that we will keep seeing significant improvements in special-purpose classical algorithms. Meanwhile the question of whether D-Wave’s technology will in the long run outperform such special-purpose classical computers can be viewed in the broader context of the power of open system adiabatic quantum computing, which is still unresolved due to the absence of a theory of fault tolerance for the adiabatic model.

    (3) Coherence: I’d agree that the role of coherence isn’t as clear in open system adiabatic computation as we’d like. Here too there is a nice opportunity for theoretical advances.

  27. Scott Says:

    Daniel Lidar #26: Thanks very much for the informative comment! I don’t care much either about the quantitative entanglement measures that are typically studied. I agree that those measures can be very close to zero (though not equal to zero!) without precluding a quantum speedup, as happens for example in the DQC1 model. My point was a more qualitative one: that as yet, we have no direct evidence that the intermediate states in the D-Wave machine look like the sorts of states that could plausibly give rise to a quantum speedup. Entanglement is just one feature among others that we would expect of such states. Anyway, I really look forward to seeing your upcoming paper, and maybe updating my assessments based on it! I might have more to say, but I have to run to teach my class…

  28. Greg Kuperberg Says:

    It’s quite a contrast: Haroche and Wineland, who just won the Nobel prize in physics for building quantum devices, vs D-Wave, which doesn’t yet deserve to win any prize for anything.

    While I respect Daniel Lidar’s interest in D-Wave’s “qubits”, I think that some people might get the wrong impression about what this really means. With most people in quantum computation, or really any area of science, the question is how much they have achieved. With D-Wave, after their highly unusual press conference in 2007, the question changed from their achievements to their credibility. In one day they managed to contradict both the PCP theorem, which says that approximate solutions to many NP-hard problems are still NP-hard; and Nayak’s theorem, which says that one qubit cannot hold more than one classical bit of information. That’s really burning one’s bridges. D-Wave has not been very successful at rebuilding them, so credibility has remained the issue ever since.

    Arguably things are not quite that terrible for D-Wave at the experimental level. I don’t remember that a single thing was said about them at the theory-dominated QIP conference at the 2012 meeting, but I heard that they have at least some presence at the experimental SQuInT meeting. Which is fine, as long as it is understood that this is the dark horse project, at best. As far as I know, studying D-Wave One is looking for diamonds in the junkyard. Again, that’s a valid research plan, sometimes it even works. (Although it’s easy to be fooled by cubic zirconia or even colored glass.)

    But it’s not like what Haroche and Wineland did. They found actual diamonds in diamond fields. And I shouldn’t single them out, because there are other experimentalists who also do great work on quantum devices. Also Haroche and Wineland are more reserved people than I am; they have the wisdom that I wish I had of not wanting to talk too much.

  29. Greg Kuperberg Says:

    If you want to understand what I mean by seeking diamonds in the junkyard, you can look at a recent paper that uses D-Wave “qubits” to calculate Ramsey numbers. (I put “qubits” in quotes because one of the main questions is whether there it is really justified to call them qubits.) The Ramsey number R(m,n) is the smallest integer R such that if you have R people at a party, at least m are mutual friends or n are mutual strangers. The Ramsey number R(3,3) is a popular grade school math problem. (The answer is 6.) It is famously difficult to calculate most values of R(m,n).

    The paper did include a calculation of R(3,3), but the main result was the calculation of R(2,n) for large n. So, read this question slowly and see if you can answer it: How many people do you need at a party in order to know that at least 2 are friends, or at least n are mutual strangers?

    Congratulations if you can prove that R(2,n) = n, but you should know that R(3,n) is a harder question.

  30. Greg Kuperberg Says:

    Finally, I also don’t want to be too much of a naysayer of D-Wave as a business venture. That’s a tough question, because brand names, venture capital, and corporate management are not the same thing as ideas. I have no idea whether D-Wave is a good investment.

    To pick a historical example, I always thought of the Shell Oil logo as a clever metaphorical reference to oil drilling. It is that, but I found out recently that Shell began in England as a company that imported actual seashells. At that time it had nothing to do with oil at all. If you said then that trading seashells has a limited future, that would have been prescient, but obviously it did not follow that Shell has no future.

    Or, a darker example is Coca-Cola. Coca-Cola began as a notorious cocaine brew. That sounds like a weird rumor that bounces around junior high recess yards, and it is, but it also happens to be true. No one knew in 1900, least of all the people who ran the company, that they could take over the world with only sugar, caffeine, and carbonation. They worried that they were giving up the store when the feds forced them to remove the cocaine from their product.

    Anyway, if the main question about scientists is usually their achievements, the main question about businessmen and politicians often is their credibility. It’s not my favorite question at all, and I doubt that it’s Scott’s favorite question either, so I totally understand his announcement to retire as a critic of D-Wave. But he did ask me to comment on this thread, so here we are.

  31. Alexander Says:

    I would like to hear a comment if Nayak-Holevo theorem is in agreement with sentence above (got from Nobel Prize site):
    [...] a quantum computer of only 300 qubits could hold 2^300 values simultaneously, more than
    the number of atoms in the universe. [...]
    I myself did not found nothing terrible in such a text used for popularisation of some difficult ideas.

  32. Greg Kuperberg Says:

    Alexander – That’s a stupid thing to say and I don’t know who wrote the Nobel Prize committee’s copy. Yes, that does violate the Nayak-Holevo theorem, but only at the level of lip service. That’s very different from the D-Wave demonstration, in which a quantum device with only 16 qubits supposedly solved a Soduku. The theorem says that a Sudoku doesn’t fit in 16 qubits, not even close. If they only had 16 “qubits” at the time (qubits or weaker), then the quantum device did NOT solve the Sudoku.

    Turning from the topic of D-Wave to the topic of science journalism, it’s fine to simplify matters, but I am against the idea of saying things that are outright wrong just for the sake of science popularization. It’s unnecessary, and worse, it’s self-reinforcing. If you keep repeating falsehoods, then the truth confuses people because it contradicts prior explanations. Certainly the 2^n amplitudes of n qubits aren’t stored data, any more than 2^n probabilities of n bits are stored data. If they were stored data, then Scott’s statements at the top, “Quantum computers are not known to be able to solve NP-complete problems in polynomial time, and can be simulated classically with exponential slowdown,” would both be wrong.

    In fact, the main reason that science journalists claim that n qubits can hold 2^n “values” is not to make the topic easier to understand, but to make it more exciting. (Falsehoods are rarely all that useful for the former purpose.) Well, the truth doesn’t need help. It takes science out of the hands of scientists and turns it into self-accountable infotainment.

  33. Scott Says:

    Alexander #31: I understand what the Nobel committee was trying to say, but I myself would never say it that way, precisely because it leads people to intuitions at odds with Holevo’s Theorem and the many other related things we know. I would say instead that in quantum mechanics, describing the state of 300 particles requires a vector of around 2300 complex numbers, which is indeed an extraordinary fact about physics. But then, in the very next sentence or so, I would add something about the vector not being directly observable, and about the whole challenge in quantum computing being to tease useful information out of the vector via measurements.

  34. Greg Kuperberg Says:

    Whereas my point of view is that it isn’t even extraordinary that this vector requires 2^300 complex numbers, since after all a vector of probabilities already requires 2^300 real numbers. I think of the quantum state (or more precisely, the corresponding density operator) as a fat generalization of a probability distribution. So actually I don’t think of it as being “there” in the first place, except in a very restricted sense. And I think of quantum algorithms as a kind of grand extension of randomized algorithms. I don’t think of them as using measurements to tease answers out of a colossal amount of data that’s otherwise hidden behind a curtain. I think of the measurements as observations of random variables.

    And I should explain that when I’ve talked to Scott in person about these metaphors, he doesn’t really disagree with mine and I don’t really disagree with his, even though he explains things a little differently.

  35. Scott Says:

    I do indeed have lots of sympathy for Greg’s viewpoint — in my own research career, I’ve exploited the close analogies between quantum states and classical probability distributions over and over and over.

    But, as Greg knows perfectly well, one place where the analogy breaks down is that we can always regard a probabilistic process, if we like, as just a deterministic process that gets a random string r as an additional input—in which case, the probability vector reflects nothing more than our ignorance about r. For a quantum process producing a quantum state, no similar interpretation is available. If I had to give a single reason why quantum states seem more “there” than classical probability distributions (even if less “there” than tables and chairs), that would be the one.

  36. Gil Kalai Says:

    As a scientific/technological idea, to build and test the behavior of machines where traditional semiconductors are replaced by superconductors looks (naively) to me as a very nice idea. (I hope I describe it correctly.) And it may lead to a valuable and perhaps even decorated scientific research. (It is a bit unfair to compare it with Nobel-prize winning research.) The way D-wave, which is a commercial company, combines also pure research seems appealing to me.

    It is also perfectly ok to be skeptical regarding the specific direction D-wave is taking, and discussing it can be interesting. It is even ok to hope or dream that quantum computers will give major advantage in solving NP-complete problems. Many people who are not experts think so, but for most of them the technical distinctions and precise implications are not clear anyway. (Beside that many people think that NP stands for “not polynomial.”) Once I heard from a high official of a major company that supports quantum computer activity, a statement about these machines being able to solve NP complete problems. I (and Noga who was also there) mumbled something to the fact that this is unknown and in doubt, but then I suggested to him to double their support to QC efforts (and I sincerely think this was a good suggestion).

    Some aspects of the D-wave 2007 PR efforts were perhaps unfortunate. But this was in 2007.

  37. Greg Kuperberg Says:

    Scott – Yes, the analogy breaks down at that point. If it didn’t, it wouldn’t be an analogy, it would be an equality! Quantum probability has to differ from classical probability somehow, so any analogy can’t extend all the way.

    Anyway I maintain that a qubit does not know its amplitudes any more than a coin knows the probability with which it is heads. In fact, a qubit can be a coin and doesn’t really know whether it is one!

  38. Alexander Says:

    Greg, #37, qubit should be compared with unfair coin and we may encode lot of information in such coin, the problem that in example with qubit we may not extract all that unlike example with coin

  39. Ronald de Wolf Says:

    Just to add my 5 cents of support against the trolls: I thought this post was very moderate, reasonable and well-balanced.

  40. Alexander Says:

    Greg #34, #37 Maybe better example is some random number generator for many correlated binary variables. You need some internal memory to keep the parameters of the distribution and that memory may need to have exponential size with respect to number of the variables if the correlations are general enough.

  41. Gil Kalai Says:

    Thinking primarily about QM as a theory of non commutative probability which is somiething I learned from both Greg and Itamar Pitowsky is a very convenient point of view. Is it still necesary from this point of view to subscribe to an interpretation like MWI?

  42. John Sidles Says:

    Please let me express my respect for Haroche and Wineland’s groundbreaking experiments, in which the assumption of flat quantum-dynamical state-space geometry yields correct predictions for even the most incredible experiments.

    And let me also express my respect for the recent work by Harvard’s Alán Aspuru-Guzik and colleagues, in which the assumption of non-flat quantum-dynamical state-space geometry yields correct predictions for even the most incredible experiments.

    A question at the heart of the Kalai/Harrow FTQC debate, is simply this: How can these two successes be reconciled?

    One reasonable reconciliation is straightforward: perhaps the assumption of flat quantum-dynamical state-space geometry is less essential than has been widely assumed.

    That would be fun! :)

  43. Mitchell Porter Says:

    Hearing Daniel Lidar speak positively of D-Wave is a surprise, and has made me think they may be getting somewhere after all.

  44. Scott Says:

    Gil #41: Greg can speak for himself, but I think a large part of the point of calling quantum mechanics a “generalized probability theory” is the desire to avoid MWI-talk.

  45. Alexander Says:

    I have read http://viterbi.usc.edu/assets/145/81696.pdf that just D. Lidar in 2010 convinced N. Allen from Lockheed to take look on D-Wave One …

  46. Greg Kuperberg Says:

    Gil – Scott is correct. Part of the merit of quantum probability is to avoid the mental baggage of something like the many-worlds interpretation. The charitable interpretation of MWI is that it is kind-of like path summation, and path summation is indeed a useful technique in both classical and quantum probability. And part of the merit of quantum probability is to clarify the Copenhagen interpretation of quantum mechanics for mathematicians, computer scientists, and even physicists, and to make CI and QM more believable for these audiences.

    The less charitable interpretation of the many-worlds interpretation is that there isn’t even a consistent story of how many worlds there are, because the criterion is basis-dependent. It’s not very helpful to people who have trouble believing quantum mechanics. Many mathematicians, perhaps most of them, know that they have done no work to properly believe it and find it confusing. Even many physicists have somewhat undeveloped intuition.

  47. Greg Kuperberg Says:

    Gil – As for D-Wave: Actually, almost every aspect of D-Wave’s public relations in 2007 was unfortunate. Not just some aspects. Since then you could say that they have gotten better. Now merely many aspects of their PR are unfortunate.

    You shouldn’t think that criticizing D-Wave is beating up on an underdog. From the point of view of actual results, this is somewhat true, but from the point of view of funding, it’s totally the opposite. These people with misrepresented, marginal results to date could be the best-funded quantum computation group in the world. And the dreadful flyer from USC shows you what happens when no one criticizes them. Hype advances further and they get even more resources.

    (I had not seen the flyer before; I thank Alexander for posting it.)

  48. John Sidles Says:

    Greg Kuperberg says: “Many mathematicians, perhaps most of them, know that they have done no work to properly believe [the many-worlds interpretation (MWI)] and find it confusing. Even many physicists have somewhat undeveloped intuition.”

    Greg, your view delightfully illuminates the view of Saunders Mac Lane, who writes (Hamiltonian Mechanics and Geometry, 1970):

    Often a book on physics will contrast a mathematical presentation of an idea (using coordinates) with a physical presentation (not using coordinates); in such cases the contrast is really between two mathematical presentations, one with coordinates and one coordinate-free.

    Nowadays, in mathematical dynamics there is an accelerating trend toward coordinate-free notations that capture (in Mac Lane’s phrase) the “physical presentation” of the dynamics. Conversely (in my experience) the main reason that mathematicians have difficulty understanding quantum physics is that Dirac notation is so clumsy, as to require physical intuition to overcome its deficits. Ouch! :)

    Dirac’s assessment of his own The Principles of Quantum Mechanics (1930) is broadly compatible with Mac Lane’s point-of-view:

    “It’s a good book, but the first chapter is missing.”

    Or as Dirac wrote one one year later (Quantised singularities in the electromagnetic field, 1931), at considerably greater length

    The steady progress of physics requires for its theoretical formulation a mathematics that gets continually more advanced. This is only natural and to be expected. What, however, was not expected by the scientific workers of the last century [19th century] was the particular form that the line of advancement of the mathematics would take, namely, it was expected that the mathematics would get more complicated, but would rest on a permanent basis of axioms and definitions, while actually the modern physical developments have required a mathematics that continually shifts its foundations and gets more abstract.

    Non-euclidean geometry and non-commutative algebra, which were at one time considered to be purely fictions of the mind and pastimes for logical thinkers, have now been found to be very necessary for the description of general facts of the physical world. It seems likely that this process of increasing abstraction will continue in the future and that advance in physics is to be associated with a continual modification and generalization of the axioms at the base of mathematics rather than with logical development of any one mathematical scheme on a fixed foundation.

    […] The most powerful method of advance that can be suggested at present is to employ all the resources of pure mathematics in attempts to perfect and generalise the mathematical formalism that forms the existing basis of theoretical physics, and after each success in this direction, to try to interpret the new mathematical features in terms of physical entities.

    Or as Saunders Mac Lane put it more succintly (Mathematics, form and function, 1986):

    “It has taken me over fifty years to understand the derivation of Hamilton’s equations.”

    Given that the time interval Hamilton to Mac Lane (1833 to 1986) was about 150 years, perhaps we may reasonably hope to achieve a comparably natural appreciation of Dirac’s 1930 quantum dynamics — and in particular, a reasonably natural appreciation of the Harrow/Kalai debate — by (roughly) the year 2083.

    This mature understanding perhaps will arrive sooner, if we are diligent … and creative … and (if we are lucky) we are inspired by the unexpected efficacy of D-Wave’s technology! :)

  49. Curious programmer Says:

    Greg Kuperberg: nowhere in any of your tirades against D-Wave do you ever say anything that backs up your premises. In fact I recall that after the 2007 demo someone explained in some detail how the sudoku solver worked, and it was eminently sensible.

    In reality (not the fantasy world you seem to live in) D-Wave’s scientific and engineering accomplishments are extraordinary. I fact I don’t believe there is any historical precedent for what they’ve already accomplished and they are not done.

    I humbly suggest if you want to be taken seriously you should start acting more like a scientist and at least gain some basic understanding of a subject before talking about it. Unfortunately you come off sounding a little silly which I’m sure you’re not.

  50. Daniel Lidar Says:

    Mitchell #43: It’s easy to get caught up in the hype, whether it’s pro or anti D-Wave. My decision to study their technology and to assemble a team at USC to perform independent “quantumness” and benchmarking tests using one of D-Wave’s machines was motivated in part by a desire to get past the hype and develop a thorough technical understanding of their system. As I mentioned in my previous comment we have a large experimental and theoretical effort underway at USC and ISI (our Information Sciences Institute, where the DW1 is located), designed to independently assess the quantumness and performance issues, and to study and develop applications.

    I’ll add that I felt this was a course worth embarking on after reading several of D-Wave’s technical publications (a good example is http://arxiv.org/pdf/1004.1628v2.pdf), talking to their scientists and engineers, and making multiple visits to their lab. It’s been an exciting journey of discovery so far, whose findings we will soon start to make public.

  51. Greg Kuperberg Says:

    Daniel – After seeing the article in the USC Viterbi newsletter, I have trouble believing that you want to step away from the hype. The article is evidence against that assertion.

  52. Raoul Ohio Says:

    WRT Greg 34:

    Most of us have worked at, and enjoy, gaining understanding of topics in the STEM area. This usually involves working through standard examples in detail.

    Another aspect is that sometimes we create or discover a picture (model, representation, …) that brings a large amount of information into focus. For example, seeing a 3D projection of the bessel function J(nu;x) — amplitude as a function of x and nu — pretty much shows you how bessel functions work.

    The statement “quantum algorithms as a kind of grand extension of randomized algorithms” helps me organize what little I know about QC.

  53. Gil Says:

    Dear Greg, thanks for your take on MWI. Regarding D-wave, I agree with Ronald that the post and letter were very reasonable. I think that it is mainly for experimentalists to say how promising D-wave’s methods are for creating useful technology or science.

  54. J. Stanson Says:

    Greg # 51
    Attacking Daniel Lidar for his comments here is unjustified and uncool. He seems to be the only one of you lot doing any sciencing at all. Greg says: “the way I view what D-Wave did 5 years ago would violate these obscure theorems, so they can’t have done anything useful at all to date!” Scott says: “D-Wave may have done X, but they still haven’t done X+i, where i = [1, infinity]!”

    Daniel says: “D-Wave may or may not have something here, and I want to DO more to find out.” So he actually gets one and tests it, like an actual scientist!

    Now, these DW machines aren’t easy to come by, so it seems that getting one requires a bit of politics, and maybe a bit of hype to get there, but goddamn! He’s DOING something to pursue the matter rather than just whining all the time and playing the antagonist against people who are trying to do something amazing.

    Also, anyone who has been involved in anything newsworthy knows that news coverage (what you guys seem to think is PR, but in reality is completely out of D-Wave’s control) is not a good source for technical accuracy.

  55. Bram Cohen Says:

    As someone who has much more experience with venture capital than the rest of you, I feel pretty confident in saying that if D-Wave’s investors understood and believed that what they’re paying for is a scaling up of something which might have magic pixie dust in it but hasn’t demonstrated that it’s scaling up anything more than regular dust, they’d be PISSED. But VCs tend not to do any real due diligence, so they get what’s coming to them.

  56. Scott Says:

    J. Stanson #54 (whose IP address is also from Vancouver):

      Greg says: “the way I view what D-Wave did 5 years ago would violate these obscure theorems, so they can’t have done anything useful at all to date!”

    Err, the PCP Theorem and Nayak’s theorem (a modern strengthening of Holevo’s Theorem) are some of the least obscure theorems in town! They’re centerpieces of TCS and quantum information respectively that we regularly teach in classes.

    However, I do agree with the larger point that, if D-Wave eventually succeeds in building a device that demonstrably exploits quantum effects to get a computational speedup, then no one will care anymore about how bad their misrepresentations of the science were back in 2007. “That was then, this is now,” they’ll say. And they’ll have a point. So, this is probably a genuine difference between me and Greg.

      Scott says: “D-Wave may have done X, but they still haven’t done X+i, where i = [1, infinity]!”

    Dude, I’ve only felt the need to say that because of persistent, almost-never-challenged claims in the press (and, at least sometimes, D-Wave’s own marketing materials) to have done X+i, for i = [1, infinity]. I’ll grant them X if they’ve done it, but I see pointing out when X ≠ X+i as simply part of my job.

      Daniel says: “D-Wave may or may not have something here, and I want to DO more to find out.” So he actually gets one and tests it, like an actual scientist!

    I’m glad Daniel and others are doing these experiments, and I look forward to hearing the results. When they announce them, though, you should expect them to be discussed critically by others as much as if they’d come from D-Wave itself. That’s, y’know, how science works: some people claim something, then other people try their hardest to shoot down the claim. If they fail, the claim is strengthened. Everyone—me, Greg, Daniel, etc.—gets to play both the “claiming” role and the “shooting down” role at various points in their careers.

  57. Alexander Says:

    Scott #33, #56 I already during long period of time aware about idea with application of Holevo’s theorem from area of quantum communications as no-go to some class of problem in quantum computation, but without references (maybe only a Zalka’s short note). Nayak theorem indeed may be more appropriate for such no-go tasks, but again, references, please…

  58. Greg Kuperberg Says:

    The issue for me is not just that D-Wave misrepresented the science, it’s that they misrepresented themselves. It would certainly be silly if they claimed to be young-earth creationists, but no worse than silly. If they claim that their “quantum computers” can do things that are mathematically impossible, that’s completely different. They “demonstrated” solving a Sudoku with 16 qubits. That’s mathematically impossible. And they said that their computers wouldn’t fully solve NP-hard problems, but would nearly solve them. Doing one without the other is also mathematically impossible.

    If they are going to seek advantage with misrepresentations of this order, then if anything, I’m *glad* that they might think of the theorems that they contradicted as obscure. That’s how you catch people in contradictions! Not with traps that they can see and walk around, but with traps that they could know about but don’t.

    And the misrepresentations don’t stop. As explained in the USC newsletter, Lockheed bought the “D-Wave One” for help with its intractable code verification problems. While using qubits for this purpose is not strictly mathematically impossible, I can hardly think of two areas of computer science that are *less* related than quantum computing and code verification. Quantum computing is about speed of algorithms. Code verification has fairly little to do with speed of algorithms. Code verification is about making computer programming more rigorous, which is a bureaucratic problem that has rarely been helped by intensive calculations. Particularly not the verification of messy, real-world code like the code in Lockheed’s fighter jets. Of course it’s a cliché in science that everything is related to everything, a cliché with some truth to it. But where do you go from here? Promising better computer printers with supercooled qubits in them?

    I take Scott’s point that if D-Wave ever does achieve anything important in quantum computation, people will forgive it for its past sins, or even declare them irrelevant. However, if you’re too worried about that, then you can never rebut any assertion from anyone, no matter how preposterous. This is a story that — in 2012 and not just in 2007 — has funding distortion written all over it. There has got to be a way to discuss that in public.

  59. Scott Says:

    Alexander #57: Here you can find the 164 quantum computing and information papers on Google Scholar that cite Nayak’s paper on quantum random access codes. (You can also look for stuff that cites the earlier paper by Ambainis, Nayak, Ta-Shma, and Vazirani that Nayak improved.)

    If you’d like to see where I’ve used Nayak’s theorem in my own work on quantum complexity theory, look no further than here, here, and here.

  60. rrtucci Says:

    “Err, the PCP Theorem and Nayak’s theorem (a modern strengthening of Holevo’s Theorem) are some of the least obscure theorems in town! They’re centerpieces of TCS and quantum information respectively that we regularly teach in classes.”

    searched google for “nayak’s theorem”
    Got 14 hits

  61. rrtucci Says:

    searched google for rrtucci
    got 8,180 hits

    I’m famous!

  62. Alexander Says:

    Scott #59, it may be relevant indeed, but I am about no-go results for quantum computations. In classical computation result of manipulation with milliards bits often expressed with very short output, or maybe even single yes/no bit. I do not need to obtain all these milliard bits.

  63. Scott Says:

    rrtucci #60: As I tried to explain before, when Greg wrote “Nayak’s theorem” he really meant “the modern, computer-sciencey version of Holevo’s theorem” (which also goes by the ANTV theorem, the quantum random access code lower bound, and other names). I just googled Holevo’s theorem and got 22,600 hits, almost 3 times more than such a famous personage as yourself. :)

  64. Alexander Says:

    rrtucci #60, did you try to enter the same search from other IP? – if you entered the same string many times before, it may change some parameters of search engine.

  65. Scott Says:

    Alexander #62: Obviously Holevo’s theorem doesn’t mean that quantum computation is impossible; no one ever claimed that it does. All it does is to underscore the wrongness of certain ways of talking about quantum computing — ways that, alas, are so pervasive in the popular press that when someone explains how QC actually works they come across as a weirdo.

  66. Alexander Vlasov Says:

    Scott, please be a bit more concrete, that is the wrong popular ways? Why Shor algorithm is possible?

  67. Scott Says:

    Alexander: The wrong way of talking about it is to say that “a quantum computer with only 1000 qubits could store 21000 classical bits.” As I’ve said many times on this blog, that’s true only for a very bizarre definition of the word “store,” a definition that doesn’t entail the ability to get out the bits later. As for “why Shor algorithm is possible,” the short answer is because it exploits interference between positive and negative contributions to an amplitude in a remarkably clever way—a way that turns out to suffice for finding the period of an exponentially-long periodic sequence (and hence for factoring, by classical number theory reductions), but that doesn’t suffice for arbitrary search problems, as you might expect it would if you thought of a quantum computer as just an exponentially-parallel classical computer. For a longer answer, see my Shor, I’ll Do It post (or, of course, any of the countless other expositions of Shor’s algorithm on the web, starting with Shor’s own).

  68. Alexander Vlasov Says:

    PS. #66. Frankly speaking, I have some problem with finding some accurate reformulation of QFA theory on language of quantum network model that would simplify all that for me.

  69. Alexander Vlasov Says:

    Scott #67, O’K. (yet they wrote 2300 “values”).

  70. Joe Fitzsimons Says:

    Alexander: I believe that Nayak’s theorem and the Holevo bound entered the discussion in relation to solving a sudoku problem. I believe the implied argument was that the DWave system has far fewer qubits than are necessary to represent the solution to a sudoku puzzle, since, roughly speaking, Holevo’s theorem proves that you can recover at most the same number of classical bits as the are qubits, while Nayak’s theorem proves that even if you only want to recover some small subset of the bits, if it is not determined a priori, you need almost as many qubits as in the case where you want to recover them all. Presumably the implication, then, is that the superconducting chip was used to perform some smaller subroutine in a larger computation (since the state of the system cannot encode the whole puzzle) and that makes claiming the chip solved the problem somewhat dubious.

  71. Alexander Vlasov Says:

    Joe #70, I have heard about sudoku puzzle first just due to D-Wave, the game is absolutely unknown here. So I am not expert. I just could suggest, that for solution of a puzzle you may need less memory than for storing whole configuration.

    Alexander #69, I failed to enter superscript with html formatting, sorry, it should be 2^300

  72. Greg Kuperberg Says:

    Joe – To be more precise, the D-Wave device at the time had so few “qubits” that their participation in solving the Sudoku, if they participated at all, was provably trivial.

    And consider what happened in a genuine calculation several years later with many more “qubits”. Instead of solving a Sudoku, this later D-Wave device statistically established that if you have 8 people at a party, either 2 are friends or all 8 are strangers.

    But hey, did you know that it’s incredibly difficult to calculate Ramsey numbers? That was in the introduction in this later paper.

  73. Greg Kuperberg Says:

    I am amazed that the same person who says here that he wants to get beyond the hype for and against D-Wave, breathlessly compared D-Wave to SpaceX in a university publication. First of all, SpaceX is not like D-Wave. SpaceX has built rockets that actually fly, while with D-Wave, there is a multimillion-dollar research project to determine if its product is any better than stone soup.

    However, in two key respects, SpaceX really is like D-Wave. One is that the founder and company leader of SpaceX, one Elon Musk, is well known for his hype and his breathless comparisons. He says that the goal of his company is privately funded human vacations on Mars. It could turn out like Shell Oil: SpaceX might be successful, but not by doing what was originally advertised. Unless they switch to implanting memories of vacations on Mars, don’t hold your breath.

    The other (potential) similarity is the real role of SpaceX as a government contractor. In launching unmanned supply rockets to the International Space Station, they haven’t done any more than reinvent the wheel at taxpayer expense. Many people interpret SpaceX’s contracts as a ruse to put the space station on a starvation diet from which it cannot escape. Actually, I think that the space station is a colossal mission to nowhere, so with reservations I am in favor of SpaceX’s participation.

    Which brings us back to Lockheed. It is blue-sky speculation that D-Wave’s products are useful contributions to quantum computing. It is also blue-sky speculation that anyone’s work in quantum computing is useful for software verification. So this is blue sky research squared. On the other hand it is Lockheed’s stated interest. If they spend money on this, then a pacifist might like it better than if Lockheed builds things that actually kill people.

  74. Raoul Ohio Says:

    Greg 73,

    I totally agree with your points in 73. However, I do give SpaceX a little credit, because there are dozens of other companies trying to do the same thing, and SpaceX appears to be the clear leader.

    Another Elon Musk operation is Tesla electric cars. One can argue that Society should invest tons of money setting up infrastructure for electric cars. One could also argue that electric cars will never fly. I am happy to argue this one either way if accosted by a true believer.

    The space station is fully the disaster everyone predicted long before it was built. Its total science output is perhaps 0.001 that of the Hubble, while costing perhaps 1000 times as much, for a round 1E6 productivity ratio. Does anyone have any better estimates than my guesses?

  75. Greg Kuperberg Says:

    The credibility of electric cars in general is a very different question from the credibility of Tesla in particular. Just as the credibility of SpaceX is not the same thing at all as the credibility of space rockets in general.

    If you look at their actual contracts narrowly, Tesla and SpaceX are both at least plausible. They could succeed at a certain scale like Orbital Sciences succeeded, or they could fail like Solyndra failed. However, because of Elon Musk’s personality, both companies are carried forward with excessive hype, even Texas swagger. Not the way to earn my trust.

  76. Barkeron Says:

    Yet I still get called a “fraud” and an “assclown” — in fact, the more moderate I am, the worse the insults seem to get.

    Sorry to hear that, but there’s an explanation for this.

    http://amormundi.blogspot.com/

    America’s not only in the death grip of the cults of evangelism, but also of superlative techno-progressivism. The techno-triumphalist fanboys out there want to believe the coming of the quantum computer is imminent, and like all true believers they react immensely hostile to anyone pointing out the problems with their object of worship.

    Those people are fanatics, so no matter how reasonable the arguments are they cannot be reasoned with.

    They will attack any perceived enemies of the cause with a staunch rabidness. You do good to de-escalate, it’s a loser’s game to try engaging in discourse with them.

    But I do not fear their backlash, so I will bring up the elephant in the room: all indications are that D-Wave is. One. Massive. Scam.

    They built a computer that uses various mathematical and engineering tricks to pretend utilization of quantum computation in order to fatten themselves with delicious investor dollars. Okay, as long as it’s just profiteers and libertarian loons like Bezos who piss away their bucks on it…

  77. Scott Says:

    Barkeron #76: It’s true that one sometimes runs into “techno-triumphalist fanboys” in the blogosphere who are very hard to reason with. But regarding your other point, I’ve met with the D-Wave folks several times, and found no reason whatsoever to doubt their sincerity. More generally, even conditioned on someone making a scientific claim that turns out to be wholly or partly wrong, I’d say the posterior probability that the person was engaging in deliberate fraud is still extremely small. There are just too many other ways to be wrong!

  78. Toby Bartels Says:

    Since I have no opinion on D-Wave, I will comment on interpretations of quantum physics. Scott #44 wrote ‘a large part of the point of calling quantum mechanics a “generalized probability theory” is the desire to avoid MWI-talk’, which is quite correct. But also, there is a many-worlds interpretation of classical probability as well, a generalisation of the frequentist interpretation of probability.

    Ordinarily, frequentists avoid speaking of probabilities of individual events, such as the probability that a specific candidate will win a specific election. (Instead, they would discuss the probability that a method of predicting election results will be correct in the long run, and things like that.) But if you imagine an infinitude of possible worlds, then the probability even of specific events has a frequentist meaning. The MWI of quantum physics is a noncommutative generalisation of this.

  79. Greg Kuperberg Says:

    Toby – Indeed, applying the many-worlds viewpoint to both classical and quantum probability is much more reasonable than declaring that quantum probability needs it and talking as if classical probability is something totally different. Because it becomes clear that you can’t separate them.

  80. Alexander Vlasov Says:

    Greg, accessible transformations are different for quantum amplitudes vs probability distributions – cf hidden subgroup problem approach to Shor. I am not sure, that idea of negativity expressed by Scott in his review is enough to explain impossibility of probabilistic analogue of Shor aglorithm. The explanation based on groups and transformanions may illustrate than amplitudes are indeed may be “here” or at least “more here” than probabilities

  81. Greg Kuperberg Says:

    Alexander – The allowed transformations for quantum amplitudes (or density operators) certainly are different than those that are allowed for classical probability distributions. Just as with Scott’s footnote about this same analogy, if they were no different, then quantum computing would be moot because it wouldn’t be different from classical computing either!

    However, the rules are only so different. The allowed maps for amplitudes are much more like the allowed maps for distributions, then they are like the free-for-all of allowed calculations on a stored list of numbers.

  82. John Sidles Says:

    Gil Kalai and I are sustaining a discussion on Gödel’s Lost Letter (GLL) that is broadly relevant to appreciations of D-Wave technology.

  83. What’s in a Name | Wavewatching Says:

    [...] negative views, as apparent from some comments on my last entry, is worrying. Unbeknownst to me, Scott Aaronson put up a blog entry about the same time and I didn't immediately pick up on it as I was travelling.  Turns out, the [...]

  84. Henning Dekant Says:

    From my point of view what D-Wave is doing is pretty close to Feynman’s original quantum simulator idea. Yet, it obviously is not a Quantum Turing Machine equivalent. What D-Wave is doing should probably be called quantum co-computing, since a classical machine always needs to be in the mix, and at least theoretically this wouldn’t be necessary for a universal quantum computer.

    On the other hand the very steep degradation of their chips fidelity with temperature increase IMHO clearly indicate that quantum processes (at least tunneling) clearly underlay the machines performance to a significant extend.

  85. Alexander Says:

    May be related http://dabacon.org/pontiff/?p=6694#comments

  86. Greg Kuperberg Says:

    The discussion here was one of the inspirations for this article by me in Slate.

  87. Black Cat in Black Box | Are You Shura? Says:

    [...] fact, the article in Slate continues a discussion in the comments to Scott Aaronson’s post about the Nobel Prize and some over news relating quantum computing. All that may be compared with [...]

  88. Daniel Lidar Says:

    Our first test of quantumness in the D-Wave One chip (which I alluded to in Comment #26) has been posted: http://arxiv.org/abs/1212.1739. Feedback is welcome.

  89. JohnFornaro Says:

    @Raoul Ohio #74

    “The space station is fully the disaster everyone predicted long before it was built. Its total science output is perhaps 0.001 that of the Hubble, while costing perhaps 1000 times as much, for a round 1E6 productivity ratio. Does anyone have any better estimates than my guesses?”

    I know a bit about the ISS. Your percentage estimate 0.001, is an anecdotal opinion; your opinion that ISS is a “disaster” is also only an opinion.

    It is more probably the case that an astronomer places a greater scientific value on Hubble’s output, but a different scientist will place a greater value on the ISS info on the medical effects of zero gee on a human body.

    It is more of an issue that one scientist likes chocolate ice cream and the other likes vanilla.

    I’m a regular poster on nasaspaceflight.com, and the QC issues noted here have come up in the following thread:

    http://forum.nasaspaceflight.com/index.php?topic=31636.0

    Getting back to the topic, thanks to all of you for teaching me more about QC.

Leave a Reply