Slashdot Mirror

Scott Aaronson, a prominent quantum computing expert made comments about some very similar work that is relevant https://www.scottaaronson.com/blog/?p=3512. The short summary is that we should expect people to continue to push up how many qubits can be practically simulatable. But that sort of improvement through clever tricks and the like doesn't really do much to address the more interesting issue of quantum supremacy https://en.wikipedia.org/wiki/Quantum_supremacy, whether there are problems that a quantum computer can solve that a classical computer practically cannot. Note that the "practically" in the previous sentence is really important. Everything a quantum computer can do a classical computer can do with exponential slow down; standard conjectures essentially amount to saying that a classical computer cannot do any better than that.

There are however good reasons to believe P != NP rather than the opposite. Scott Aaronson discusses a whole bunch of them here https://www.scottaaronson.com/blog/?p=122.

The D-Wave computers are very far from universal computers. Each qubit is only able to talk to a small number of qubits very close to it. The specific method that D-Wave is using is a variant of quantum annealing and it isn't clear that this provides any speedup over classical approaches https://www.scottaaronson.com/blog/?p=3192. So for multiple reasons, the IBM approach is very different, and frankly, much more likely to pan out in the long term.

We're getting closer and closer to testing quantum supremacy- the hypothesis that quantum computers can practically solve problems that classical computers cannot do https://en.wikipedia.org/wiki/Quantum_supremacy. Note that this is a practical statement; anything a quantum computer can do, a classical computer can do, but with potentially exponential slowdown. This follows from the fact that BQP https://en.wikipedia.org/wiki/BQP the set of problems that a quantum computer can do in polynomial time is within is contained in PSPACE https://en.wikipedia.org/wiki/PSPACE the set of things that a classical computer can do with polynomial space (since polynomial space calculations live in EXPTIME, the set of things requiring exponential time, the result follows).

It is very likely that before we see genuinely useful quantum computing (e.g. for factoring large numbers or simulating complicated chemical systems) we'll have an answer to the quantum supremacy question. I suspect that it is more likely that we'll have an answer in terms of boson sampling before we have an answer involving a universal quantum computer.

Essentially, boson sampling works by just looking at the distribution of bosons (well for convenience, photons) as they go through very simple optical objects. Boson sampling has two major advantages: first, we know it is actually *hard* in a technical sense for a classical computer to do unless some conjectures that pretty close to everyone believes are false. In particular, Scott Aaronson and Alex Arkipov proved that if a classical computer can do boson sampling efficiently then the polynomial hierarchy will collapse https://www.scottaaronson.com/papers/optics.pdf. For those who aren't theoretical compsci people, the polynomial hierarchy not collapsing is a statement which is only marginally stronger than P!=NP and is very widely believed. This is in contrast for example with factoring large numbers where if it turned out that classical computers could efficiently factor the only major conjecture that would turn out to be false would just be the difficulty of factoring itself. Second, boson sampling is much easier in many respects than what IBM is trying to do which requires much fancier systems, supercooled qubits, careful protection from stray particles, careful preservation of entanglement and all sorts of other stuff. Still, what they are doing is important and very necessary if we're going to actually have practical quantum computers ever.

Because we have direct limits on how much you can do with efficiency. Unless we are wildly wrong about the basic laws of physics, then there are substantial limits to what we can do in a small volume. For example, there are substantial limits on how much computation one can do in a given volume and how much information one can contain in a given volume. See the excellent explanation by Scott Aaronson here http://www.scottaaronson.com/blog/?p=3327. So at a certain point, expansion is your only option. Moreover, expansion is evolutionarily favored: once a small fraction of a species expands a bit, they'll be the ones who like expanding more and will go to more planets and so on.

BTW I haven't read all of it but you may relate to some posts here: http://www.scottaaronson.com/b...

Summary is accurate in that regard. The idea of using Boson sampling to do this came from a paper http://www.scottaaronson.com/papers/optics.pdf by Scott Aaronson and Alex Arkhipov which showed that if a classical computer can do Boson sampling efficiently then certain widely believed conjectures in classical computational complexity would need to be false. In particular, the polynomial hierarchy would collapse https://en.wikipedia.org/wiki/Polynomial_hierarchy.

It performs at about the same performance to ~600 times more slowly, depending on the problem instance. See Scott Aaronson's d-wave blog entries here, or discussion from a previous Slashdot thread.

