Under the Hood of Quantum Computing

nanotrends writes "Gordie Rose, the CTO of Dwave Systems, the venture funded company that plans to offer paid use of a superconducting quantum computer starting in 2007, reveals secrets of his quantum computer construction. It is based on nobium superconducting 'circuits of atoms' and is not RSFQ. (Rapid Single Flux quantum)."

Advantages?

[Zouden]

I read the article, but it didn't make it very clear - what will be the advantages of paid use of their quantum computer? Unless it's going to be faster than other supercomputers, I can't see the point. Is there some other advantage I'm not aware of?

I'd be very suprised if their quantum computer will be faster than conventional computers by next year. 20 years away, maybe.

Re:Advantages?

[QuantumG]

I don't think anyone can assess the capabilities of his systems from that article. I also don't think that was unintentional.

Re:Advantages?

[RKBA]

"what will be the advantages of paid use of their quantum computer?"

I'm sure the NSA and other government agencies have a passing interest in code breaking, which among other things means being able to factor huge numbers quickly [rsasecurity.com]. A quantum computer would (if it contained sufficient logic cells) be able to try all possible factors of a number at the same time, and would thus be able to factor any number almost instantaneously. It would mean the death of most common types of encryption that depend upon the difficulty of factoring as a means of insuring the privacy of data. After all, the government probably has petabytes of encrypted data from their nationwide wiretapping of telephone and Internet [sc.edu] communications they would love to be able to decrypt quickly.

Carl Sagan Said it Best

[deadline]

I paraphrase:

"extraordinary claims require extraordinary evidence"

Yet another under construction web page and half baked idea. I pity the investors. And remember what Feynman said (which is still true today):

"No one understands quantum mechanics"

Which does not keep us from using the results of a a highly successful theory, but just keep in mind, wave function computing is not going to be easy, but I believe it is possible. And I should know, I'm made of atoms.

Do they know what they are talking about?

[rufusdufus]

The linked article, and the company web site is very sparse on information. Is there any indication that this guy knows what he's talking about? I did find one 'fact' on their web site [dwavesys.com] that indicates that the answer may be no. Take a look at the last paragraph on the page:

Quantum computers can be used to get approximate solutions to large NP-complete optimization problems much more quickly than the best known methods running on any supercomputer.

I think this statement is incorrect [wikipedia.org]. My understanding concurs with what is written in the wiki article:

This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete logarithm, and quantum physics simulations. However, there is no proof that the advantage is real: an equally fast classical algorithm may still be discovered (though some consider this unlikely). There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. It is quantum database search, and can be solved by Grover's algorithm. In this case the advantage is provable. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers.

and

BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

Re:Advantages?

[RKBA]

I don't claim to be a mathematician, but it's pretty easy to show that factoring is a boolean satisfiability (SAT) problem [wikipedia.org] and is generally believed to be at least NP-Hard, if not NP-complete as SAT is. Consequently, if factoring could be "solved" (ie; performed "easily" by use of quantum computing or other means) then any other NP problem could be cast in terms of a SAT problem for easy solution. That would mean P=NP, would it not?

Re:Advantages?

[Anonymous Coward]

> Quantum computers can be used to get approximate solutions to large NP-complete optimization problems much more quickly than the best known methods running on any supercomputer.

Ahh. Let's break it down, shall we?
NP-complete are decision problems (yes or no), not optimization
*approximate* solutions for NPC - we know how to do those in polynomial time, you don't exactly need a quantum computer there; it's the exact solutions that are hard
approximate solutions for *NPC* - they do however not transform very well between problems so each problem would need a different method (the exact solutions can be transformed)

Re:Advantages?

[EJB]

Not to mention Darwin's apple or Rembrandt's Mona Lisa. ;-)

(Try "Schrodinger's cat" or the "Heisenberg uncertainty principle")

Re:Advantages?

[Anonymous Coward]

Factoring may a SAT problem, but that doesn't mean SAT is always a factoring problem. All that says is that a SAT solver could solve factorization.
Prime factorization is in NP, so if it is proven NP-Hard, it must be NP-Complete.

Re:Advantages?

[StikyPad]

Except that taxation is an illusion, since the government creates the money. What they're really doing is pretending to give it to you. The most obvious version of this is that government workers pay taxes, but we're all government workers indirectly, since we work for the government's money. If taxation did not exist, salaries would just be lower. You wouldn't make any more money, and even if you did, everyone else would too, which means inflation would increase to offset the extra cash. Remember, inflation is set by how much disposible income people have on average. The prices of goods and services is, and always will be, directly proportional (or at least closely linked) to how much the lowest paid workers make. If they make "more," the price of goods and services must increase -- both because you're paying the people who make them more, and because prices are proportional to average income. When income goes up, prices always follow. The only way the cycle could end is if all matter and energy were reduced to 0 value, which is highly unlikely.

Re:QP =? NP

[lgw]

That's the promise of Quantum Computing. I'm quite skeptical, but given the NSA is suggesting that one rely on ECC instead, there's something brewing: the NSA has given *very* good advice historically, though it has sometimes taken the private sector decades to understand.

Also note that factorization hasn't been *proven* NP-hard, so there may be a different explanaiton for the NSA's advice. They are the world's largest employer of math PhDs, after all, and it's just possible they know something we don't.

In any case, there's a lot of study about what kind of problems a quantum computer could solve in P time: it's *not* all of NP, which is pretty interesting in an abstract way even if QC turns out to be BS.

Re:Advantages?

[Luyseyal]

1) No gov't oversight
+
2) Dismantling of public-funded education
=
Aristocracy within 2 or 3 generations because the concentration of wealth at the top will far exceed the paltry pittance at the bottom. People complain about wealth at the top today -- wait til the Gilded Age of Libertarianism takes over.

Did you know Libertarian arguments favor child labor?

1) It's the parent's right to force a child to work. This has been the case for pretty much ever. Parents force their kids to do chores. Parents regularly employ their children in TV and movies. It's a basic tenet of every culture and society that children do work for their parents.

2) Gov't should not deny parental rights to child earnings by telling them their kids have to go to school (assuming we have any since public education is Evil[tm]).

3) The poor will force their children to contribute to household income using basic labor rather than paying for an education and deferring earnings. Obviously, an uneducated child's overall wealth potential decreases dramatically.

4) So, the poor get poorer (and more ignorant) and the rich get richer.

5) The rich, knowing that strict Libertarianism does not favor them, will do what they have always done: change the laws to favor themselves.

Ergo, over time, a Libertarian system favors Aristocracy.
-l