Next Big Future on quantum computation

[Robert J. Hansen]

Some people have been all abuzz over this article lately:

http://nextbigfuture.com/2015/07/currently-quantum-computers-might-be.html

Rather than go through it point by point I'm just going to talk about
the author's closing paragraph, which one would expect to have been
pretty closely checked prior to publication.

	"Getting 1.4 million times speedup over a single CPU
	 is possible now with a Google data center. In ten to
	 15 years it could be inside one rack of future
	 conventional computers. If that rack of computers
	 could not solve your NP-hard problem you could use
	 it for many other revenue generating and useful
	 applications."

The first "wait, what did you just say?" was his assertion that it's
possible to get a 1.4 millionfold speedup over a single CPU with the
money it would take to build a Google data center.  If it was possible,
don't you think Google, Microsoft, Apple, and Facebook would *already be
building them*?  Entrepreneurs who can afford to do this are
overwhelmingly choosing not to do this.  When the people who should be
doing it aren't, think hard and think twice.

His next claim is just ... it makes no sense to me.  "If that rack of
[quantum] computers could not solve your NP-hard problem..."

Point blank: quantum computers cannot solve NP-Hard problems.  Period,
end of sentence.  NP-Hard is where the ridiculously difficult problems
live.  If you had a computer that could break NP-Hard problems, you
could literally crack one-time pads, predict the future, solve the
Halting Problem, reverse entropy, and essentially become a god.

Okay, so maybe the author had a goof.  Maybe he meant NP-Complete.
That's better, right?  If that rack of computers couldn't solve your
NP-Complete problem you could use it for many other revenue generating
and useful applications.

Except that, by definition, if you're unable to solve *one* NP-Complete
problem, you're unable to solve *any* NP-Complete problem.  It's an
all-or-nothing deal.  You can either solve everything in NP-Complete, or
nothing.  No in-betweens.  So reading his sentence as "couldn't solve
your NP-Complete problem" doesn't improve it.  Can't solve one, can't
solve any.

Let's scale it back some more.  Maybe he meant "If that rack of
computers couldn't solve your NP problem you could...".  Okay.  Now
we're getting kind of close to reality, except that NP is a *big* class
of algorithms -- this is like asking someone to find your lost dog and
saying you're pretty sure you left him in Australia.  It's too vague to
really be meaningful.  NP is like that, but its Outback is bigger.

Take it back a step further: "If that rack of computers could not solve
your BQP problem you could..."  BQP is the set of all algorithms that
can be efficiently solved with a quantum computer.  If that rack of
computers can't solve a BQP problem, then maybe you should consider
whether you've been defrauded.

So that sentence there --

	* Can't be true for NP-Hard: you're not a god.
	* Is nonsense for NP-Complete: if you can't solve one, you
	  can't solve any.
	* Isn't particularly well-defined for NP.
	* Is trivially true for BQP.


... I'm a thesis shy of a Ph.D. in computer science and I've got
absolutely no idea what the author meant by what he said in that
paragraph.  None.  Zero.  It sounds nice but I'm at a loss to explain
what it means.

I'm not an expert on rocketry, so I won't comment on those parts of the
essay.  But the computer science parts of the essay are all like this:
they're superficially glib but they're just plain *bad*.

Also, check out the author's bio/resume:

	http://lifeboat.com/ex/bios.brian.l.wang