What I mean when I say analog computer, or why I hate the gate model part 1. August 22, 2006
Posted by Geordie in General.trackback
Today I’m going to talk about analog computers, but first I’m going to define what I mean by the term. Here is a beautiful definition from a beautiful paper:
…analog computation is quite different from the commonly used binary-digital computation. In the digital approach, you first devise an algorithm (a set of instructions for finding the solution to a problem), then execute each step of the algorithm in the manner of Boolean operation. In contrast, analog computation is concerned with no symbolic Boolean operation; instead it utilizes the properties of a physical system to perform the mathematical operations required for the solution.
…analog computation is quite different from the commonly used binary-digital computation. In the digital approach, you first devise an algorithm (a set of instructions for finding the solution to a problem), then execute each step of the algorithm in the manner of Boolean operation. In contrast, analog computation is concerned with no symbolic Boolean operation; instead it utilizes the properties of a physical system to perform the mathematical operations required for the solution.Yeah that’s sweet.
Something important to note: The definition of analog computer I’m using is the one in the quote above. Note that NOWHERE does it say anything about continuous variables, etc, or any of the other additional stuff that sometimes people associate with analog computation. The core of the above is simply that an analog computer uses the natural physical evolution of some (hopefully programmable) system in order to solve a difficult computational problem.
If you’re interested in quantum computation, then it’s very important to understand the difference between the two computational models outlined in the above quote. In the “digital/gate” approach, algorithms are compiled to gates which are then “fed” to a circuit containing bits/qubits. In the analog approach, there are no gates; there is just the natural physical evolution of some system, which somehow is supposed to calculate something interesting.
Alot of research in quantum computation focuses on the “gate model” applied to quantum systems. Now if you know me you know I HATE the gate model. For various technical reasons (which eventually I’m going to enumerate) I don’t think gate model quantum computers are ever going to be commonplace.
This being said, the gate model is quite popular, and for many people learning about quantum computation, it’s the only model you learn about, which is a shame (since building them is verging on impossible). Some of the concepts people take for granted, such as the concept that noise is always harmful to quantum computation, really only apply to the gate model and aren’t generally useful concepts for other models of quantum computation.
OK so I hate the gate model. But I really love another model. It’s called adiabatic quantum computation.
Now we don’t exactly do adiabatic quantum computation (AQC) at D-Wave; our processors use a remarkable variant of it, developed internally here. Followers of our progress will note that we almost never talk about the technical details of what we’re doing. We are however going to disclose the computational model of the processor in order to show experts how it works “under the hood”. Stay tuned.
Anyway AQCs are analog computers. There are two very good papers that talk about how you might build an AQC using superconducting qubits here and here.
The way the AQC model works is that you build an array of qubits (say a square grid for example) with programmable couplers between qubits (see here for some published info on one of D-Wave’s programmable couplers). The settings of these couplers, together with individual biases (favoring one qubit state over the other) on each qubit, comprise the machine language of an AQC. The user of the AQC (1) starts the machine with all of the couplers turned off and all of the local biases favoring the 0 qubit state; (2) turns on a tunneling term between the qubit states of each qubit; (3) slowly turns off the tunneling term while tuning the couplers and local biases to their target values; (4) measures the final states of the qubits. That’s it. No gates.
There are alot of very nice features of the AQC model that make it MUCH easier to build one than a gate model quantum computer. I’m not going to go into all of them just yet (I’m going to later after our computational model paper publishes). So we must be giving something up, right? No! AQC is formally equivalent to the gate model in computational power.
It really is much easier to build an AQC (or its cousin cluster state QC, which is also an analog computational model) than a gate model QC. So why aren’t more people trying to build AQCs or cluster state QCs? I’m not sure exactly, but I think it is related to the interdisciplinary nature of this sort of development. In order to appreciate how much of a difference there is (practically) in difficulty between building two different hardware proposals, the input of a lot of engineers is needed.
Unfortunately, and to the field’s detriment, there are only a handful of places in the world where the type of infrastructure exists to separate practical models (such as AQC) from models that are probably only useful as theoretical abstractions (the gate model).
Those are some fascinating papers you linked to. Sadly they are way over my head. Too bad it’s not this blog entry that is being slashdotted, because there is so much information here now.
If I understand correctly, this approach seeks to avoid the superposition of states that makes the more popular quantum computing approach so exotic sounding. That makes it sound less quantum, even though it achieves the same factor of speed-up of NP problems and is more scaleable.
When those papers talk about an algorithm taking polynomial time, is that the time spent in step 3 where you are slowly transitioning from the starting state to the final state? During that the time, are perturbations are going back and forth at the speed of light while it finds the lowest energy state? I would expect that measuring a highly coupled system to such precision would suffer from something analogous to virtual particles that would introduce random errors. The papers you cite talk about how the feasibility of this approach being established by simulations of up to 26 nodes. That means any quantum effect that is not represented in the simulation model really hasn’t been considered yet. Only real experiments will show how well it will work.
Anyway, thanks for providing these details on such promising work.
thanks for the clarification. can you give hints on number of qubits achieved in current and anticipated models?
Reading one of the scaling papers it talks about theoretically getting to hundreds or thousands of qubits in optimal cases.
In a 2004 Business 2.0 article it mentions that you, gordie Rose had a target of 32 qubits for 2007.
I got the prior article slashdotted. My guess is when Gordie releases the service that he mentioned or states some key info like qubits for 2007 then we can get another article slashdotted.
Meanwhile I can send some stuff up to digg and some other sources.
I am excited by the potential for this technology to enable more rapid progress in areas like Molecular nanotechnology. (quantum simulations etc..)
blue gene just lost a lot of luster
“blue gene just lost a lot of luster” Yeah right.
Rose, you say that your definition of analog computer does not mention continuous variables. Well, just because you choose to ignore the truth does not mean it’s going to go away. The problem with analog computers is that they are not very accurate. Consider slide rules: analog computers, easy to implement, and they DO work. But they give you E-3 accuracy. PCs, on the other hand, give you E-15 accuracy. Have your engineers estimated the accuracy of your machine? Does your company have a plan B that includes digital circuits and error correction?
Hi rrtucci! The difference between classical analog computers, like slide rules, and quantum ones, like AQCs, is that in approaches like AQC the natural physical variables we’re using for computation are inherently discrete because of QM, and that discrete QM nature protects them from the types of errors that usually plague analog computers (note that this is far from obvious - see Ed Farhi’s 2001 Science paper on AQC for an overview). So I wanted to point out that even though our normal conception of analog computers are machines where the variables we care about (position, angles, etc.) are continuous on the scale of precision of our measuring devices, in analog quantum computational models these variables are discrete on the scale of the measuring devices, and this discrete nature leads to an energy gap between the “correct” answer and approximate answers which protects these approaches from errors. Therefore the definition of analog computation that applies for both quantum and classical machines is the one I quoted in the post - alot of the other tags analog computation gets only apply to classical analog computers.
Yes but, adiabatic quantum computers are more analog than digital quantum computers. They evolve continuously rather than in discrete steps. And discrete energy levels can be so close compared to noise that their discreteness becomes irrelevant.
Have your engineers estimated the accuracy of your machine, either analytically (Cramer Rao bound for a model, etc.) or by computer simulation? Graphs from such studies would be very pertinent to this conversation. Such studies can be wrong too, but at least they go beyond the point of mere words. Of course, your experiments will answer the accuracy question eventually, but not trying to estimate it beforehand would be a reckless gamble for a company.
I agree with your dislike of the gate model, it’s stiffling and antiquated, but I think the authors of that paper should have chosen a different term than “analog” for their method. Unfortunately for them, it already is in common use for “continous value” computation methods, therefore trying to use it for “analogy-based” will cause confusion among readers.