First these fucks said d-wave wasnt doing any quantum stuff. Then these fucks said it was slower than conventional hardware. Now these fucks say its still slower than conventional hardware if you use a different algorithms that wont solve the same set of problems...

This is not accurate. The first statement is that it wasn't clear that the D-Wave system was engaging in any quantum computation. That's still not clear. Part of the issue here is that it simply isn't completely clear what one means by quantum computation in this context. For example, your laptop's transistors use quantum mechanics in a critical fashion, but they aren't doing quantum computations. The question has always been twofold a) is non-trivial entanglement going on and b) is that entanglement being used to do processing that cannot be easily simulated on a classical system. Those are both strongly connected to questions of efficiency. Right now, the answer to a seems to be yes (although it took forever for the evidence to actually come out).

Your second two sentences are even more wrong. The fact is that it is slower than cheap conventional hardward if one *uses the best known classical algorithms*. That's being used to solve the same problems, as would be clear, if you read the link I gave.

Your insistence that one must use the "the same algorithms" to benchmark is also incredibly wrong in this context, since one cannot use the same algorithms on both at a fundamental level. D-Wave's system uses a variant of an annealing algorithm and cannot run classical algorithms in any meaningful way. In that context, the classical computers are in this sense essentially emulating an annealing process. If you insist that one must use the same algorithms rather than look actual time for solving problems, then the systems are simply incomparable. Actually looking at cost and time to solve problems makes more sense.

As someone else noted.. Google, NASA, etc must be complete idiots for not bowing to the clearly rational flying goalpost these fucks swing around.

Let's recall for a moment that the primary "fuck" you are talking about is Scott Aaronson who is one of the world's most respected quantum computing experts. He's responsible for many major results including the algebraization barrier http://www.scottaaronson.com/papers/alg.pdf and the first substantially non-trivial lower bounds on the basic collision problem http://www.scottaaronson.com/papers/collision.pdf among other work.

