dwave_networkx.generators.pegasus_graph

pegasus_graph(m, create_using=None, node_list=None, edge_list=None, data=True, offset_lists=None, offsets_index=None, coordinates=False, fabric_only=True, nice_coordinates=False)[source]

Creates a Pegasus graph with size parameter m. The number of nodes and edges varies according to multiple parameters, for example,

pegasus_graph(1) contains zero nodes, pegasus_graph(m, fabric_only=False) contains \(24m(m-1)\) nodes, pegasus_graph(m, fabric_only=True) contains \(24m(m-1)-8m\) nodes, and pegasus_graph(m, nice_coordinates=True) contains \(24(m-1)^2\) nodes.

The maximum degree of these graph is 15, and counting formulas are more complicated for edges given most parameter settings. Upper bounds are given below,

pegasus_graph(1, fabric_only=False) has zero edges, pegasus_graph(m, fabric_only=False) has \(12*(15*(m-1)^2 + m - 3)\) edges if m > 1

Note that the above are valid with default offset parameters.

A Pegasus lattice is a graph minor of a lattice similar to Chimera, where unit tiles are completely connected. In the most generality, prelattice \(Q(N0,N1)\) contains nodes of the form

\((i, j, 0, k)\) with \(0 <= k < 2\) [vertical nodes]

and

\((i, j, 1, k)\) with \(0 <= k < 2\) [horizontal nodes]

for \(0 <= i <= N0\) and \(0 <= j < N1\); and edges of the form

\((i, j, u, k)\) ~ \((i+u, j+1-u, u, k)\) [external edges]

\((i, j, 0, k)\) ~ \((i, j, 1, k)\) [internal edges]

\((i, j, u, 0)\) ~ \((i, j, u, 1)\) [odd edges]

The minor is specified by two lists of offsets; \(S0\) and \(S1\) of length \(L0\) and \(L1\) (where \(L0\) and \(L1\), and the entries of \(S0\) and \(S1\), must be divisible by 2). From these offsets, we construct our minor, a Pegasus lattice, by contracting the complete intervals of external edges:

I(0, w, k, z) = [(L1*w + k, L0*z + S0[k] + r, 0, k % 2) for 0 <= r < L0]
I(1, w, k, z) = [(L1*z + S1[k] + r, L0*w + k, 1, k % 2) for 0 <= r < L1]

and deleting the prelattice nodes of any interval not fully contained in \(Q(N0, N1)\).

This generator is specialized to \(L0 = L1 = 12\); \(N0 = N1 = 12m\).

The notation \((u, w, k, z)\) is called the Pegasus index of a node in a Pegasus lattice. The entries can be interpreted as following,

\(u\): qubit orientation (0 = vertical, 1 = horizontal)

\(w\): orthogonal major offset

\(k\): orthogonal minor offset

\(z\): parallel offset

and the edges in the minor have the form

\((u, w, k, z)\) ~ \((u, w, k, z+1)\) [external edges]

\((0, w0, k0, z0)\) ~ \((1, w1, k1, z1)\) [internal edges, see below]

\((u, w, 2k, z)\) ~ \((u, w, 2k+1, z)\) [odd edges]

where internal edges only exist when:

w1 = z0 + (1 if k1 < S0[k0] else 0), and
z1 = w0 - (1 if k0 < S1[k1] else 0)

linear indices are computed from pegasus indices by the formula:

q = ((u * m + w) * 12 + k) * (m - 1) + z
Parameters:
  • m (int) – The size parameter for the Pegasus lattice.
  • create_using (Graph, optional (default None)) – If provided, this graph is cleared of nodes and edges and filled with the new graph. Usually used to set the type of the graph.
  • node_list (iterable, optional (default None)) – Iterable of nodes in the graph. If None, calculated from m. Note that this list is used to remove nodes, so any nodes specified not in range(24 * m * (m-1)) will not be added.
  • edge_list (iterable, optional (default None)) – Iterable of edges in the graph. If None, edges are generated as described above. The nodes in each edge must be integer-labeled in range(24 * m * (m-1)).
  • data (bool, optional (default True)) – If True, each node has a pegasus_index attribute. The attribute is a 4-tuple Pegasus index as defined above. (if coordinates = True, we set a linear_index, which is an integer)
  • coordinates (bool, optional (default False)) – If True, node labels are 4-tuple Pegasus indices. Ignored if nice_coordinates is True
  • offset_lists (pair of lists, optional (default None)) – Used to directly control the offsets, each list in the pair should have length 12, and contain even ints. If offset_lists is not None, then offsets_index must be None.
  • offsets_index (int, optional (default None)) – A number between 0 and 7 inclusive, to select a preconfigured set of topological parameters. If both offsets_index and offset_lists are None, then we set offsets_index = 0. At least one of these two parameters must be None.
  • fabric_only (bool, optional (default True)) – The Pegasus graph, by definition, will have some disconnected components. If this True, we will only construct nodes from the largest component. Otherwise, the full disconnected graph will be constructed. Ignored if edge_lists is not None or nice_coordinates is True
  • nice_coordinates (bool, optional (default False)) – In the case that offsets_index = 0, generate the graph with a nicer coordinate system which is more compatible with Chimera addressing. These coordinates are 5-tuples taking the form (t, y, x, u, k) where 0 <= x < M-1, 0 <= y < M-1, 0 <= u < 2, 0 <= k < 4 and 0 <= t < 3. For any given 0 <= t0 < 3, the subgraph of nodes with t = t0 has the structure of chimera(M-1, M-1, 4) with the addition of odd couplers. Supercedes both the fabric_only and coordinates parameters.