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, check_node_list=False, check_edge_list=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. The nodes should typically be compatible with the requested lattice shape parameters and coordinate system, incompatible nodes are accepted unless you set check_node_list=True. If not specified, calculated from m, fabric_only, nice_coordinates, offset_lists and offset_index and coordinates per the topology description below.

  • edge_list (iterable (optional, default None)) – Iterable of edges in the graph. Edges must be 2-tuples of the nodes specified in node_list, or calculated from m, fabric_only, nice_coordinates, offset_lists and offset_index and coordinates per the topology description below; incompatible edges are ignored unless you set check_edge_list=True. If not specified, all edges compatible with the node_list and topology description are included.

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

  • check_node_list (bool (optional, default False)) – If True, the node_list elements are checked for compatibility with the graph topology and node labeling conventions, an error is thrown if any node is incompatible or duplicates exist. In other words, only node lists that specify subgraphs of the default (full yield) graph are permitted. An exception is allowed if check_edge_list=False, in which case any node in edge_list is treated as valid.

  • check_edge_list (bool (optional, default False)) – If True, the edge_list elements are checked for compatibility with the graph topology and node labeling conventions, an error is thrown if any edge is incompatible or duplicates exist. In other words, only edge_lists that specify subgraphs of the default (full yield) graph are permitted.

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, h)\)

  • 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)]    
{'linear_index': 4, 'pegasus_index': (0, 0, 4, 0)}