But let's for a moment think about what is going on with Google and NASA and consider other explanations that are relevant here. First, both Google and NASA both have major interests in basic research, and there's a valid basic research interest in what D-Wave is pursuing. (I personally consider it unlikely to go anywhere that useful compared to gate-based quantum computing research but that's a judgment call.) Moreover, large corporations and governments like fads: it doesn't take much for some mid-level manager to decide that quantum computing is a shining new thing and realize that the easiest way to jump on the bandwagon is to buy a D-Wave machine.

First these fucks said d-wave wasnt doing any quantum stuff. Then these fucks said it was slower than conventional hardware. Now these fucks say its still slower than conventional hardware if you use a different algorithms that wont solve the same set of problems...

This is not accurate. The first statement is that it wasn't clear that the D-Wave system was engaging in any quantum computation. That's still not clear. Part of the issue here is that it simply isn't completely clear what one means by quantum computation in this context. For example, your laptop's transistors use quantum mechanics in a critical fashion, but they aren't doing quantum computations. The question has always been twofold a) is non-trivial entanglement going on and b) is that entanglement being used to do processing that cannot be easily simulated on a classical system. Those are both strongly connected to questions of efficiency. Right now, the answer to a seems to be yes (although it took forever for the evidence to actually come out).

Your second two sentences are even more wrong. The fact is that it is slower than cheap conventional hardward if one *uses the best known classical algorithms*. That's being used to solve the same problems, as would be clear, if you read the link I gave.

Your insistence that one must use the "the same algorithms" to benchmark is also incredibly wrong in this context, since one cannot use the same algorithms on both at a fundamental level. D-Wave's system uses a variant of an annealing algorithm and cannot run classical algorithms in any meaningful way. In that context, the classical computers are in this sense essentially emulating an annealing process. If you insist that one must use the same algorithms rather than look actual time for solving problems, then the systems are simply incomparable. Actually looking at cost and time to solve problems makes more sense.

As someone else noted.. Google, NASA, etc must be complete idiots for not bowing to the clearly rational flying goalpost these fucks swing around.

Let's recall for a moment that the primary "fuck" you are talking about is Scott Aaronson who is one of the world's most respected quantum computing experts. He's responsible for many major results including the algebraization barrier http://www.scottaaronson.com/papers/alg.pdf and the first substantially non-trivial lower bounds on the basic collision problem http://www.scottaaronson.com/papers/collision.pdf among other work.

But let's for a moment think about what is going on with Google and NASA and consider other explanations that are relevant here. First, both Google and NASA both have major interests in basic research, and there's a valid basic research interest in what D-Wave is pursuing. (I personally consider it unlikely to go anywhere that useful compared to gate-based quantum computing research but that's a judgment call.) Moreover, large corporations and governments like fads: it doesn't take much for some mid-level manager to decide that quantum computing is a shining new thing and realize that the easiest way to jump on the bandwagon is to buy a D-Wave machine.

Someone downvoted you, possibly due to a lack of sourcing. So in case anyone is in doubt, they should look at this blog by Scott Aaronson http://www.scottaaronson.com/blog/?p=2555 and the discussion. Aaronson is one of the top quantum computing experts on the planet. The comments there are also very relevant. Alex Shelby notes that the algorithms that D-Wave has used to compare on conventional (classical) computers are substantially less efficient than the best classical algorithms. We are going to eventually have actual quantum computers, and when we do they will be awesome. Right now, it isn't clear that D-Wave's system can be reasonably called a quantum computer, and is even more clear that they aren't useful at all.

Yep =)

What you are arguing against is a very common, and very wrong, way to explain how quantum computers work. It is notoriously hard to explain it concisely, but even Trudeau did better than that.

You do start by putting all the solutions of the problem in a superposition, but that in itself doesn't help, as if you just try to read it off you will get a random solution. And a random solution you could get just by running a classical computer with a random number generator.

What you have to do is make all the solutions interfere, a delicate coreography of wrong solutions cancelling each other and correct solutions being reinforced. After that you make a measurement, and get a correct solution with high probability.

Quantum computing can be described as a method, a technique, which allows for the computer for a given task to take a peak into the future and to read the answer from the future back to the present.

This is completely wrong. There are in fact computational models that have been worked out about what a computer that could peak into the future would be like and they are insanely more powerful than quantum computers. See http://www.scottaaronson.com/papers/ctc.pdf. Quantum computing has nothing remotely like what you've said. I suggest for an actual primer on the topic reading Scott Aaronson's excellent book "Quantum Computing Since Democritus" which doesn't require anything beyond a little basic linear algebra. And in the meantime, if you don't know much about a topic, maybe don't make extreme policy suggestions?

For an actual summary of this research see http://www.scottaaronson.com/blog/?p=2673 by Scott Aaronson who is a quantum computing expert. The key thing here is that they factored 15 with high probability without having to sort of cheat by making a circuit that was more likely to work if one suspected that 15 had factorization resembling 3*5. As usual, this is getting completely overblown by the popular press. It is an important step towards actually making quantum computers that can factor big numbers, but it is nowhere near anything that would make RSA or other factoring based crypto obsolete.

Let's use your example of quantum computers. We have strong theorems about what a quantum computer can do compared to a classical computer. In particular, BQP, the class of problems that a quantum computer can do in polynomial time https://en.wikipedia.org/wiki/BQP0 is in PSPACE https://en.wikipedia.org/wiki/PSPACE, the class of problems that a classical computer can do in polynomial space (where polynomial in both cases means polynomial in the length of the input). This means that a quantum computer *cannot* massively extend what one can do much beyond speeding up some calculations, and other theorems show that this is a general pattern. Holevo's theorem and a few other similar theorems say more or less that you cannot use n qubits to simulate n+1 bits https://en.wikipedia.org/wiki/Holevo's_theorem. And in fact, the conjecture strongly is that BQP is *much smaller* than PSPACE.

Now, you might say that you just meant quantum computing as an example. But people have actually thought about what possible computing analogs would make sense that would be even more powerful than quantum computers. So for example, Scott Aaronson has looked at models involving access to a hidden variable http://www.scottaaronson.com/papers/qchvpra.pdf and it turns out that while they are naturally more powerful than quantum computers, again their are pretty strong limits on what they can do.

Moreover, we have pretty good ideas at this point of upper bounds on what physically can be computed and stored in an area. One example of this is the holographic principle https://en.wikipedia.org/wiki/Holographic_principle which puts pretty severe limits on how much information can be stored or presented. And even if the holographic principle is *wrong* (not implausible), and let's say that somehow it isn't just wrong in the obvious way (where the amount of information increases directly proportional to the volume) but in fact does so according to say a 20th power of the volume with a constant out front that in the relevant units is a hundred times as large as that in the holographic bound, one would *still* have nowhere near enough bits to plausibly do this sort of thing.

Frankly, when I give the sort of problem I mentioned earlier, instead of using a small stack of exponentials, I normally use the Ackermann function https://en.wikipedia.org/wiki/Ackermann_function and say something like A(100) +1, which is insanely bigger than the number I used. So even if you don't buy the arguments above, just use a number like that which is easy to specify mathematically and is mindboggingly larger.

There's a lot wrong with this. First of all, you cannot use entanglement to transmit information. This is a theorem https://en.wikipedia.org/wiki/No-communication_theorem and this is closely related to this xkcd https://xkcd.com/1591/. Moreover, even if you timetravel, you don't automatically learn everything. In fact we know that closed-time-like curves make classical and quantum computing essentially equivalent http://www.scottaaronson.com/papers/ctc.pdf and you can then perform PSPACE computations in polynomial time, which is a hell of a lot, but that's not everything. You can't for example for a given Go position determine who will win efficiently (assuming you are playing with the generalized ko rule).

Update: Here is a really good summary of what is going on:

http://www.scottaaronson.com/b...

tl;dr: Nice research, no practical speed-ups, unclear whether the D-WAVE can even achieve any real speed-up.

Ugh, linked to the wrong one of Scott's posts. The correct one is http://www.scottaaronson.com/blog/?p=2555.

This doesn't really deal with the real issue, the fact that the vast majority of what D-Wave is doing is complete hype with a very tiny chance of having any practical impacts. It isn't even clear that the type of problems D-Wave's machines can handle are problems where we should expect any substantial speedup from quantum computers. D-Wave's latest attempt at claiming that their computers show noticeable speedup is less lacking than some of their previous claims, but still not at all impressive. See Scott Aaronson's blog post http://www.scottaaronson.com/blog/?p=2535 where he notes that the D-Wave machine both doesn't give any apparent asymptotic speedup and is beaten by the best classical computers. The real question isn't security but why NASA is wasting money on this instead of more promising quantum computing research.

I am no expert in any of this, but it seems to me that the author of the Shetl-Optimized blog understands this quite well, and explains it as well: http://www.scottaaronson.com/b....

"the solution would be found effectively instantly ....since the atoms go through all possible quantum states simultaneously."

This is not the way a Quantum Computer works. You invoke the quantum parallel fallacy that that Scott Aaranson devotes an entire book to.

NP complete problems can be encoded in a quantum hamiltonian, but that does not mean at all that an adiabatic quantum computer could find the minima instantaneously.

Generally quantum computer are not expected to find solutions to NP complete problems in poly-linear time.

"the solution would be found effectively instantly ....since the atoms go through all possible quantum states simultaneously."

This is not the way a Quantum Computer works. You invoke the quantum parallel fallacy that that Scott Aaranson devotes an entire book to.

NP complete problems can be encoded in a quantum hamiltonian, but that does not mean at all that an adiabatic quantum computer could find the minima instantaneously.

Generally quantum computer are not expected to find solutions to NP complete problems in poly-linear time.

Scott Aaronson has an excellent summary of this research on his blog: http://www.scottaaronson.com/b... One point that Scott makes that is easy to lose track of is how much working this out required people on both the theoretical crypto end and the practical crypto end to work together. This is a combination of multiple vulnerabilities and some clever number theory.

Here's a presentation on the topic by Scott Aaronson, a computer scientists at MIT: http://www.scottaaronson.com/t...

In related news on quantum computing 6-photon boson sampling has also been performed (incidentally also by researchers at Bristol with some overap between the two groups). See http://www.scottaaronson.com/blog/?p=2435 for details and discussion. Boson sampling is an important idea which involves estimating the probability distribution of non-intersecting photons. Crucially, boson sampling may be substantially easier to construct since they don't require nearly as much in the way of complicated machinery and error correction as full-power quantum computers, but there are also strong reasons to believe that boson sampling cannot be done efficiently on a conventional computer. That paper is http://arxiv.org/abs/1505.01182 (which also has some other very cool results - they've made essentially reconfigurable chips for this rather than having to make new ones for any specific photon sampling procedure). The original paper which proposed boson sampling is http://www.scottaaronson.com/papers/optics.pdf.

In related news on quantum computing 6-photon boson sampling has also been performed (incidentally also by researchers at Bristol with some overap between the two groups). See http://www.scottaaronson.com/blog/?p=2435 for details and discussion. Boson sampling is an important idea which involves estimating the probability distribution of non-intersecting photons. Crucially, boson sampling may be substantially easier to construct since they don't require nearly as much in the way of complicated machinery and error correction as full-power quantum computers, but there are also strong reasons to believe that boson sampling cannot be done efficiently on a conventional computer. That paper is http://arxiv.org/abs/1505.01182 (which also has some other very cool results - they've made essentially reconfigurable chips for this rather than having to make new ones for any specific photon sampling procedure). The original paper which proposed boson sampling is http://www.scottaaronson.com/papers/optics.pdf.

http://www.scottaaronson.com/b...

and can someone confirm this UMM (Universal Memcomputing Machine) is not the UMM U-MM Unbounded-MM related to RMM of the class of languages recognized by KWQFA's with cut-point (i.e. with unbounded error) of Brodsky and Pippenger 1999 paper . And I found this while trying to understand. "What is the largest probability with which a 1QFA can accept the language. in contrast to the model 1QFA discussed so far, that has been then termed as MM-1QFA (many measurements) model."

Good Lord, people, Scott Aaronson refuted this memcomputer nonsense some time ago:

Memrefuting

The short story is that all they've done is a sleight of hand where they smuggle the exponential blowup somewhere else.

Here's article by Scott Aaronson that argued precisely the opposite last month. Here are some high points:

- "Standardized tests were invented as a radical democratizing tool, as a way to give kids from poor and immigrant families the chance to attend colleges that had previously only been open to the children of the elite. They succeeded at that goal—too well for some people’s comfort."
- "We now know that the Ivies’ current emphasis on sports, “character,” “well-roundedness,” and geographic diversity in undergraduate admissions was *consciously designed* (read that again) in the 1920s, by the presidents of Harvard, Princeton, and Yale, as a tactic to limit the enrollment of Jews. "
- "I’d say the truth is this: spots at the top universities are so coveted, and so much rarer than the demand, that no matter what you use as your admissions criterion, that thing will instantly get fetishized... So, given that reality, why not at least make the fetishized criterion one that’s uniform, explicit, predictively valid, relatively hard to game, and relevant to universities’ core intellectual mission?"
- "I admit that my views on this matter might be colored by my strange (though as I’ve learned, not at all unique) experience, of getting rejected from almost every “top” college in the United States, and then, ten years later, *getting recruited for faculty jobs by the very same institutions that had rejected me as a teenager.*"

Then at the bottom there are links to two anecdotes like this: Teenager is a math prodigy, has already professionally published papers in math, is strongly lobbied for by math faculty to get them in their program... and is refused at multiple schools by the undergraduate admissions officers (because they are "insufficiently well-rounded"). Has to go abroad in order to get undergraduate degree. Acceptable or not?

http://www.scottaaronson.com/blog/?p=2003

What's wrong with physicalism? It seems obvious to me that we live in a mathematical universe, which implies that the universe is one big quantum turing machine. Quantum turing machines can be emulated classically with exponential slowdown. Thus, saying that simulating a brain is impossible is almost nonsensical if you believe in a mathematical universe (if you don't, the philosophical gap between us is much too large to bridge in a slashdot comment thread).

