dwave_networkx.algorithms.elimination_ordering.pegasus_elimination_order

pegasus_elimination_order(n, coordinates=False)[source]

Provides a variable elimination order for the Pegasus graph.

The treewidth of a Pegasus graph pegasus_graph(n) is lower-bounded by \(12n-11\) and upper bounded by \(12n-4\) [bbrr] .

Simple pegasus variable elimination order rules:

  • eliminate vertical qubits, one column at a time

  • eliminate horizontal qubits in each column once their adjacent vertical qubits have been eliminated

Parameters
  • n (int) – The size parameter for the Pegasus lattice.

  • coordinates (bool, optional (default False)) – If True, the elimination order is given in terms of 4-term Pegasus coordinates, otherwise given in linear indices.

Returns

order – An elimination order that provides an upper bound on the treewidth.

Return type

list

bbrr

Boothby, K., P. Bunky, J. Raymond, A. Roy. Next-Generation Topology of D-Wave Quantum Processors. Technical Report, Februrary 2019. https://www.dwavesys.com/resources/publications?type=white