Commercial Quantum Computer

[Dan]

Found this at slashdot. Seems pretty cool, but I accidentally read the "description" first and had to wiki it.

[Lepton*]

Cool, yeah, but with very limited application. Quantum computers are, themselves, quite limited in scope; the design of this one particularly limits the types of problems that may be solved. Still, if the technology matures and expands as D-Wave is hoping, there are going to be some very neat things in the future.

I'm looking forward to attending the demonstration in Vancouver on Thursday.

[Dan]

Nice, I'm kinda jealous. You'll get waaay more out of it than I could though.

[Lepton*]

First, I'll mention that you should be able to find video clips of the Silicon Valley show on youtube. Fortunately for me, the Vancouver show was a little bit more technically-oriented. I'll give some impressions, try to describe how the computer works, and then relate an anecdote involving a semi-famous sci-fi author.

---

First things first, it was a classy event. They held it at the local (well-endowed) science museum. The banquet afterwards had some delicious hors d'oeuvres and wine. The Silicon Valley show was at a computer history museum. I guess that they are trying to subliminally suggest that the quantum computer is the next big advance. I think that I agree.

The computer was operated remotely through the internet. The current model isn't capable of anything dazzling: the word of the day was "proof of concept". Geordie Rose, the CTO, claimed that it was solving problems at about one hundredth the speed of a new desktop computer, which seemed about right. A Sudoku solver took about 5 seconds to fill in a regular-sized puzzle. The showcase application was a program that compared a given molecule against a database to find the closest match. It seemed pretty slick. A third application was a comercially-available party-seating (ie: Bob cannot sit next to Al; Sue can't sit across from Bob, etc) program whose "guts" had been replaced with a call to the QC.

The emphasis of the event was to attract the attentions of different people to whom the computer might be useful in the future. They are planning to have a 1024-qubit model ready in the third quarter of 2008; that's about how big they'll need to go to compete with conventional supercomputers for the specific problems that are applicable to the quantum computer. The current model is 16 qubits.

Sun, the computer company, has been selling supercomputer cycles for the last year or so with little success. If D-Wave is going to succeed with their plan of a centralized server, they'll need to develop a computer that can embarassing squash the efforts of a conventional supercomputer.

---

Now, imagine a 4 by 4 grid of electrons. As you may know, electrons have an intrinsic spin, which we can think of as an arrow that points either up or down. The state of any given electron depends on the spins of it's neighbours. This is the Ising model in two dimensions, and it's essentially what same the quantum computer. (the electrons being replaced by small current-carrying loops, which are the qubits)

So imagine that, in the Ising model, you fix the spin of a certain corner electron to be up and you want to know what happens to the rest of the grid. If you have the QC running, you can set up one of the qubits to have spin up and let the rest of the qubits do their thing for a little while. Then, once it's settled, you read off the configuration of the system, and there's your answer. Well, that's not too impressive because we've used a computer that is built to be an Ising model to make a simulation of an Ising model. But the cool thing is that we can map other situations to the Ising model.

Consider a graph with 16 vertices and a number of lines that connect different vertices. You want to find the largest subset of vertices such that none of these vertices are connected by a line. Now, to map that to the QC, each of the vertices gets to be a qubit, and the lines connecting the vertices are current-carrying wires between the qubits. You set up the system, and then you read off the states of the different qubits. Of course, the system might settle into a state that isn't the true lowest energy, but if you run the simulation a few times, you'll hit the lowest energy value most of the time.

As it turns out, you can write a number of optimization-type problems into these relationship graphs, so the technique of turning them into Ising models is pretty powerful.

There is a fair bit of debate on whether D-Wave's type of QC (a superconducting adiabatic quantum computer) is capable of solving NP-Complete problems. [edit: senseless nonsense deleted]

On that technical point, I should point out that D-Wave claims they aren't going to try to break prime-factorization-based cryptography. In any case, our credit card numbers are safe for the time being. From D-Wave, anyway.

---

Spider Robinson is one of the most famous living science fiction authors. He recently published a novel whose nucleus is owing to Heinlein, which was quite a bit deal for some people. I saw him come into the room shortly before the presentation began. Afterwards, while chatting with my buddy, I mentioned that I'd seen him. No sooner had I said so than Spider himself walks up and strikes up a conversation with his wife, who'd been standing next to us the whole time. I felt like a galactic doofus. But I don't particularly like his style of writing, so it's not so bad.

http://www.dwavesys.com

[Bicho the Inhaler]

A problem is NP-hard if it is at least as hard as all NP problems. A problem is NP-complete if it is NP-hard and it is itself an NP problem. The NP-hard problems thus contain the NP-complete problems and all strictly harder problems.

From what I heard about this, they don't claim to obtain an exponential speedup on any NP-hard problem, which would be needed to truly bring any of these problems into the realm of tractability, but they do claim to obtain a quadratic speedup, which is still notable. This is apparently better than the current best published theoretical result, at least on the problem they chose. (According to my professor.)