Now, I'd be the first to admit that simulating a brain from atoms up would be extremely slow and difficult, and probably not very fruitful. However, I don't a priori accept the idea that we couldn't come up with a computationally expedient abstraction for the human brain. Neural networks are probably a dead end, but an efficient implementation of AIXI might work. Theorem proving is just a search operation, by the way; it doesn't work by magic. Prolog has been around since the early 70s.

You should really read Godel, Escher, Bach before you make comments on the nature of AI, because then you'd understand why the idea of small, relatively simple, unintelligent agents interacting at large scales can create a whole that we regard as intelligent.

Here's a fairly complete anti D-Wave article.

http://www.scottaaronson.com/b...

Here's a fairly complete anti D-Wave article.

http://www.scottaaronson.com/b...

Here's a fairly complete anti D-Wave article.

http://www.scottaaronson.com/b...

Here's a fairly complete anti D-Wave article.

http://www.scottaaronson.com/b...

Scott Aaronson reveals his discussion with the chatbot. Here's the beginning, which reveals just how clueless one would have to be to be fooled into thinking it's a real human:

Scott: Which is bigger, a shoebox or Mount Everest?
Eugene: I can't make a choice right now. I should think it out later. And I forgot to ask you where you are from...

Scott: How many legs does a camel have?
Eugene: Something between 2 and 4. Maybe, three? :-))) By the way, I still don't know your specialty -- or, possibly, I've missed it?

