So many times scientists are very harsh on science journalists. Thus it is refreshing to see this article in the MIT Technology Review by Jason Pontin on D-Wave’s recent Orion quantum computer. The article includes an interview with D-Wave’s Geordie Rose by Pontin which is rather refreshing mostly for the fact that Pontin pulls out the PCP theorem on Geordie (Gunslinging computer scientists come equiped with the PCP theorem strapped to their belts. Only recently were the schematics for how to build this gun made accessible to mere mortals like us physicists.) The article seems rather fair to me, airing both Geordie’s views as well as asking the hard questions, includes criticisms from Scott and Umesh Vazirani, as well as a more moderate view from Seth Llloyd. Whether you are satisfied with the answers Geordie gives, of course, is a different matter! For example, me I don’t think that the current setup they have scales if they continue with the same setup they have here (energy gap goes like one over problem size, I might buy that thermalizing helps a bit, but am extremely skeptical when the energy from the environment will swamp the energy spectrum), but this is different from believing that it’s not possible to modify the path they are taking to actually scale their system.
Update: Here is the New York Times version of the article, where, sadly the PCP theorem has been removed. Sad, I mean all the latte-sipping Volvo-driving lefties I know can speak elegantly in an instancet about the PCP theorem and approximation algorithms.
O brave new quantum world!
Dave, let me repeat a question here that I just posed on Scott’s blog. How do you solve Sudokus with just 16 qubits? Moreover, 16 qubits that only execute an Ising Hamiltonian?
“(energy gap goes like one over problem size”
I think I’m totally confused, but isn’t the whole disppointment in AQC over the fact that the energy gap is in general *exponentially* small, not inverse polynomial like 1/n or 1^n^2?
You’re talking about the ground state gap E1-E0, right?
-random layperson
Greg: Whether or not they actually solved the sudoku problem or not is of course open to speculation. I should, however, point out that they may be allowing the use of a classical computation as well as the ‘quantum computation’ that is going on.
While this may sound dodgy, virtually all quantum computer implementations require some classical computer controling them i.e. storing measurement results and doing feed foreward.
One way to solve a sudoku problem would be to cast the grid in terms of an Ising network of spin-4 particles, setting the couplings so that illegal solutions suffered an increased energy, which would be relatively easy to do. The problem then reduces to finding the ground state of the system.
D-Wave could be doing something similar, and finding the ground state for various regions independantly, and then trying to piece them together (which would be a perfectly legitimate use of their system). The problem could also be solved by simulated annealing, so it still wouldn’t be obvious whether they had a quantum computer or a classical one, (even to them).
That said, the above was just a guess at how the problem may be approached, so I have no idea whether it is what D-Wave actually is doing.
Also I have no idea how hard sudokus are to solve in general. The fact that I can do it by hand probably isn’t a good sign.
Thomas:
There are two issues here. One is if you are going to use adiabatic quantum computers in the way they were originally envisioned. In this case, the problem with using them to solve hard problems (like NP-complete) problems is that the gap in these systems seems to shrink exponentially. But there is another way to use adiabatic quantum computers and this is to “simulate” a quantum circuit. For these constructions, the gap goes like one over the a polynomial in the circuit size (roughly). This later idea is recent and is, in my opinion, the more interesting use of the type of quantum computer D-wave is trying to make. D-wave doesn’t sell this idea yet, in part because the current constructions for this type of adiabatic quantum computation can’t be achieved using the Hamiltonian they have.
Ahh, polynomial in the circuit size. Thanks for clarifying!
-Thomas
hi dave!
But there is another way to use adiabatic quantum computers and this is to “simulate†a quantum circuit.
are you referring to quant-ph/0405098?
Yes, and follow ups, like quant-ph/0504050
do we have a ‘recipe’ how to translate an arbitrary quantum circuit into a quantum adiabatic protocol based on qubits?
Yes. See those two papers. In particular the later paper shows how to do this with qubits on a planar lattice. There is also a followup paper by Mizel, Mitchell, and Lidar which does this for qubits with spatial degrees of freedom. I myself have a paper which I’m working on which does this for qubits in a simple manner.
Sad, I mean all the latte-sipping Volvo-driving lefties I know can speak elegantly in an instance about the PCP theorem and approximation algorithms.
Was that supposed to be “elegantly in an instant”?
Doh, thank you Typo Guy!
Greg: Maybe you should just ask me how it works. Seems like that would be the most straightforward way to find out.
One way to solve a sudoku problem would be to cast the grid in terms of an Ising network of spin-4 particles.
I’m glad that you’re thinking about this question, because I have the growing sense that the Sudoku demo was like pulling a curtain rod out of a top hat. It just doesn’t fit.
Yes, you could suppose casting a Sudoku as an Ising network of spin-4 particles. But that is not what the “Orion” is. It is a model of a 4×4 grid of spin-1/2 particles. They have been calling the memory units qubits, not qunones. They have also said that the Orion can do 65,536 things at once, which clearly implies binary state.
Moreover, even if you did suppose such a model of partial Sudokus, it wouldn’t be a nearest-neighbor Hamiltonian. If you have a 4×4 grid of spin-1/2 particles with a nearest-neighbor Hamiltonian, then I have trouble fitting more than about a 2×2 piece of a Sudoku inside of it.
D-Wave could be doing something similar, and finding the ground state for various regions independantly, and then trying to piece them together (which would be a perfectly legitimate use of their system).
It’s hard to imagine doing that in any way that isn’t more classical work than just solving it classically.
That said, the above was just a guess at how the problem may be approached, so I have no idea whether it is what D-Wave actually is doing.
Well, there is one simple way to achieve the demo that has been videotaped, which is to fake the whole thing. I have yet to see another believable explanation.
All right, how does it work?
Greg: We are going to release a bunch of “case studies” when the system goes live on-line. That will contain a thorough write-up of how everything works top to bottom. In advance of this, here are some of the main ideas/concepts for doing any constrained optimization problem (including the sudoku example).
Observation #0: Sudoku can be recast as a constrained optimization problem over binary variables.
Observation #1: Any constrained optimization problem can be recast as a Maximum Independent Set (MIS) problem with N vertices and E edges.
Observation #2: All 156 graphs with up to 6 vertices can be embedded in a 4×4 grid of qubits with NN and NNN couplers. A subset of graphs with vertices between 7 and 16 can likewise be embedded.
Observation #3: Most MIS problems generated by real applications have N>>16 and therefore cannot be directly solved in one shot on the hardware we’ve got today.
Observation #4: Many of the best classical heuristics (such as local search) work by sequentially solving sub-problems that are much smaller than the original problem. A local search heuristic might work as follows: (a) pick a subset of the vertices that fits on the hardware, using at most linear (in N+E) work; (b) find configuration of variables that optimizes the subproblem in hardware; (c) use that result to improve the “big problem” solution quality; (d) repeat until exit criteria achieved.
This approach can be used for any size hardware, with bigger and bigger local search neighborhoods as the number of variables the hardware can handle increases.
Hope this helps!
hi geordie!
it’d be really cool, if you could explain the alogirthm…
“Can I take your summary as an explicit assertion that the Sudoku that you demonstrated was solved in this way?”
No. It’s just a set of observations. The actual way we did it is considerably more sophisticated, and will be described in a case study released when the system goes live on-line.
Greg and Andrew: What I laid out was a perfectly reasonable algorithm for solving sudokus on our hardware, and in fact we have during the course of our projects run an algorithm exactly as I described.
We have also done dozens of variants, many of them much more effective. If you want to think about this as a particular example you can.
Greg: if you really have the experience you claim–which I doubt, given that I have seen no peer review of those statements–you should have been able to figure this little problem out. We use it (and others that are much harder) to screen potential software employees in our interview process.
Hi Joe, absent a full peer review of your statement about google scholar, I simply can’t accept this as evidence. Well, there is one simple way to achieve the google scholar entry, which is to fake the whole thing. I have yet to see another believable explanation.
Re. the local optima issue: yes the algorithm above is most definitely a heuristic and most definitely will not in general provide global optima in all cases. It isn’t even guaranteed to work well (no local search techniques are). Most of our algorithms are heuristics.
Joe:
“how can you be sure that your device will be more useful than a classical algorithm ahead of time?”
We can’t be sure. The only way to know for sure is to build/test/redesign and use the knowledge we gain along the way to make it as useful as it can be.
What you describe, in the case of Sudoku, rewrites the Sudoku puzzle twice, first as an abstract problem with binary variables, then an MIS problem. The result has at the very least hundreds of vertices and could easily have thousands. The 16 qubits can locally optimize between 6 and 16 of these sets of vertices. The qubit hardware would have to be called many times to do this optimization.
The demo did include a solution to a Sudoku puzzle. Can I take your summary as an explicit assertion that the Sudoku that you demonstrated was solved in this way?
You began by saying that the most straightforward way to find out a Soduku was solved with 16 qubits in the demo is to ask you. After offering a set of hypotheticals, you punted on the question. That is a blatant evasion. I have more than 20 years of experience with practical computer programming, with theoretical algorithms, and with quantum mechanics. I don’t need to be protected from jargon. A concise, direct, convincing explanation of how it was done should be possible.
Long time reader, first time poster (mainly because I’m a layman as goes this stuff, heh.)
Just wanted to emphasize Greg’s assertion. I’m sure there’s a good explanation somewhere but that was a BLATANT evasion.
Geordie, after reviewing the outline for your algorithm above, I must admit that I have serious concerns about your approach. The algorithm, as you outling it above, seems to suffer from a possibility of getting stuck in local minima, where the number of operations required to reach a better approximation is larger than the number of vertices which can be stored simultaneously in your processor.
This being the case, it seems that simulated annealing might well be a better approach as it is not as tightly boung by the 16 bit operation limit that would appear to be imposed in the case of Orion. Maybe I’m missing something, but the way you chose to express you algorithm is somewhat ambiguous.
And in defense of Greg, I should point out that you can get “peer review of those statements” with a little help from google scholar: http://scholar.google.com/scholar?q=Greg+Kuperberg&hl=en&lr=&btnG=Search
Not to be pedantic (well, actually, yes, to be pedantic) my statement about google scholar is verifiable.
On a more serious note, given the limitations of such heuristic algorithms, how can you be sure that your device will be more useful than a classical algorithm ahead of time?
“Rabbi, tell me, how does the telegraph work?”
“Oh, that’s simple. Imagine a very-very long dachshund. So if one pulls the dog’s tail, then the dog barks. This is how it works!”
“I see! But rabbi… Then how does the wireless telegraph work?..”
“It works exactly the same way – but without the dachshund!”
hi greg! hi geordie! hi all!
please, an unfriendly discussion doesn’t help anyone…
geordie, thanks for the outline of your algorithm. it’s very general, but it provides some insights. i have some questions, though…
#0: recast Sudoku as a constrained optimization problem over binary variables
trivial attempt: for i,j,k=1…9, if the cell in the i_th row and the j_th column has the value k, then sudoku_{ijk}=1, else sudoku_{ijk}=0. so one needs 9*9*9=729 binary variables to encode a sudoku (which is certainly not optimal).
the constraints should consider that each integer appears only once in each 3×3 area/column/row, that each cell contains only one single integer and that there are some fixed cell values: sudoku_{i,j,k=value}=1 and sudoku_{i,j,k!=value}=0
#1: recast the constrained optimization problem as a MIS problem with N vertices and E edges
unfortunately, i’m not familiar with this mapping… for M binary variables are there some lower or upper bounds for the number of corresponding vertices N? is the mapping bijective? i suppose that the recast requires polynomial time.
#2: All 156 graphs with up to 6 vertices can be embedded in a 4×4 grid of qubits with NN and NNN couplers
ok. so orion solves a MIS problem with maximally 6 vertices?
#3: Most MIS problems generated by real applications have N>>16
ok
#4: sequentially solving sub-problems that are much smaller than the original problem
so the trick is to map the sudoku problem and its global constraints into a six vertices MIS problem with local constraints – in an iterative fashion.
i’m really looking forward for your publication! btw, geordie, would it be the algorithm which you announced on your blog?
I attended lectures by Greg Kuperberg and he’s one of the best math/CS guys around (top 16 putnam i believe?) and he’s published on quantum computing. Even my PhD math advisor at Berkeley said “Ah Kuperburg, he does hard math.” If Geordie can’t convince Greg, I think the problem lies with Geordie.
Does “latte-sipping Volvo-driving lefties” mean you’re possibly a tea-sipping Volkswagon-driving conservative?