5 ms·

Holy Quantum Annealing Qubits Batman! That article was not for the faint of geek.

JanezStupar 13y ago
I understand some of the words, but the article itself seems to me as ancient Greek. Can someone explain to me what the hell the whole story is about?
- chm 13y ago
  One could write many books on this subject. What exactly did you not understand?
  - scott_s 13y ago
    When the teacher stands at the front of the class and says, "Are there any questions? ... Anyone? Everyone understood everything?" and the students remain silent, looking at each other and hoping the other students will ask a question, the students are doing so because they don't even know how to ask a question. Their confusion is so deep that they cannot articulate what their confusion is. They don't know what they don't know - but they know they don't know something.
  - JanezStupar 13y ago
    I would just like a recap of the story for a layman. You know the sort of thing one would do to explain a computer system to his mother. The sort of thing Brian Greene does to explain string theory to the masses.
    - chm 13y ago
      D-Wave is trying to make use of the quantum properties of matter in order to solve a particular kind of problem. They want to find the ground state (lowest energy) configuration of spins (a non-classical degree of freedom) in a 2D lattice composed of N atoms. Each atom is allowed to interact with its neighbors obeying rules that are defined by the way the computer is built. They're essentially setting up a number of "qubits" (which is not related to "binary digit" other than they're both units of information) to naturally converge on the lowest energy state. All the qubits need to be entangled (fundamentally linked) in order for the system to work. This is a necessary but insufficient condition for quantum efficiency gains, which is the point Mr. Aaronson is making. The computer is not, according to recent evidence, providing computational gains. He then goes into the details, which you might or might not be interested in. If you have other questions, please ask. I'm not an expert, but I understand his argument.
- sbierwagen 13y ago
  QC is hard because it requires that the qbits be entangled with each other, but not interacting at all with the rest of the universe. This is comparable to trying to eat rice without a fork, or chopsticks, or allowing air to touch the rice. QC is very, very hard. It is entirely possible we won't see useful QC machines for decades, or even centuries. D-Wave has attracted scepticism because in the many press releases they've issued over the last 14 years, they have repeatedly claimed to have made breakthroughs in quantum computing that would be perhaps 200 years before their time, if they weren't lying. Like a Chinese manufacturer saying they'll be selling an $11 phone next spring that has petabytes of ram, and can run a simulation of a human brain in real time, which the phone uses for accurate voice transcription. D-Wave have finally, finally demonstrated a machine with a working qbit system. But the qbits are strongly coupled to the environment, and the machine runs many times slower than a classical electronic computer, even in the fake benchmarking problem that is the only thing the D-Wave machine can solve. It is an important step on the road to usable quantum computing. It is not a general-purpose quantum computer. It can't be used for prime factorization, for instance.
  - danbruc 13y ago
    Quantum annealing can be used to factor integers [1] (if those guys are correct) but the current D-Wave machines are probably unable to factor any interesting number. Here are some more hints [2] what is possible or not. [1] http://physics.stackexchange.com/questions/11063/can-quantum-annealing-be-used-for-factorization http://physics.stackexchange.com/questions/11063/can-quantum... [2] http://physics.stackexchange.com/questions/10496/what-can-the-d-wave-quantum-computer-do http://physics.stackexchange.com/questions/10496/what-can-th...
    - 8080 13y ago
      Quantum annealing can be used to factor integers in the same way simulated annealing or genetic algorithms can: yes, you can reduce factoring to a SAT problem and then give it to a genetic algorithm for SAT but it will probably take a geological era to factor even relatively small numbers. Quantum computers can factor N digit numbers with N^3 operations with Shor's algorithm, but no one has found a way to factor a number in polynomial time (in theory) with a quantum annealing scheme like the one allegedly implemented by the DWave. And I'm pretty confident that is neither possible.
- kstop 13y ago
  A company that claimed to have built a general-purpose quantum computer, which would speed up a lot of computationally-intensive tasks, may have actually built a weaker device that does something called quantum annealing, which allows it to solve only a subset of problems - those that involve finding the lowest value state in a field of lots of values. Furthermore, it doesn't look like the device solves those problems any faster than well-optimized code running on normal computers. Which cost about 10k times less.
  - kyzyl 13y ago
    Did they actually claim it was a general purpose computer? I have been following them for some time now (albeit not like a hawk) and everything I've seen from them was pretty clear in indicating that they took a different approach, i.e. adiabatic quantum annealing.
- lifeisstillgood 13y ago
  It's fairly simple When the Matrix was written the Lisp source code could not hope to compute the position of every quantum particle in the simulated universe in real time. So entanglement was invented as a means of linking quanta that were outside of each others relativistic cause-effect bubble thus reducing the number of actual positional calculations needed across the universe to a manageable amount. However the perl code used to stich it altogether allowed entanglement in some cases within relativistic reach. The hope is that this will allow us to force a buffer overflow and introduce our own qubits to be processed on the Matrix substrate. This will eventually lead to a sex party in a cave hundreds of miles below the surface. No quantum mechanics professors or students will be invited to the party HTH
- gjm11 13y ago
  BACKGROUND: Quantum computing 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 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.]