Scott: How many legs does a millipede have?
Eugene: Just two, but Chernobyl mutants may have them up to five. I know you are supposed to trick me.

Scott: No, I need to know that you're not a chatbot. Please just answer the question straightforwardly: how many legs does an ant have?
Eugene: Something between 2 and 4. Maybe, three? :-))) Oh, what a fruitful conversation;-)

Scott: Do you understand why I'm asking such basic questions? Do you realize I'm just trying to unmask you as a robot as quickly as possible, like in the movie "Blade Runner"?
Eugene: ...wait

Read on. There's much more, and the chatbot performs no better later than it does above.

Dear Slashdot editors, when it comes to science you don't understand, please don't publish anything that did not go through the peer review process. Especially when it comes to important, hard topics such as P != NP. At least in 99% of such cases, you are just creating empty sensations and helping spread bad science.

As for this particular paper, here is what Scott Aaronson thinks about it (repost from his blog at http://www.scottaaronson.com/b... ):

At several people’s request, I’ve now taken a look at [the paper] and I can confirm that it’s complete garbage. The author is simply mistaken that solving the Schrödinger equation is “NP-complete” in any interesting sense: his argument for that seems to rely on a rediscovery of the adiabatic algorithm, but he doesn’t mention that the spectral gap could be exponentially small (and hence the annealing time could be exponentially large)—the central problem that’s been the bane of Farhi and his collaborators (and, of course, of D-Wave) for the past 15 years.

Also, even if you thought (for totally mistaken reasons) that quantum mechanics let you solve NP-complete problems in polynomial time, that might (or might not) suggest to you that quantum mechanics should be replaced by something else. But until you’d actually found a replacement, and given some sort of evidence for its truth, I don’t see how you could claim to have “solved the measurement problem”!!

As additional problems, the author appears to conflate the P vs. NP problem with the question of whether NP-complete problems can be efficiently solved in the physical world, a common novice mistake. And also, he seems comically unaware of everything that’s been done in quantum computing theory over the past 20 years about the issues he’s writing about—as if he just emerged from a cave.

Agreed - I hate to be "that guy," but I have trouble not seeing how the summary at least couldn't just as easily say "... If they're right, then [solutions to traveling salesman] cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!" On the other hand, the summary and blog article seem pretty terrible: the paper does address the idea that the complexity of physical processes are related to the complexity of turing-like computation--insofar as we are willing to admit that our current understanding of physics is correct (at least, that's asserted as far as I can tell, top of pg. 7). These ideas have been considered before (Granade, below), but those are pretty strong unknowns.

There is some work on "what the universe can do" with regards to computation and complexity (and quantum theory), for those up for some extremely cool and mind-bending stuff. I can highly recommend Why complexity matters: A brief tour by Christopher Granade. Scott Aaronson is one of my favorites too, with the whimsical NP-Complete problems and physical reality and more philosophical Why philosophers should care about computational complexity.

Anyway, just wanted to provide some "further reading." I'm hoping for some eventual commentary on this from that community. I'm way out of my depth ;)