[L'lanmal]

Taking a shot at explaining this to people who don't know the terminology.

Saying a problem is in P means it can be solved in polynomial time. For instance, to find the largest number in an NxN grid, you could check all (N ² ) numbers. You can do this in less than N ² comparisons, which is a polynomial in terms of N, so this problem is in P. If N is large, this may take you personally some time. But for most P problems, people consider it practical to solve them on a computer. Your home computer even.

A problem in NP may or may not be solved in polynomial time. However, if someone gave you the answer, you could check it is correct in polynomial time. For instance, you might not know a good way to factor numbers, but if someone told you that 1001 = 7 x 11 x 13, you could quickly check that by multiplying 7 x 11 x 13. You might or might not have a good algorithm for placing arithmatic opporators between the numbers 5 5 5 4 2 13 7 to make 129. But if I told you that 5x5x5-4/2+13-7=129, you could check that quickly by doing the computation. If I told you the largest number in an NxN array was 2001, you could check that in polynomial time (in this case, using the same method you would use to find the largest number).

A problem is NP-complete if it is verifiable in polynomial-time AND if you happened to know all the answers to it, you could solve any NP problem in polynomial time. So suppose I asked you how to insert operators into 5 3 5 4 2 13 7 9 12 1 2 1 1 3 to make 78. You could go to this machine that solves NP-complete problems, ask it a (seemingly unrelated) problem. It would tell you something like a salesman should go to France, then England, then the U.S., then Japan to minimize travel time, then you could take that answer and do some (polynomial time) work and come up with the answer to my question.

A problem is NP-hard if you happened to know all the answers to it, you could solve any NP problem in polynomial time. However, you might not be able to easily check that the solution to the NP-hard problem is correct. If you only care about the NP problem, this won't be a problem because you can quickly check the answer to your NP problem. But if you are building a computer to solve an NP-hard problem, it may take a while to convince people that your computer always gives the right answers.

If anyone found a polynomial-time solution to either an NP-complete or NP-hard problem, then you could find polynomial time solutions to any NP problem, showing that P and NP are no different. Since most public-key cryptography relies on problems which can be "verified" quickly (decoded if you know the key) but not "solved" quickly (decoded if you DON'T know the key), this is would be a very significant thing. As it has stood before, when computers get fast enough to break your encryption, you could scale up your method to make it unpractical to break. (For the methods you normally hear about, go from an 8-bit key to a 32-bit key to a 128-bit key, etc. From the names, you might think a 32-bit encryption is four times better than an 8-bit. This would be true if it were a linear problem. If it were a O(N ² ) problem like finding the largest number in an NxN array, it would be 4 ² =16 times better.
But if the problem is non-polynomial, it can be much, much better than that.) If a polynomial time algorithm existed, increasing key length would have a less-profound impact on solving time.

The quantum computer does not claim to do this, but only claims that it will eventually be able to solve NP-problems faster. So the question of "How much faster?" will be vital to its success.

[Antrax]

Wow, those are some good explanations.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Lepton]

I'm not sure what I was thinking when I wrote that stuff about NP-hard and NP-complete. I've removed it.

[Antrax]

Well, from your description, it sounds like this computer could solve the boolean satisfiability problem (SAT / 3-SAT) which is NP-complete, and maybe even its stronger cousin (PSPACE-complete, which contains NP), TQBF (True Quantified Boolean Formula). Do you have any links to any research about this?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Nsof]

While able to solve integer factorizations, quantum computers are not known to solve np-complete problems. (Integer factorization is not known to be NPC (it is even suspected as not NPC).)

The fact that quantum computers can solve integer factorizations and ruin all current encryption methods is meaningless since together with that comes Quantum cryptography which is much better.

[L'lanmal]

[extropalopakettle]

[Dan*]

This is awesome. Thanks Lepton for reporting.

[Antrax]

Quantum Cryptography I do know sometihng about, and from what I've seen, it's still in the stage where the encryption overhead is as large as the message you want to send itself. There's a protocol where you use n bits (with n as a safety factor, so the odds of an adversary breaking the encryption is 2^-n) to pass one secure bit, and a more efficient one based on ideas from coding theory, where you transfer n secure bits by transmitting O(n) bits with the same security factor.
So, still not half as practical as today's ideas.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Lepton*]

Exactly, Antrax. Quantum cryptography is quite overblown. If I want to send my friend Alice a secure message, it would be just as secure for me to go over to her house, flip a coin N times and use the binary sequence as a crypto key on a one-time pad. It gives a way to bootstrap against a man-in-the-middle attack, but then, given that the coherence of an entangled quantum state isn't going to survive outside of a dedicated fiber-optic line, there's no need to bootstrap when you are communicating with someone a few minute's drive away.

Still, it's nice to see quantum mechanics in the headlines. It's really a cool idea.

[Lepton*]

extro: In short, no. The quantum part is only useful to detect an eavesdropper.