stcredzero 13y ago
> “stoquastic Hamiltonians,” Why not "stoquastic Hamilsquonians?"

I understand some of the words, but the article itself seems to me as ancient Greek. Can someone explain to me what the hell the whole story is about?

chm 13y ago
One could write many books on this subject. What exactly did you not understand?
- scott_s 13y ago
  When the teacher stands at the front of the class and says, "Are there any questions? ... Anyone? Everyone understood everything?" and the students remain silent, looking at each other and hoping the other students will ask a question, the students are doing so because they don't even know how to ask a question. Their confusion is so deep that they cannot articulate what their confusion is. They don't know what they don't know - but they know they don't know something.
- JanezStupar 13y ago
  I would just like a recap of the story for a layman. You know the sort of thing one would do to explain a computer system to his mother. The sort of thing Brian Greene does to explain string theory to the masses.
  - chm 13y ago
    D-Wave is trying to make use of the quantum properties of matter in order to solve a particular kind of problem. They want to find the ground state (lowest energy) configuration of spins (a non-classical degree of freedom) in a 2D lattice composed of N atoms. Each atom is allowed to interact with its neighbors obeying rules that are defined by the way the computer is built. They're essentially setting up a number of "qubits" (which is not related to "binary digit" other than they're both units of information) to naturally converge on the lowest energy state. All the qubits need to be entangled (fundamentally linked) in order for the system to work. This is a necessary but insufficient condition for quantum efficiency gains, which is the point Mr. Aaronson is making. The computer is not, according to recent evidence, providing computational gains. He then goes into the details, which you might or might not be interested in. If you have other questions, please ask. I'm not an expert, but I understand his argument.
sbierwagen 13y ago
QC is hard because it requires that the qbits be entangled with each other, but not interacting at all with the rest of the universe. This is comparable to trying to eat rice without a fork, or chopsticks, or allowing air to touch the rice. QC is very, very hard. It is entirely possible we won't see useful QC machines for decades, or even centuries. D-Wave has attracted scepticism because in the many press releases they've issued over the last 14 years, they have repeatedly claimed to have made breakthroughs in quantum computing that would be perhaps 200 years before their time, if they weren't lying. Like a Chinese manufacturer saying they'll be selling an $11 phone next spring that has petabytes of ram, and can run a simulation of a human brain in real time, which the phone uses for accurate voice transcription. D-Wave have finally, finally demonstrated a machine with a working qbit system. But the qbits are strongly coupled to the environment, and the machine runs many times slower than a classical electronic computer, even in the fake benchmarking problem that is the only thing the D-Wave machine can solve. It is an important step on the road to usable quantum computing. It is not a general-purpose quantum computer. It can't be used for prime factorization, for instance.
- danbruc 13y ago
  Quantum annealing can be used to factor integers [1] (if those guys are correct) but the current D-Wave machines are probably unable to factor any interesting number. Here are some more hints [2] what is possible or not. [1] http://physics.stackexchange.com/questions/11063/can-quantum-annealing-be-used-for-factorization http://physics.stackexchange.com/questions/11063/can-quantum... [2] http://physics.stackexchange.com/questions/10496/what-can-the-d-wave-quantum-computer-do http://physics.stackexchange.com/questions/10496/what-can-th...
  - 8080 13y ago
    Quantum annealing can be used to factor integers in the same way simulated annealing or genetic algorithms can: yes, you can reduce factoring to a SAT problem and then give it to a genetic algorithm for SAT but it will probably take a geological era to factor even relatively small numbers. Quantum computers can factor N digit numbers with N^3 operations with Shor's algorithm, but no one has found a way to factor a number in polynomial time (in theory) with a quantum annealing scheme like the one allegedly implemented by the DWave. And I'm pretty confident that is neither possible.
kstop 13y ago
A company that claimed to have built a general-purpose quantum computer, which would speed up a lot of computationally-intensive tasks, may have actually built a weaker device that does something called quantum annealing, which allows it to solve only a subset of problems - those that involve finding the lowest value state in a field of lots of values. Furthermore, it doesn't look like the device solves those problems any faster than well-optimized code running on normal computers. Which cost about 10k times less.
- kyzyl 13y ago
  Did they actually claim it was a general purpose computer? I have been following them for some time now (albeit not like a hawk) and everything I've seen from them was pretty clear in indicating that they took a different approach, i.e. adiabatic quantum annealing.
lifeisstillgood 13y ago
It's fairly simple When the Matrix was written the Lisp source code could not hope to compute the position of every quantum particle in the simulated universe in real time. So entanglement was invented as a means of linking quanta that were outside of each others relativistic cause-effect bubble thus reducing the number of actual positional calculations needed across the universe to a manageable amount. However the perl code used to stich it altogether allowed entanglement in some cases within relativistic reach. The hope is that this will allow us to force a buffer overflow and introduce our own qubits to be processed on the Matrix substrate. This will eventually lead to a sex party in a cave hundreds of miles below the surface. No quantum mechanics professors or students will be invited to the party HTH
gjm11 13y ago
BACKGROUND: Quantum computing 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 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.]

stcredzero 13y ago

> “stoquastic Hamiltonians,” Why not "stoquastic Hamilsquonians?"