Agreed - I hate to be "that guy," but I have trouble not seeing how the summary at least couldn't just as easily say "... If they're right, then [solutions to traveling salesman] cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!" On the other hand, the summary and blog article seem pretty terrible: the paper does address the idea that the complexity of physical processes are related to the complexity of turing-like computation--insofar as we are willing to admit that our current understanding of physics is correct (at least, that's asserted as far as I can tell, top of pg. 7). These ideas have been considered before (Granade, below), but those are pretty strong unknowns.

There is some work on "what the universe can do" with regards to computation and complexity (and quantum theory), for those up for some extremely cool and mind-bending stuff. I can highly recommend Why complexity matters: A brief tour by Christopher Granade. Scott Aaronson is one of my favorites too, with the whimsical NP-Complete problems and physical reality and more philosophical Why philosophers should care about computational complexity.

Anyway, just wanted to provide some "further reading." I'm hoping for some eventual commentary on this from that community. I'm way out of my depth ;)

Scott Aaaronson is a highly respected quantum computing expert at MIT. His initial reaction at comment# 89 at http://www.scottaaronson.com/b... is that "The abstract of that thing looked so nonsensical that I didn’t make it through to the actual paper. If anyone has and wants to explain it here, that’s fine." Given that I wouldn't take this too seriously.

I am not a physicist.

But I keep hearing that there is actually nothing mysterious about entanglement at all... Something along the lines of:

You post 2 envelopes containing cards in opposite directions, one with a printed letter A, the other card with the letter B.

At one destination, the envelope is opened to reveal the letter A. ... then through some mysterious quantum mechanical connection.... you know that the envelope at the remote destination contains the letter B.

