cluster state computing

David Deutsch, one of the preeminent quantum computing theorists, has suggested on his blog that recent advances in cluster state computing mean that it might be possible to actually build a quantum computer within the next few years. See here and here. I have studied cluster state computing a little (n.b.: this is COMPLETELY DIFFERENT from classical cluster computing), and I know one thing for sure:

I haven't the FOGGIEST notion how to build a machine to run such a computation.

Deutsch seems to think that this paper by Lim et al. is a serious, practical proposal. And, it happens to be, essentially, a form of quantum multicomputer, which is my thesis topic, so I'm very interested in this. But, before we can decide how practical Lim's proposal is, we need to know at least a little bit about cluster state computing.

Be warned: cluster state computing is mathematically difficult stuff, and even more important, a real mind-bender of an idea. It is important, though, and I think the basic idea can be comprehended without following the math, so I'm going to try to explain it. One particularly comprehensive paper on it is this one, but it's rough going. A better first step might be this one. Both of these are by the originators of the concept, Raussendorf and Briegel, and their collaborator Browne (we'll call them RBB). They sometimes call cluster state computing the "one-way quantum computer" and abbreviate it as QCc, a notation we'll adopt. Even if you follow little of the text and none of the mathematics, checking out their diagrams in those papers might be helpful, since I have none on this blog. There are many papers on QCc, including how to do fault-tolerant QCc; I have read only a few, and won't go into details here.

Okay, my totally inept attempt to explain a little about it, in layman's terms:

If you know how to build and program a classical computer, how to design circuits, you can use that knowledge with the "standard" (circuit-based) model of quantum computation. Mathematical physicists often deal more abstractly in the actual Hamiltonians involved, especially when they want to directly simulate another quantum system, rather than run what you and I think of as an "algorithm". But you can stick with the circuit model pretty comfortably for most purposes, and that's how I've done my work on e.g. how to do integeer arithmetic on a quantum computer. But there's a third way: cluster state computing.

If the circuit model is C or assembly language for a quantum computer, then QCc is Prolog. In QCc, you don't so much tell the computer what to do as you make statements about conditions the state of the computer fulfills.

Cluster state computation is "build a huge entangled state, then selectively measure some of the connections, and magically the state transforms to the result you're looking for". That's an egregious simplification, but it's the basic idea. It has been heralded, with good reason, as the biggest theoretical revolution in quantum computing in recent years.

I think the theorists are attracted by totally new paradigm (which is a wonderful new way to think - computation carried out strictly by measurement!). It is also supposed to open up entirely new avenues of thought and new ways to "program" a quantum computer. But let's stick to one particular path - how to map the circuits we know to QCc.

For QCc, you start with a set of physical qubits that are in a 2-D grid (logically or physically) and can connect to their Manhattan neighbors. You initialize them, then perform some local operations that entangle small groups into a specific state called the cluster state. You then probabilistically connect those small groups together to make larger groups, retrying until it works (it's probabilistic, but we know when it works and when it doesn't, so we can just keep retrying until it does). Eventually, your entire machine is in one VERY large entangled state. The work up to this point is independent of the computation (circuit or algorithm) you're going to execute - you don't need to know anything but how big a cluster state to build.

Now back up for a second. Those circuits we're talking about (for some examples, see my arithmetic page (which is out of date these days, but anyway...)) are drawn using horizontal lines and vertical line segments connecting some of those lines in particular patterns. Each line represents a qubit, and the vertical line segments are gates being executed on the connected qubits. Time flows left to right. The physical resources you need are the vertical axis (the number of lines) and the time you need is the horizontal axis. (It's also worth mentioning, if you're delving into the literature, that a circuit is often called a "network". This is network in the sense that you create a netlist when doing circuit design (VLSI or PCB layout), not network in the Internet sense. There is research (and even products already) in the quantum long-distance network sense, but that's not what we're talking about here.)

To turn a circuit into a cluster state computation, we are going to unroll the computation and lay it out flat on a large cluster state. The physically-laid out cluster state will look much like the complete circuit diagram, instantiated all at once. To start with, our cluster state is a featureless 2-D grid. The derivation of the rules for mapping a circuit to it is difficult, but their application is straightforward once you understand them. First, you cut out a number of the qubits, creating holes in the grid. This cutting is done by measuring those qubits along the z axis (recall that a single qubit state can be thought of as a point anywhere on the unit sphere - a unit vector - and that measuring the qubit along a particular axis forces the qubit into a state aligned along that axis in either the positive or negative direction).

At this point, we have a structure that is partially adapted to our planned circuit, but we haven't yet applied any of the gates. A "gate" in QCc is nothing but the measurement of a particular pattern of nearby qubits along a specific set of axes (that's why this is also sometimes referred to as "measurement-based computing"). The choice of which qubits to measure and along which axes will determine what gate is effectively executed.

So now we have a plan - we know, roughly, what measurements we are going to perform on which qubits and how that will get us where we want to go. Next question: in what order do we apply those measurements? Ah, that's where the magic of QCc really shines. You might intuitively think that we more or less follow the circuit, starting from the left, applying the measurements to effect the gates in more or less the order they appear in the circuit. Nope!

Some of the possible quantum gates fall into what is known as the Clifford group. This includes the control-NOT (CNOT) gate and a few single-qubit rotations such as NOT and Hadamard. It does not include the CCNOT (control-control NOT, or Toffoli) gate. All of the gates in your circuit that are in the Clifford group can be executed at the same time! That is, if your circuit consists of only Clifford group gates, the execution of your entire circuit takes one time step, regardless of the apparent dependencies among gates! This is one of the most exciting features of cluster state computing. We have just traded space for time in a way that should make any parallel-computing guru green with envy.

Ah, but there's a catch: the non-Clifford-group gates. We need the Toffoli gate to run addition, and there are non-Clifford-group gates in the quantum Fourier transform, as well. How do those work? Well, it turns out that the choice of which measurements to make (the choice of measurement axis, not which qubit to measure) depends on the results of previous measurements. It turns out that they become dependent in a way that has some relationship to the original circuit, but is not identical. For both the QFT and addition, the number of timesteps winds up being N for an N-bit computation. To quote RBB, "the temporal axis is converted into an additional spatial axis. The temporal axis in a QCc computation emerges anew."

For a Vedral-Barenco-Ekert (VBE) carry-ripple adder, QCc requires about 100x as many qubits as does the direct circuit implementation. However, it might be faster, depending on the relative difficulty of preparing the cluster state and making single-qubit measurements for the QCc versus the cost of Toffoli gates for the circuit implementation. This is a technology-dependent question.

Moreover, the cluster states are HUGE, requiring an entangled state that is on the order of the total number of GATES, not qubits, you would have in the circuit version of the problem. This is not practical, so you have to figure out how to buffer the state you need on a rolling basis with limited physical resources. This is understood, though I'm not familiar with the details, so that will have to wait for another time.

The theorists believe that QCc opens up new paths to finding quantum algorithms. So far, though, what is best understood is how to map the known circuits to QCc, and there, as we have seen, QCc's advantages are somewhat muted.

This brings us back to where we started - the Lim et al. proposal to implement a distributed cluster-state computer. But this posting has already gotten long, and I'm not through digesting the Lim paper yet, so it will also have to wait for another time.

Important theoretical advance? Heck, yeah. Faster path to real implementations? I'm not sure, but personally I kind of doubt it.

Of course, I hope to be part of the team that proves myself either right or wrong in short order :-).