Slashdot Mirror

This has the same central problem as before. D-Wave's computers haven't demonstrated that their commercial bits are entangled. There's no way to really distinguish what they are doing from essentially classical simulated annealing. And the set of problems which their machines can supposedly works on is an NP-hard problem minimization problem involving Ising spin where it isn't even clear that from a complexity standpoint that the the problem can be more quickly solved in general by a quantum system. (Essentially we don't know the relationship between BQP, the set of problems reliably solvable on a quantum computer in polynomial time http://en.wikipedia.org/wiki/BQP and NP http://en.wikipedia.org/wiki/NP_(complexity). Recommended reading that is skeptical of D-Wave's claims is much of what Scott Aaronson has wrote about them. See for example http://www.scottaaronson.com/blog/?p=639, http://www.scottaaronson.com/blog/?p=198 although interestingly after he visited D-Wave's labs in person his views changed slightly and became slightly more sympathetic to them http://www.scottaaronson.com/blog/?p=954.

This has the same central problem as before. D-Wave's computers haven't demonstrated that their commercial bits are entangled. There's no way to really distinguish what they are doing from essentially classical simulated annealing. And the set of problems which their machines can supposedly works on is an NP-hard problem minimization problem involving Ising spin where it isn't even clear that from a complexity standpoint that the the problem can be more quickly solved in general by a quantum system. (Essentially we don't know the relationship between BQP, the set of problems reliably solvable on a quantum computer in polynomial time http://en.wikipedia.org/wiki/BQP and NP http://en.wikipedia.org/wiki/NP_(complexity). Recommended reading that is skeptical of D-Wave's claims is much of what Scott Aaronson has wrote about them. See for example http://www.scottaaronson.com/blog/?p=639, http://www.scottaaronson.com/blog/?p=198 although interestingly after he visited D-Wave's labs in person his views changed slightly and became slightly more sympathetic to them http://www.scottaaronson.com/blog/?p=954.

This has the same central problem as before. D-Wave's computers haven't demonstrated that their commercial bits are entangled. There's no way to really distinguish what they are doing from essentially classical simulated annealing. And the set of problems which their machines can supposedly works on is an NP-hard problem minimization problem involving Ising spin where it isn't even clear that from a complexity standpoint that the the problem can be more quickly solved in general by a quantum system. (Essentially we don't know the relationship between BQP, the set of problems reliably solvable on a quantum computer in polynomial time http://en.wikipedia.org/wiki/BQP and NP http://en.wikipedia.org/wiki/NP_(complexity). Recommended reading that is skeptical of D-Wave's claims is much of what Scott Aaronson has wrote about them. See for example http://www.scottaaronson.com/blog/?p=639, http://www.scottaaronson.com/blog/?p=198 although interestingly after he visited D-Wave's labs in person his views changed slightly and became slightly more sympathetic to them http://www.scottaaronson.com/blog/?p=954.

Sure. There are definite limits of that sort that aren't implausible. But at the same time, we know that if present trends continue our computational substrates will hit the end of the line in a few decades. Fundamental limits mean that if our understanding of the laws of physics are correct we hit the limits for classical computational systems in about fifty years. It is hard to say when such limits get hit for quantum stuff (and one needs to be careful about what one means here). At that some point, one will eventually run into a situation where just making things bigger will be the most viable option. The only known exception to this is if one can make wormholes and take advantage of closed-time like curves. See http://www.scottaaronson.com/papers/ctc.pdf. Even then, there are eventual limits, it just isn't clear they are limits any civilization would ever care about. So although people in the 1950s were wrong, they probably weren't wrong about the very long run. Even today, we have supercomputers, mainframes and large clusters that aren't that far off from what were envisioned in the 1950s. If aliens are out there and this is wrong then this is almost as interesting a claim as the claim that they are out there. In some respects it is a bigger claim because it means we are wrong about very fundamental physics, whereas finding life is in complete consistency with physics as we know it.

I agree that at this point we can't detect any smaller projects and that at this point "smaller" means a bit larger than Earth (unless the project does something ridiculous that dumps out a lot of radiation, like say a controlled black hole that is constantly fed matter). And such projects are much more likely. Even projects the size of a small moon are probably hundreds or thousands of years ahead of us and would be utterly invisible to us by any technology we can conceive.

It isn't at all clear that D-Waves system is using any sort of quantum entanglement at all. D-Wave has had a long history of massive hype. See e.g. http://www.scottaaronson.com/blog/?p=431. It isn't at all clear that D-Waves commercial system can do any of the things that we expect a quantum computer to do like say factor integers using Shor's algorithm http://en.wikipedia.org/wiki/Shor's_algorithm. It seems that D-Wave has made a fast computer but there's very little evidence that it actually is using quantum processes any more than a normal computer. You could call your laptop a quantum computer because quantum mechanics is used in determining how the transistors function and you might be close to what D-Wave is claiming. The key is whether there are entangled qubits that we can get info from, and D-Wave has shown little indication of that. They have had a handful of research papers that sort of point in that direction but it is very hard to separate the hype from what they've actually done.

The real question is "Does the D-Wave 'quantum computer' do anything useful at all?"

See Scott Aaronson's opinions on the topic: http://blogs.forbes.com/alexknapp/2011/05/24/q-and-a-with-prof-scott-aaronson-on-d-waves-quantum-computer/

Aaronson is a brilliant quantum algorithm complexity professor for MIT. You can read his blog at http://www.scottaaronson.com/

It isn't my area specifically so I may not be the best person to give advice, but Scott Aaronson's blog - http://www.scottaaronson.com/blog/ seems to be a good way of keeping up on a lot of these issues.

P vs. NP for dummies

Here is a way it could possibly not apply.

Your argument seems to be this (please correct me if I'm misrepresenting it):

Take the formal system of the "theory of everything", call it TOE. By Godel's theorem, there exists a certain arithmetic statement (G) that is independent of TOE. Because the universe is Turing complete, it's possible to physically build a Turing machine (M) whose output (or, even better, whether it halts or not) depends on the truth value of G. Since G is undecidable in TOE, the "theory of everything" can't predict what would physically happen if we actually build M in the physical world. So, this means that the "theory of everything" can't actually predict everything.

One possible objection is the following:

When you follow Godel's proof, you notice that the arithmetic statement that the proof constructs involves huge numbers, and that the more axioms you put on your system, the larger the numbers involved must be (if you don't remember just how huge the numbers are, go back and check it: it's mind boggling, even for the relatively simple formal system used by Godel).

That in itself would not be a problem, since we're only talking about the theoretical possibility of the existence of the "theory of everything". But, it turns out that it's possible (and even probable) that our universe is not actually Turing complete because there's a limit to how much computation is possible even in principle. That is, it's possible that the formal system of the "theory of everything" is complex enough that in order to build the Turing machine that would be unpredictable, you'd either have put so much in too little space that it would become a black hole, or you'd have to spread it out so much (in order to prevent the black hole) that the universe expansion would make one end of the Turing machine inaccessible to the other end, and so the machine wouldn't be able to compute anymore.

In case that last point is not too clear, you can find a much better explanation in this lecture (search for "So what does any of this have to do with computation?").

I'm not saying that this is the case, but it's certainly a possibility that has not been ruled out (and maybe it's even true).

Note this is from a respected MIT prof:

If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of PNP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.

I’m dead serious—and I can afford it about as well as you’d think I can.

My hunch is he's pretty sure it's broken.

This question has been considered by quite a few different people; search google for P vs NP independent ("independent" meaning independent from the usual accepted axioms for mathematics, i.e., can't be proven using the currently accepted axioms).

There's a nice survey paper about this question that's very readable if you're willing to invest some time: Is P Versus NP Formally Independent?.

The pdf of the paper (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf) is produced using pdfTeX (see File -> Properties) in Acrobat Reader.
This of course means it was prepared using TeX, and nicely type-set too !

Scott Aaronson listed ten signs a mathematical breakthrough is wrong.

The very first sign is whether the authors used the standard technology for scientific publication (TeX/LaTeX). This paper appears to be written in MS freakin' Word. I'm not saying it is impossible for a genius mathematician to be a publication newbie, but consider what is more likely:

1. Someone with no experience in scientific publication independently discovered a proof sought after for decades, which some have conjectured to be not even provable.
2. Somewhere in those hundred pages is an incorrect generalization, a hidden assumption, circular reasoning or one of dozens of other pitfalls a budding computer scientist or mathematician falls into while attempting a complex proof.

Scott Aaronson unfortunately hasn't found the time yet to examine the paper closely, but he does bet 200k against its correctness.

The pdf of the paper (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf) is produced using pdfTeX (see File -> Properties) in Acrobat Reader.
This of course means it was prepared using TeX, and nicely type-set too !

Scott Aaronson listed ten signs a mathematical breakthrough is wrong.

The very first sign is whether the authors used the standard technology for scientific publication (TeX/LaTeX). This paper appears to be written in MS freakin' Word. I'm not saying it is impossible for a genius mathematician to be a publication newbie, but consider what is more likely:

1. Someone with no experience in scientific publication independently discovered a proof sought after for decades, which some have conjectured to be not even provable.
2. Somewhere in those hundred pages is an incorrect generalization, a hidden assumption, circular reasoning or one of dozens of other pitfalls a budding computer scientist or mathematician falls into while attempting a complex proof.

Scott Aaronson unfortunately hasn't found the time yet to examine the paper closely, but he does bet 200k against its correctness.

Scott Aaronson listed ten signs a mathematical breakthrough is wrong.

The very first sign is whether the authors used the standard technology for scientific publication (TeX/LaTeX). This paper appears to be written in MS freakin' Word. I'm not saying it is impossible for a genius mathematician to be a publication newbie, but consider what is more likely:

1. Someone with no experience in scientific publication independently discovered a proof sought after for decades, which some have conjectured to be not even provable.
2. Somewhere in those hundred pages is an incorrect generalization, a hidden assumption, circular reasoning or one of dozens of other pitfalls a budding computer scientist or mathematician falls into while attempting a complex proof.

Scott Aaronson unfortunately hasn't found the time yet to examine the paper closely, but he does bet 200k against its correctness.

Scott Aaronson listed ten signs a mathematical breakthrough is wrong.

The very first sign is whether the authors used the standard technology for scientific publication (TeX/LaTeX). This paper appears to be written in MS freakin' Word. I'm not saying it is impossible for a genius mathematician to be a publication newbie, but consider what is more likely:

1. Someone with no experience in scientific publication independently discovered a proof sought after for decades, which some have conjectured to be not even provable.
2. Somewhere in those hundred pages is an incorrect generalization, a hidden assumption, circular reasoning or one of dozens of other pitfalls a budding computer scientist or mathematician falls into while attempting a complex proof.

Scott Aaronson unfortunately hasn't found the time yet to examine the paper closely, but he does bet 200k against its correctness.

"I’m dead serious—and I can afford it about as well as you’d think I can." See his blog.

... because quantum computers are NOT known to solve any problem that "requires exponential time" in polynomial time.

This is one of the most frequent misconceptions about quantum computing. Take a look at Scott Aaronson's blog:

http://www.scottaaronson.com/blog/

It states "Quantum computers are not known to be able to solve NP-complete problems in polynomial time" for a reason ...

Quantum computers can factorize numbers in polynomial time. However determining prime factors is NOT known to be NP-complete, even though it is commonly assumed to be "hard".

Well, if you want to split hairs, at least split them to the end...

Eventually, of course, the universe will run out of mass for you to make tape out of, but the machine is still a proper Turing machine.

How is this "still a proper Turing machine"? There are programs that would work on a theoretical Turing machine (with arbitrary amount of tape), but would run out of memory in your scheme.

The OP point stands: we will never actually be able to build a real Turing machine[1]. Still, computers are very good approximations (for programs that require up to a certain amount of memory).

[1] Assuming the universe is actually expanding and that the theory of relativity is right (a good discussion can be found here: http://www.scottaaronson.com/democritus/lec20.html)

Sorry to reply to my own comment but I should add a link. It covers, in non technical language, the some of the objections to D-Waves claims, what kind of dubious science their people do and what is bull**** that the marketing people flat out invent. It is only one person's perspective but the guy is very, very capable of evaluating statements made by D-Wave.

I'd respectfully disagree and say it's pretty bad from the computer science side of things. There's plenty of experimental evidence that indirectly suggests FTL information propagation is impossible, if you consider that allowing it enables the efficient computation of NP-complete problems, for which I'll cite Prof. Aaronson at Shtetl-Optimized.

Yes, see NP-complete Problems and Physical Reality, by Scott Aaronson.

As far as I know, the "only" crypto applications of QC that would give an exponential speed-up are for factoring (Shor's algorithm). I realize that that's essentially all currently used asymmetric (public/private key) encryption, but afaik elliptical encryption, which is also usable for asymmetric encryption, isn't impacted.

Of course, no one knows if elliptical encryption will fall to some quantum algorithm, and you can always get a O^0.5 speed up using Grover's algorithm, but O^0.5 just requires double the key length rather than making encryption impractical.

Scott Aaronson, a quantum algorithm complexity researcher at MIT, believes that quantum computing does not in general give an exponential speed-up to algorithms, and I believe him...

"The interesting thing about such a value is that it could be used to determine the correct value of any problem simply by casting it to the appropriate data type."

This is incorrect. Determining the superposition's state won't give you the correct answer. It will give you a random answer from all of its possible states -- weighted by the chance of that being the right answer. This makes quantum computing much trickier.

http://scottaaronson.com/blog/?p=208 is a great article if you want to understand how some Quantum algorithms we know of will work using this "probable-answer" property.

But you don't have that ability. Quantum computer != massively parallel computer. I went looking myself and found this page which explains why it doesn't work like that, and how it actually works.

It's not a 'new toy' for computer science. Computer science has pretty much nothing to do with it. Mostly, it's a toy, or rather, academic persuit for theoretical physicists.

No, it's of real interest to theoretical computer science. Quantum computing defines a new class of algorithmic complexity: there are, for instance, sub-exponential quantum algorithms for problems which have only exponential-time classical solutions. There is a whole subindustry of algorithmic complexity theory devoted to exploring the differences between algorithms that can be executed on quantum computers and those which are executed on classical computers. Scott Aaronson's lecture notes are a good introduction to this subject.

D-Wave has provided neither proof nor convincing evidence that they have, or are capable of building a quantum computer. There are several theoretical limitations that experts remain skeptical have been overcome. Their demonstrations have been suspicious and not open for peer review. In sum, I will believe it when I see it.

See some skepticism here:
http://scottaaronson.com/blog/?p=306
http://scottaaronson.com/blog/?p=291
http://scottaaronson.com/blog/?s=d-wave

D-Wave has provided neither proof nor convincing evidence that they have, or are capable of building a quantum computer. There are several theoretical limitations that experts remain skeptical have been overcome. Their demonstrations have been suspicious and not open for peer review. In sum, I will believe it when I see it.

See some skepticism here:
http://scottaaronson.com/blog/?p=306
http://scottaaronson.com/blog/?p=291
http://scottaaronson.com/blog/?s=d-wave

D-Wave has provided neither proof nor convincing evidence that they have, or are capable of building a quantum computer. There are several theoretical limitations that experts remain skeptical have been overcome. Their demonstrations have been suspicious and not open for peer review. In sum, I will believe it when I see it.

See some skepticism here:
http://scottaaronson.com/blog/?p=306
http://scottaaronson.com/blog/?p=291
http://scottaaronson.com/blog/?s=d-wave

The proof was a legitimate effort by a non-crackpot, but the ideas in it were well known to specialists in the field and were generally understood to not be powerful enough to crack the problem. So the errors were found fairly quickly. Scott Aaronson's post Ten Signs that a claimed mathematical breakthrough is wrong item #10 may be helpful in understanding what happened.

http://www.scottaaronson.com/blog/?p=208 'Shor, I'll do it' laymans guide to a useful quantum algorithm. http://en.wikipedia.org/wiki/Quantum_dot http://en.wikipedia.org/wiki/Quantum_wire http://en.wikipedia.org/wiki/Quantum_well

Do you have an example of asymmetric encryption that is secure against quantum algorithm? PK is broken by Schor's algorithm (if you have a big enough quantum computer), and per Scott Aaronson (an algorithmic complexity professor at MIT), elliptical encryption is also demonstrated to be vulnerable. He appeared to imply in that same discussion that all asymmetric algorithms were vulnerable...

Parent post is absolutely correct; grandparent is absolutely wrong.

Read Scott Aaronson's blog to get a clue about quantum computing.

Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem ;-).

Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).

Look up Grover's algorithm and Schor's algorithm on Wikipedia, and you'll see that the GP is speaking beyond his knowledge.

I should say that I also made the mistake of thinking factoring was NP complete, and made a fool of myself on Scott's blog before the many, many people more knowledgeable than I about QC on that forum corrected me.

Actually, quantum computers don't work quite like that. The result of a quantum computer computation is the superposition of all the possible results. At the end, you have to collapse the wave function, and you wind up with a specific result, randomly from all the possible results. To factor large integers, you have to rotate the cubits 90 degrees after doing the computation, and somehow that's similar to doing an FFT. If you run the computation many times, statistically you get results bunched into clumps, and the distance between clumps tells you what the factor is.

There's no evidence to date that a quantum computer can be used to solve NP complete problems, and most people seem to think factoring is in a class in between P and NP-complete.

Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:

http://www.scottaaronson.com/writings/limitsqc-draft.pdf

Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/

(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)

Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:

http://www.scottaaronson.com/writings/limitsqc-draft.pdf

Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/

(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)

Hi fellow slashdotters!!

You might be interested in knowing what the author of TFA thinks about his article and the discussion here

"Explanation for the man in the street" by Scott Aaronson,
http://scottaaronson.com/blog/?p=208

"Good question. The period-finding algorithm doesn't work for a function that's 0 almost everywhere, and 1 only in a few exponentially-far-apart places. For the quantum Fourier transform to tell you anything useful, you need a function whose periodic structure is "globally detectable." There's a paper by Hales and Hallgren from years ago where they made that intuition more precise."

"approved" by Peter Shor.
http://scottaaronson.com/blog/?p=208#comment-9958

(Shor wrote "Great article, Scott! That's the best job of explaining quantum computing to the man on the street that I've seen."). Scott Aaronson suggests the following 12 sites as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
http://en.wikipedia.org/wiki/Shor's_algorithm

"Explanation for the man in the street" by Scott Aaronson,
http://scottaaronson.com/blog/?p=208

"Good question. The period-finding algorithm doesn't work for a function that's 0 almost everywhere, and 1 only in a few exponentially-far-apart places. For the quantum Fourier transform to tell you anything useful, you need a function whose periodic structure is "globally detectable." There's a paper by Hales and Hallgren from years ago where they made that intuition more precise."

"approved" by Peter Shor.
http://scottaaronson.com/blog/?p=208#comment-9958

(Shor wrote "Great article, Scott! That's the best job of explaining quantum computing to the man on the street that I've seen."). Scott Aaronson suggests the following 12 sites as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
http://en.wikipedia.org/wiki/Shor's_algorithm

Shortest path isn't NP-complete; Dijkstra's algorithm can solve shortest path in O(V^2) where V is the number of vertices in the graph.

Maybe you're thinking of the often repeated claim that one can find a Steiner tree (the determination of which is NP-complete) using soap and a physical setup. But that, too, is false.

Kieu tried to find a way to make quantum trickery (in ordinary quantum computers) calculate NP-complete problems (and a lot more) in polynomial time, but his hypercomputation algorithm was later disproved. So just as P = NP in classical computing seems to be very hard to prove or disprove in the general case, so appears its quantum mechanical analog to be, as well. (But as the paper states, some computers using exotic physics could be able to solve NP-complete problems easily; for instance, a time-traveling computer could solve PSPACE-complete problems without much difficulty, and if loop quantum gravity is true, a computer making use of it might be able to solve NP-complete problems as well.)

Scott Aaronson has a wonderful explanation of how it works (including why it's so much faster with quantum) at http://scottaaronson.com/blog/?p=208.

For me, this looks like the best shot I have at understanding it.

http://www.scottaaronson.com/democritus/lec9.html

"Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers."

I have an ingenious idea for a company. My company will be in the business of selling computer games. But, unlike other computer game companies, mine will never have to hire a single programmer, game designer, or graphic artist. Instead I'll simply find people who know how to make games, and ask them to donate their games to me. Naturally, anyone generous enough to donate a game will immediately relinquish all further rights to it. From then on, I alone will be the copyright-holder, distributor, and collector of royalties. This is not to say, however, that I'll provide no "value-added." My company will be the one that packages the games in 25-cent cardboard boxes, then resells the boxes for up to $300 apiece.

But why would developers donate their games to me? Because they'll need my seal of approval. I'll convince developers that, if a game isn't distributed by my company, then the game doesn't "count" -- indeed, barely even exists -- and all their labor on it has been in vain.

Admittedly, for the scheme to work, my seal of approval will have to mean something. So before putting it on a game, I'll first send the game out to a team of experts who will test it, debug it, and recommend changes. But will I pay the experts for that service? Not at all: as the final cherry atop my chutzpah sundae, I'll tell the experts that it's their professional duty to evaluate, test, and debug my games for free!

On reflection, perhaps no game developer would be gullible enough to fall for my scheme. I need a community that has a higher tolerance for the ridiculous -- a community that, even after my operation is unmasked, will study it and hold meetings, but not "rush to judgment" by dissociating itself from me. But who on Earth could possibly be so paralyzed by indecision, so averse to change, so immune to common sense?

I've got it: academics!

It's good to hear that there are at least some journalists with an interest and an aptitude for science. I think the entire quantum computing academic community has been a bit bummed out about the quality of media coverage lately. Scott Aaronson's blog has a number of posts discussing this issue, including a letter that he wrote to The Economist about its particularly bad D-Wave coverage. There is also some good news--Scott got asked by Scientific American to write a summary of Shor's algorithm--but mostly reading press coverage of our field is just maddening.

Science is hard work -- is it really surprising that interpreting scientific research, and translating results into layman's terms, is in some ways almost as hard?

No, it's certainly not surprising. I get a reminder of how hard it is to explain this stuff every time I try to tell someone what I do and their eyes glaze over. I don't claim to be good at explaining it, whereas science journalists seem to be quite good at making stuff entertaining and bringing it down to a layman's level. The problem is the completely uncritical coverage of miraculous claims, and the glaring technical errors that horribly distort the science. Is it common for journalists/editors to run a draft of their article past an actual scientist in the field? If not, why doesn't this happen? Pride? Deadlines? Journalism guidelines?

After being burned on a previous interview, I'd now be very reluctant to give an interview about my work without the reporter agreeing to run a draft past me for me to check for technical accuracy. Do science journalists honor that kind of request? If not, can you give me a journalist's perspective on what I can do to ensure the resulting article is accurate? I ask because I've got a paper coming out soon that might attract a bit of media interest.

Disclaimer: IAAPRQC (I Am A Physicist Researching Quantum Computing).

I have no doubt their chip actually exists. That's not what people are skeptical of. There are more fundamental questions, a few of which I'll list below, along with my guesses as to the answers:

1) Does their chip demonstrate global coherence?
Maybe.

2) If yes to (1), can they maintain that when scaling up to larger numbers of qubits?
Almost certainly not with anything like their present design, unless they move to implement quantum error correction and the massive amounts of overhead that entails.

3) If no to either (1) or (2), can they implement a practical algorithm that gives at least a sqrt(N) speed-up over classical computers without global coherence?
Possible, but would be surprising if true. This is probably the main thing the academic community is skeptical about--we want to see some peer-reviewed research from D-Wave on this.

4) Why is all the press coverage so horribly wrong and misinformative?
Because it's more fun to make jokes and stupid statements about quantum mechanics than it is to actually write a clear and well-researched article. Also, talking to an actual physicist is far too scary for your typical J-school grad.

See this post on Scott Aaronson's blog for a much more informative and detailed analysis of D-Wave's claims.

Is there really any reason why government-funded research shouldn't be made available to the masses? After all, wasn't it the masses who paid for the research?

Yes, there is a reason -- but not a good one. Very big publishing houses such as Elsevier have a huge financial interest in maintaining the status quo, whereby government-funded researchers donate their work for free to the publishers, who then make a large profit by printing and selling it. It is typical (though not universal) for the publishers also to take the copyright of the papers they publish. To add insult to injury, it's not ususual for the publishers to CHARGE THE AUTHORS for the privilege of donating their work -- usually a fixed amount per page above some predefined page limit.

The whole academic publishing game is a racket of the most egregious kind, and the Open Access movement is a very badly needed antidote to the way things are. Scott Aaronson has written a scathing analogy to the current situation which I strongly encourage everyone to read (not least because it's funny).

Quantum computing researcher Scott Aaronson wrote some good anti-hype pieces about the D-Wave PR here and here, focusing on their incorrect marketing claims to be able to solve NP-complete problems in polynomial time. The first link also has an update with comments from Lawrence Ip of Google, who clarifies what the D-Wave people are really claiming.

Quantum computing researcher Scott Aaronson wrote some good anti-hype pieces about the D-Wave PR here and here, focusing on their incorrect marketing claims to be able to solve NP-complete problems in polynomial time. The first link also has an update with comments from Lawrence Ip of Google, who clarifies what the D-Wave people are really claiming.

Disclaimer: I am a physicist who works on quantum computing and also has a computer science background

Nobody is going to use Travelling Salesman in the real world to plan journeys. You can already quickly run an algorithm which will get you a journey plan that's maybe 99% as good as the optimum.

Actually, I think there is a theorem that finding an algorithm that efficiently produces highly-accurate approximate solutions to arbitrary problems in NP-hard is about as hard solving NP-complete problems exactly.

All this aside, it's worth noting that D-Wave is only claiming to provide a square-root speed-up for NP-complete problems, and there is some doubt as to whether they can even deliver that, as they scale up to larger numbers of quantum computers. While it's technically possible that P=NP, most people believe P!=NP, and it seems almost as likely that BQP != NP (BQP is the class of problems efficiently solvable with a quantum computer).

For an excellent discussion of what D-Wave has done and just how skeptical you should be, visit Scott Aaronson's blog. (No, I am not Scott Aaronson, but I do know him and can vouch for him being an extremely smart guy. I am also not the Quantum Pontiff, aka Dave Bacon.)