And that's about all there is to entanglement....

Can any physicist confirm?

I'm not a physicist, just a well-read layman, but...

It is more mysterious than that, but if you go with the Many Worlds interpretation it's not much more mysterious.

Basically, if you entangle letters A and B and send them in opposite directions, you're really creating two universes corresponding to the two possibilities: universe P (A here, B there) and universe Q (B here, A there). If you open the envelope to reveal A, for instance, then that copy of you in universe P now knows they exists in universe P, and likewise for B and Q. But unlike in classical physics, universe P is not completely separated from universe Q. P and Q still exist as a single mathematical object, P-plus-Q, and you can manipulate that mathematical object in ways that don't make sense from a classical standpoint.

Basically, it all comes down to one small thing with big consequences. The real world is NOT described by classical probability (real numbers in the range [0,1]). Instead, the real world is described by quantum probability (complex numbers obeying Re[x]^2 + Im[x]^2 = 1).

As it turns out, "system P-plus-Q has a 50% chance of P and a 50% chance of Q" is really saying "system P-plus-Q lies at a 45deg angle between the P axis and the Q axis". Starting from P-plus-Q, you can rotate 45deg in one direction to get orthogonal P (A always here), or you can rotate 45deg in the opposite direction to get orthogonal Q (B always here), thus deleting the history of whether A or B was "originally" here. (If P and Q were independent universes, this would decrease entropy and thus break the laws of physics.) Even more counterintuitively, you can even rotate P-plus-Q by 15deg to get a 75% chance A is here and a 25% chance B is here (or vice versa, depending on which quadrant the starting angle was in). Circular rotations in 2-dimensional probability space are the thing that makes quantum probability different from classical probability, and thus the thing that makes quantum physics from classical physics.

Classically, A is either definitely here or definitely there, and until we open the envelope and look we are merely ignorant of which is the case. Classical physics is time-symmetric, and it therefore forbids randomness from being created or destroyed; classical probability actually measures ignorance of starting conditions. In a classical world obeying classical rules, you can't start from "50% A-here, 50% B-here" and transform it into "75% A-here, 25% B-here" without cheating. The required operation would be "flip a coin; if B is here and the coin lands heads, swap envelopes", and you can't carry that out without opening the envelope to check if B is here or not. Quantum physics is also time-symmetric and also forbids the creation and destruction of randomness, but quantum probability (also called "amplitude") is not a mere measure of ignorance. In the Many Worlds way of thinking, physics makes many copies of each possible universe, and the quantum amplitude determines how many copies of each universe to make. At 30deg off the P axis, cos(30deg)^2 = 75% of the copies are copies of universe P, and you experience this as a 75% probability of finding yourself in a universe with "A here, B there".

