If you are able to get substantial numbers of "quantum bits" to stay entangled with one another, and hence behave in all those counterintuitive ways quantum things do, then you can (in principle) use the resulting machinery to perform some kinds of computations faster than any "conventional" computer can do them.
Making that actually happen is an enormous engineering challenge. No one's been able to do it with more than a very few bits, yet.
If they did, it would be a big deal: in particular, something called Shor's algorithm allows you (in principle) to factorize numbers efficiently on a quantum computer, and a big enough quantum computer would effectively break RSA encryption. As an indication of the progress that's been made in practical quantum computation: the first ever demonstration of Shor's algorithm in practice was in 2001 when some researchers at IBM managed to use it to find that 15 = 3x5; there was a major breakthrough in 2011, when the algorithm was used to find that 21 = 3x7.
Some other varieties of public-key encryption are not, so far as anyone currently knows, broken once we have quantum computers. But exactly what quantum computers are capable of is a very open question.
BACKGROUND: D-Wave
There's a company called D-Wave that, for years now, has been touting what they claim is a quantum computer of an unconventional design, very different from what most quantum computing researchers have been trying to do (or trying to analyse the capabilities of). They have claimed that their machine works with hundreds of (qu)bits, whereas no one else is using more than, say, ten. They have attracted a lot of media attention and a lot of money.
(Their machine allegedly does something called "adiabatic quantum computing", which somewhat resembles the non-quantum optimization process called simulated annealing. It may or may not actually be more powerful than simulated annealing.)
Until very recently, D-Wave (despite their great media success) had provided no evidence at all that their machine actually does anything "genuinely quantum", or that it is able to do anything that can't be done just as well with conventional classical computers costing much, much less than their machine.
Scott Aaronson (a young but already eminent researcher in the theory of quantum computation) has long been a leading critic of D-Wave, countering their hype (and that of those in the media who like their story) with patient skepticism and careful analysis.
A couple of years ago, D-Wave (for the first time) offered some actual evidence for actual quantum effects having some actual contribution to the behaviour of their machine. Aaronson's post about this -- http://www.scottaaronson.com/blog/?p=639 -- said (among other things) "I hereby announce my retirement as Chief D-Wave Skeptic".
WHAT'S GOING ON NOW
In the last few days there have been breathless reports in the media about how D-Wave's machine has been found to be thousands of times faster (at solving a single particular problem, the one it was designed to solve) than conventional computers. These reports have been discussed here on HN, too.
So Aaronson is back to debunking D-Wave hype. First, though, the good news: it does appear that this latest work gives some evidence that D-Wave's machine is genuinely doing something quantum. Specifically, some researchers have taken the same kind of problems that D-Wave's machine solves, and compared the performance of D-Wave's machine with (1) an algorithm called "quantum Monte Carlo", which is approximately a simulation (on conventional classical computers) of the particular quantum thing it's alleged to be doing and (2) a conventional computer doing ordinary simulated annealing. They found that the performance characteristics -- which problems are easier to solve and which harder, and by how much -- match up well between D-Wave's machine and the simulation of the quantum process it's meant to be an implementation of, whereas classical simulated annealing doesn't match at all well. So it does seem pretty likely that D-Wave's machine is doing roughly what D-Wave say it is, and that this truly is a quantum effect. Yay!
The bad news, part 1: This particular quantum phenomenon turns out to be one that can be efficiently and accurately simulated using ordinary classical computers. In other words, in so far as D-Wave's machine is really doing that, it offers no prospect of a more-than-constant-factor speedup relative to conventional, "non-quantum" digital computers. (The quotation marks are because actually semiconductors, as used in all integrated circuits, are fundamentally quantum devices. But they don't exploit quantum coherence in the sort of way quantum computers do.)
The bad news, part 2: At the same time as one researcher was comparing D-Wave's machine against a bunch of classical optimization algorithms and finding that D-Wave's machine performs much better, another researcher was comparing it against a different classical optimization algorithm, namely (you guessed it) simulated annealing -- and finding that simulated annealing actually solves the problems just as well as D-Wave's machine, but much faster and on cheaper hardware.
CONCLUSION
(For the avoidance of doubt, this is my summary of what Aaronson says; I think he is almost certainly right because he demonstrably knows his stuff, but I'm in no position to give any endorsement beyond that.)
D-Wave do seem to have a genuine quantum device. However, it doesn't seem to be a quantum computer in the sense of something that exploits quantum effects to do computation faster than a classical device can do by more than a constant factor, and the recent hype about their machine is very misleading.
[EDITED to fix a goof where I missed out half a sentence.]
Geordie's reply to Scott's blog: "The majority of that post is simply factually incorrect.
As one example, Troyer hasn’t even had access yet to the system Cathy benchmarked (the Vesuvius – based system). (!) Yes Rainier could be beat by dedicated solvers — it was really slow! Vesuvius can’t (at least for certain types of problems). Another is he thinks we only benchmarked against cplex (not true) and he thinks cplex is just an exact solver (not true). These types of gross misunderstanding permeate the whole thing.
I used to find this stuff vaguely amusing in an irritating kind of way. Now I just find it boring and I wonder why anyone listens to a guy who’s been wrong exactly 100% of the time about everything. Update your priors, people!!
If you want to know what’s really going on, listen to the real experts. Like Hartmut.
Scott's gauntlet throw down: "Now, as for the difference between the 128-qubit machine and the 512-qubit one: based on the results Troyer explained to me (some of which, unfortunately, are not yet public), I see Geordie’s bet and raise it. Give Troyer and his postdocs full access to the Vesuvius-based system. If they can’t outperform it classically within a year or so, I will eat my words."
If you are able to get substantial numbers of "quantum bits" to stay entangled with one another, and hence behave in all those counterintuitive ways quantum things do, then you can (in principle) use the resulting machinery to perform some kinds of computations faster than any "conventional" computer can do them.
Making that actually happen is an enormous engineering challenge. No one's been able to do it with more than a very few bits, yet.
If they did, it would be a big deal: in particular, something called Shor's algorithm allows you (in principle) to factorize numbers efficiently on a quantum computer, and a big enough quantum computer would effectively break RSA encryption. As an indication of the progress that's been made in practical quantum computation: the first ever demonstration of Shor's algorithm in practice was in 2001 when some researchers at IBM managed to use it to find that 15 = 3x5; there was a major breakthrough in 2011, when the algorithm was used to find that 21 = 3x7.
Some other varieties of public-key encryption are not, so far as anyone currently knows, broken once we have quantum computers. But exactly what quantum computers are capable of is a very open question.
BACKGROUND: D-Wave
There's a company called D-Wave that, for years now, has been touting what they claim is a quantum computer of an unconventional design, very different from what most quantum computing researchers have been trying to do (or trying to analyse the capabilities of). They have claimed that their machine works with hundreds of (qu)bits, whereas no one else is using more than, say, ten. They have attracted a lot of media attention and a lot of money.
(Their machine allegedly does something called "adiabatic quantum computing", which somewhat resembles the non-quantum optimization process called simulated annealing. It may or may not actually be more powerful than simulated annealing.)
Until very recently, D-Wave (despite their great media success) had provided no evidence at all that their machine actually does anything "genuinely quantum", or that it is able to do anything that can't be done just as well with conventional classical computers costing much, much less than their machine.
Scott Aaronson (a young but already eminent researcher in the theory of quantum computation) has long been a leading critic of D-Wave, countering their hype (and that of those in the media who like their story) with patient skepticism and careful analysis.
A couple of years ago, D-Wave (for the first time) offered some actual evidence for actual quantum effects having some actual contribution to the behaviour of their machine. Aaronson's post about this -- http://www.scottaaronson.com/blog/?p=639 -- said (among other things) "I hereby announce my retirement as Chief D-Wave Skeptic".
WHAT'S GOING ON NOW
In the last few days there have been breathless reports in the media about how D-Wave's machine has been found to be thousands of times faster (at solving a single particular problem, the one it was designed to solve) than conventional computers. These reports have been discussed here on HN, too.
So Aaronson is back to debunking D-Wave hype. First, though, the good news: it does appear that this latest work gives some evidence that D-Wave's machine is genuinely doing something quantum. Specifically, some researchers have taken the same kind of problems that D-Wave's machine solves, and compared the performance of D-Wave's machine with (1) an algorithm called "quantum Monte Carlo", which is approximately a simulation (on conventional classical computers) of the particular quantum thing it's alleged to be doing and (2) a conventional computer doing ordinary simulated annealing. They found that the performance characteristics -- which problems are easier to solve and which harder, and by how much -- match up well between D-Wave's machine and the simulation of the quantum process it's meant to be an implementation of, whereas classical simulated annealing doesn't match at all well. So it does seem pretty likely that D-Wave's machine is doing roughly what D-Wave say it is, and that this truly is a quantum effect. Yay!
The bad news, part 1: This particular quantum phenomenon turns out to be one that can be efficiently and accurately simulated using ordinary classical computers. In other words, in so far as D-Wave's machine is really doing that, it offers no prospect of a more-than-constant-factor speedup relative to conventional, "non-quantum" digital computers. (The quotation marks are because actually semiconductors, as used in all integrated circuits, are fundamentally quantum devices. But they don't exploit quantum coherence in the sort of way quantum computers do.)
The bad news, part 2: At the same time as one researcher was comparing D-Wave's machine against a bunch of classical optimization algorithms and finding that D-Wave's machine performs much better, another researcher was comparing it against a different classical optimization algorithm, namely (you guessed it) simulated annealing -- and finding that simulated annealing actually solves the problems just as well as D-Wave's machine, but much faster and on cheaper hardware.
CONCLUSION
(For the avoidance of doubt, this is my summary of what Aaronson says; I think he is almost certainly right because he demonstrably knows his stuff, but I'm in no position to give any endorsement beyond that.)
D-Wave do seem to have a genuine quantum device. However, it doesn't seem to be a quantum computer in the sense of something that exploits quantum effects to do computation faster than a classical device can do by more than a constant factor, and the recent hype about their machine is very misleading.
[EDITED to fix a goof where I missed out half a sentence.]