The 128-qubit Rainier chip: II. graph embedding

In the previous post I introduced the concept of an allowed edge set in hardware, and presented the edge set we chose for our current processor designs. I mentioned that a reduction in edges reduces the capability of the processor. In this post I will explain why this is and how it affects the performance of the system.

To begin, note that in the design we’re building, it is useful to refer to the physical qubits as vertices V and physical couplers as edges E in a graph G. Call G=(V,E) the hardware graph. The hardware graphs for 8, 32 and 128-qubit systems were explicitly shown in the previous post, although in principle many other types of hardware graph (say for example the one we used for the 28-qubit Leda or 16-qubit Cerberus chips) are feasible. Internally here we call graphs formed of tiling the plane with K_{44} blocks Chimera graphs.

Assume a hardware graph G has been defined. For the following example, we’ll use the 32-qubit version for simplicity. Here it is for reference:

We now want to use this hardware graph for solving problems. Assume that we wish to use the chip to run a quantum adiabatic algorithm to solve for the global minimum of

{\cal E}(s_1, ..., s_{32})=\sum_{j=1}^{32} h_j s_j + \sum_{i<j=1}^{32} J_{ij} s_i s_j

ie, a fully connected (all J_{ij} non-zero) graph on 32 variables. Can we do this? The answer is no. To see why, assign to this problem a graph G_p=(V_p, E_p), with vertices V_p identified with variables and edges E_p drawn whenever a non-zero J_{ij} is required. For this example, this graph is the fully connected (all J_{ij} non-zero) graph on 32 vertices. Call G_p the problem graph.

A problem graph can be solved natively in the hardware if G_p can be embedded in the hardware graph G. A graph embedding is in general a one to many map between vertices and edges in G_p to vertices and edges in G. In the example above, G_p cannot be embedded in G, as they have the same number of vertices, while G_p is fully connected and G is not.

Let’s try another problem graph. Let’s say we want to solve for the global minimum of

{\cal E}(s_1, ..., s_N)=\sum_{j=1}^N h_j s_j + \sum_{i,j \in E_p}^N J_{ij} s_i s_j

where N and the problem edge set E_p are arbitrary. What can we say about whether or not we can embed the problem graph into a hardware graph? Here are some things that we know:

  1. You can always embed a fully connected graph on N variables into a Chimera graph with N^2 variables.
  2. You can never embed a problem graph that has either more vertices or more edges than a hardware graph.
  3. Any instance that is in the middle needs to be determined by solving what is in general a hard problem in its own right, that is does G_p embed in G. In practice if you wanted to operate in this regime, you’d probably have a fast heuristic embedder to see if a problem natively embeds.

Based on these observations, there are three obvious ways these chips can be operated.

  1. Use the chip as a solver for complete graphs, where the algorithm calling the chip has a hard-coded embedding scheme for any problem edge set. This option has the advantage that it is the most flexible for inclusion in the master algorithm (no restrictions on problem edge set), and there is no runtime cost for embedding. Its key disadvantage is that the number of variables of problems you can solve in this mode is upper bounded by roughly the square root of the number of qubits in hardware, which is a significant cost with the current chips & their low qubit count.
  2. Use the chip as a solver for problem graphs that exactly match the hardware graph by making this a hard constraint in the master algorithm. In other words, as an algorithm designer you are constrained to only pose problems to the hardware that have problem graphs that exactly match the hardware graph. This has the advantage of having trivial hard-coded embedding and maximally using the resources of the hardware. Its key disadvantage is a severe loss of flexibility in algorithms design possibilities.
  3. Use the chip for arbitrary problem sizes by running an embedding heuristic each time a possibly embeddable graph is generated by the master algorithm. This has the advantage of a significant gain in flexibility for algorithm designers. The main disadvantage is the increased runtime burden of having to compute embeddings on the fly.

My own strong preference is for #2 above. The loss of flexibility in algorithms design is a big problem, but we’ve been able to find ways to build algorithms respecting fixed hardware graphs already so I think that the advantages of #2 carry the day, at least in the short term.

So how does embedding work in practice? I will defer delving too deeply into the technical details here, leaving this to this publication. Here is a picture from that paper. The problem graph G_p is on the left, and a simple hardware graph G (not the one we use) is on the right. This is an example of a successful embedding.

One very interesting subject that Vicky’s paper discusses is that the embedding details actually affect the runtime of the quantum adiabatic algorithm for solving the problem, not just whether the problem can be natively solved. In other words, two different embeddings which are both completely valid can have vastly differing adiabatic runtimes. The reason for this is that the runtime is a function of the minimum gap between ground and first excited states, and the matrix element between them. Both of these are functions of the actual embedding and embedding parameters used. In fact, it is likely that different embedding strategies could change the asymptotic scaling of quantum adiabatic algorithms. As far as I know, no-one is currently investigating this aspect of the scaling of these algorithms–this is a feature of operation in a regime where the AQC does not natively support full inter-qubit connection (ie. any real machine).

To finish this introduction, note that the 128-qubit Rainier chip can embed two complete graphs of size K_{16} and K_{12} as shown here:

Here the blue and red circles are couplers, the black lines are qubits (a 4×4 array of 8-qubit unit cells), the yellow circles are individual qubit biases (the h_j). The dashed lines show regions where fully connected graphs can be embedded. If an algorithm designer wanted to use this chip in mode #1 above (a complete graph solver), you’d architect the system to feed this chip 16 and/or 12 variable problems. This illustrates the significant hit using the chips as complete solvers gives. You go from having 128 variables to 16. This is the primary reason why I think using this scale of system as a fully connected graph solver is not the best idea.

5 thoughts on “The 128-qubit Rainier chip: II. graph embedding

  1. i see why now 2K qubits is where operating at number 1 start to take off. you would have K 256 and K 192.

    so 2 at first, then when qubits increase you can use 2 and 1.

    when does 3 become interesting / worth it?

  2. JP, I think 3 becomes necessary when you can’t do 1 and 2: you may not have enough qubits to do 1, and the particular problem that you’re trying to solve may be getting hurt too much when directly using the hardware graph, so then 2 doesn’t work either.

  3. Pingback: Sparse coding on D-Wave hardware: things that don’t work | Hack The Multiverse

  4. Here: http://dwave.wordpress.com/2013/04/17/sparse-coding-on-d-wave-hardware-things-that-dont-work/ you say the 128 qubit chip can fully embed 17 variables and the 512 qubit chip 33. I’m trying to reconcile that with the “k 256 at 2048 qubits” comment by JP above.

    I guess I’d like to see a plot of fully embed-able variables against the number of qubits for the current 4×4 qubit tiling and any other topology you are considering (8×8, etc.).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s