dwave_networkx.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.

Parameters:
  • m (int) – 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)) are not added.
  • edge_list (iterable, optional (default None)) – Iterable of edges in the graph. If None, edges are generated as described below. 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 below. If the coordinates parameter is True, a linear_index, which is an integer, is used.
  • coordinates (bool, optional (default False)) – If True, node labels are 4-tuple Pegasus indices. Ignored if the nice_coordinates parameter is True.
  • offset_lists (pair of lists, optional (default None)) – Directly controls the offsets. Each list in the pair must have length 12 and contain even ints. If offset_lists is not None, the offsets_index parameter must be None.
  • offsets_index (int, optional (default None)) – A number between 0 and 7, inclusive, that selects a preconfigured set of topological parameters. If both the offsets_index and offset_lists parameters are None, the offsets_index parameters is set to zero. At least one of these two parameters must be None.
  • fabric_only (bool, optional (default True)) – The Pegasus graph, by definition, has some disconnected components. If True, the generator only constructs nodes from the largest component. If False, the full disconnected graph is constructed. Ignored if the edge_lists parameter is not None or nice_coordinates is True
  • nice_coordinates (bool, optional (default False)) – If the offsets_index parameter is 0, the graph uses a “nicer” coordinate system, 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.
Returns:

G – A Pegasus lattice for size parameter m.

Return type:

NetworkX Graph

The maximum degree of this graph is 15. The number of nodes depends on multiple parameters; for example,

  • pegasus_graph(1): zero nodes
  • pegasus_graph(m, fabric_only=False): \(24m(m-1)\) nodes
  • pegasus_graph(m, fabric_only=True): \(24m(m-1)-8(m-1)\) nodes
  • pegasus_graph(m, nice_coordinates=True): \(24(m-1)^2\) nodes

Counting formulas for edges have a complicated dependency on parameter settings. Some example upper bounds are:

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

Note that the formulas above are valid for default offset parameters.

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

  • vertical nodes: \((i, j, 0, k)\) with \(0 <= k < 2\)
  • horizontal nodes: \((i, j, 1, k)\) with \(0 <= k < 2\)

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

  • external: \((i, j, u, k)\) ~ \((i+u, j+1-u, u, k)\)
  • internal: \((i, j, 0, k)\) ~ \((i, j, 1, k)\)
  • odd: \((i, j, u, 0)\) ~ \((i, j, u, 1)\)

Given two lists of offsets, \(S0\) and \(S1\), of length \(L0\) and \(L1\), where both lengths and values must be divisible by 2, the minor—a Pegasus lattice—is constructed 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, ‘pegasus_graph()’, is specialized for the minor constructed by prelattice and offset parameters \(L0 = L1 = 12\) and \(N0 = N1 = 12m\).

The Pegasus index of a node in a Pegasus lattice, \((u, w, k, z)\), can be interpreted as:

  • \(u\): qubit orientation (0 = vertical, 1 = horizontal)
  • \(w\): orthogonal major offset
  • \(k\): orthogonal minor offset
  • \(z\): parallel offset

Edges in the minor have the form

  • external: \((u, w, k, z)\) ~ \((u, w, k, z+1)\)
  • internal: \((0, w0, k0, z0)\) ~ \((1, w1, k1, z1)\)
  • odd: \((u, w, 2k, z)\) ~ \((u, w, 2k+1, z)\)

where internal edges only exist when

  1. w1 = z0 + (1 if k1 < S0[k0] else 0)
  2. 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

Examples

>>> G = dnx.pegasus_graph(2, nice_coordinates=True)
>>> G.nodes(data=True)[(0, 0, 0, 0, 0)]    # doctest: +SKIP
{'linear_index': 4, 'pegasus_index': (0, 0, 4, 0)}