Recently a friend of mine observed in an email discussion “I must admit I find it a little difficult to keep up with the various definitions of quantum computing.”
A healthy sign for an enlightened confusion, because this already sets him apart from most people who still have yet to learn about this field, and at best think that all quantum computers are more or less equivalent.
As computers became an integral part of peoples everyday lives, they essentially learn the truth of Turing completeness – even if they have never heard the term. Now, even a child exposed to various computing devices will quickly develop a sense that whatever one computer can do, another should be able to perform as well, with some allowance for the performance specs of the machine. Older, more limited machines may not be able to run a current software for compatibility or memory scaling reasons, but there is no difference in principle that would prevent any computer from executing whatever has already been proven to work on another machine.
In the quantum computing domain, things are less clear cut. In my earlier post where I tried my hand at a quantum computing taxonomy, I focused on maturity of the technology, less so on the underlying theoretical model. However, it is the dichotomy in the latter that has been driving the heated controversy of D-Wave’s quantumness.
When David Deutsch wrote his seminal paper, he followed in Turing’s footsteps, thinking through the consequences of putting a Turing machine into quantum superposition. This line of inquiry eventually gave rise to the popular gate model of quantum computing.
D-Wave, on the other hand, gambled on adiabatic quantum computing, and more specifically, an implementation of quantum annealing. In preparation for this post I sought to look up these terms in my copy of Nielsen and Chuang’s ‘Quantum Computation and Quantum Information’
At the time it was not clear how the computational powers of the adiabatic approach compared to the quantum gate model. Within a year, Vazirani et al. published a paper that showed that Grover Search can be implemented on this architecture with quantum speed-up. And although the notoriety of Shore’s algorithm overshadows Grover’s, the latter has arguably much more widespread technological potential. The Vazirani et al. paper also demonstrated that there will be problem instances that this QC model will not be able to solve efficiently, even though they can be tackled classically.
In 2004 a paper was submitted with a title that neatly sums it up: “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation” (Lloyd et al.)
If D-Wave had aimed for universal adiabatic quantum computation, maybe it would not have experienced quite as much academic push-back, but they pragmatically went after some lower hanging fruit i.e, quantum annealing. (Notwithstanding, this doesn’t stop MIT’s Seth Lloyd from claiming that the company uses his ideas when pitching his own QC venture).
An adiabatic quantum computing algorithm encodes a problem into a cost, or in this case energy function, that is then explored for its absolute minimum. For instance, if you try to solve the traveling salesman problem your cost function would simply be distance traveled for each itinerary. A simple classical gradient descent algorithm over this energy ‘landscape’ will quickly get stuck in a local minimum (for an analog think of balls rolling down the hilly landscape collecting at some bottom close to were they started and you get the idea). A truly quantum algorithm, on the other hand, can exploit the ‘spooky’ quantum properties, such as entanglement and the tunnel effect . In essence, it is as if our rolling balls could somehow sense that there is a deeper valley adjacent to their resting place and “tunnel through” the barrier (hence the name). This gives these algorithms some spread-out look-ahead capabilities. But depending on your energy function, this may still not be enough.
The graph bellow illustrates this with a completely made-up cost function, that while entirely oversimplified, hopefully still somewhat captures the nature of the problem. To the extent that the look-ahead capabilities of an adiabatic algorithm are still locally limited, long flat stretches with a relative minimum (a ‘plain’ in the energy landscape) can still defeat it. I threw in some arbitrary Bell curves as a stand in for this local quantum ‘fuzziness’ (the latter incidentally the correct translation for what Heisenberg called his famous relation).
To the left, this fuzzy width doesn’t stretch outside the bounds of the flat stretch (or rather, it is negligibly small outside any meaningful neighborhood of this local minimum).
On the other hand, further to the right there is some good overlap between the local minimum closest to the absolute one (overlayed with the bell curve in green). This is where the algorithm will perform well.
D-Wave essentially performs such an algorithm with the caveat that it does not allow completely arbitrary energy functions, but only those that can be shoe-horned into the Ising model.
This was a smart pragmatic decision on their part because this model was originally created to describe solid state magnets that were imagined as little coupled elementary magnetic dipoles, and the latter map perfectly to the superconducting magnetic fluxes that are implemented on the chip.
In terms of complexity, even in a simple classical 2-d toy model, the amount of possible combinations is pretty staggering as the video below nicely demonstrates. The corresponding energy function (Hamiltonian in QM) is surprisingly versatile an can encode a large variety of problems.