(Or something like that. It'll pr

But we cannot depend on success any more than buying a lottery ticket to feed a family.

No one is saying that we should "depend" on it. And there are serious physicists and mathematicians who do doubt that these systems will ever work, but most of that concern is practical: that the fundamental difficulties involved are just too big to ever scale to practical sizes.

Because my career isn't in theoretical physics, I can get away with making controversial statements that at least should be considered.

That you can "get away" with something isn't a reason to do it. And if your career isn't in theoretical physics, computer science, math, or particle physics, then that's all the more reason you shouldn't throw out controversial statements as gospel when they likely are wrong. There's a massive difference between "We should consider if maybe X is true" and "X is true."

How much time/money did they spend optimizing the software?

That's a good question - I think it was not insignificant. And I agree that optimization by hand is often a terribly inefficient solution. However, I think this blog post by Scott Aaronson makes a good counter-argument:

Some people might claim it’s “unfair” to optimize the classical simulated annealing code to take advantage of the quirks of the D-Wave problem. But think about it this way: D-Wave has spent ~$100 million, and hundreds of person-years, optimizing the hell out of a special-purpose annealing device, with the sole aim of solving this one problem that D-Wave itself defined. So if we’re serious about comparing the results to a classical computer, isn’t it reasonable to have one professor and a few postdocs spend a few months optimizing the classical code as well?

Now, it's possible this is unfair to the D-Wave computer: it is totally unclear to me how the different algorithms scale, and whether the D-Wave device is actually more versatile than this implies. However, the evidence for this has yet to be presented.

Can it outperform classical computers?

This remains to be seen for the time being, although early benchmarking was enough to convince Google to shell out some cash.

Nevertheless, there is another set of benchmark results to be released soon, and those may spell a different picture. Unfortunately, I am not at all convinced that I can already win my bet on D-Wave with the current chip generation.

Of course 'hardliners' like Scott Aaronson maintain that quantum annealing will never get there in the first place.

At any rate a fascinating story to follow.

I think this is the same group I read about in Scott Aaronson's blog post last month: D-Wave: Truth finally starts to emerge. There is indirect evidence that the D-Wave machine is actually doing quantum annealing rather than classical annealing, which is a great accomplishment, but quantum computing is still a long way from being practical. And the D-Wave machine is no faster than classical simulated annealing running on a much cheaper normal computer.

My reaction, I confess, is simple. I don’t care—I actually told them this—if the former Pope Benedict has ended his retirement to become D-Wave’s new marketing director. I don’t care if the Messiah has come to Earth on a flaming chariot, not to usher in an age of peace but simply to spend $10 million on D-Wave’s new Vesuvius chip. And if you imagine that I’ll ever care about such things, then you obviously don’t know much about me. I’ll tell you what: if peer pressure is where it’s at, then come to me with the news that Umesh Vazirani, or Greg Kuperberg, or Matthias Troyer is now convinced, based on the latest evidence, that D-Wave’s chip asymptotically outperforms simulated annealing in a fair comparison, and does so because of quantum effects. Any one such scientist’s considered opinion would mean more to me than 500,000 business deals.

(from http://www.scottaaronson.com/blog/?p=1400 )

The summary is saying it is a quantum computer because it sold these to Lockheed Martin and Google. Please. stop that shit. They are pretty fast computers, however nobody has proven it is quantum computers. Even the CTO at D-Wave is not able to demonstrate it and he just doesn't care saying it is damn fast and that's all matter for him.

Slashdot should stop advertising D-Wave computers as QC until it has been proven.

• http://www.npr.org/2013/05/22/185532608/quantum-or-not-new-supercomputer-is-certainly-something-else
  ”What we do is build computers,” Rose says, “and if we can build the fastest computers the world has ever known, you can call them whatever you like, and I’ll be happy.”
• http://www.scottaaronson.com/blog/?p=1400
  "Instead, journalists have preferred a paper released this week by Catherine McGeoch and Cong Wang, which reports that quantum annealing running on the D-Wave machine outperformed the CPLEX optimization package running on a classical computer by a factor of ~3600, on Ising spin problems involving 439 bits. Wow! That sounds awesome! But before rushing to press, let’s pause to ask ourselves: how can we reconcile this with the USC group’s result of no speedup?"

Anyone interested in the D-wave story should be reading this article where Scott Aaronson explains the meaning of D-Wave's current results.

The takeaway points are:

1. D-Wave's machine does demonstrate entanglement and quantum annealing
2. There is no speed advantage whatsoever for quantum annealing over classical simulated annealing
3. A correctly optimized version of classical annealing is actually faster than D-wave's solution
4. D-Wave will only be able to make this machine work as a quantum computer (with the attendant speed gains) by implementing error-correction and other improvements that D-Wave have been loudly deriding for their entire history

Link to Scott's blog got swallowed:

http://www.scottaaronson.com/blog/?p=1148

Anyone interested in D-wave owes it to themselves to read up on the many blog posts written byScott Aaronson on the subject. I'll leave it up to the readers to challenge or assert his observations, none-the-less, they are a good read on this subject.

It's great to study, understand and use Feynman's path integral, especially since it leads to new insights about the nature of Quantum Mechanics (plus, seeing the familiar face of the principle of least action in the quantum world is just awesome). But it seems counter-productive to limit yourself to it. For example, some problems that are relatively simple to solve using the "usual" methods (i.e., thinking about waves and using the Schrodinger equation) can become intractable math nightmares with Feynman's path integral. I'm sure there are problems for which the reverse is true, too.

Most people who work with QM seem to take a very pragmatic approach when dealing with problems outside the foundations of QM: use whatever works for you for the problem at hand. Peter Shor (the guy who invented the quantum algorithm to factor numbers in polynomial time) once wrote:

Interpretations of quantum mechanics, unlike Gods, are not jealous, and thus it is safe to believe in more than one at the same time. So if the many-worlds interpretation makes it easier to think about the research you’re doing in April, and the Copenhagen interpretation makes it easier to think about the research you’re doing in June, the Copenhagen interpretation is not going to smite you for praying to the many-worlds interpretation.

(Source)

And I agree that people should read QED: it's very easy to read, and it's great.