pygsti.baseobjs.qubitgraph

Defines the QubitGraph class and supporting functions

Module Contents

Classes

QubitGraph

A directed or undirected graph data structure used to represent geometrical layouts of qubits or qubit gates.

class pygsti.baseobjs.qubitgraph.QubitGraph(qubit_labels, initial_connectivity=None, initial_edges=None, directed=True, direction_names=None)

Bases: pygsti.baseobjs.nicelyserializable.NicelySerializable

A directed or undirected graph data structure used to represent geometrical layouts of qubits or qubit gates.

Qubits are nodes in the graph (and can be labeled), and edges represent the ability to perform one or more types of gates between qubits (equivalent, usually, to geometrical proximity).

Parameters
  • qubit_labels (list) – A list of string or integer labels of the qubits. The length of this list equals the number of qubits (nodes) in the graph.

  • initial_connectivity (numpy.ndarray, optional) – A (nqubits, nqubits) boolean or integer array giving the initial connectivity of the graph. If an integer array, then 0 indicates no edge and positive integers indicate present edges in the “direction” given by the positive integer. For example 1 may corresond to “left” and 2 to “right”. Names must be associated with these directions using direction_names. If a boolean array, if there’s an edge from qubit i to j then initial_connectivity[i,j]=True (integer indices of qubit labels are given by their position in qubit_labels). When directed=False, only the upper triangle is used.

  • initial_edges (list) – A list of (qubit_label1, qubit_label2) 2-tuples or (qubit_label1, qubit_label2, direction) 3-tuples specifying which edges are initially present. direction can either be a positive integer, similar to those used in initial_connectivity (in which case direction_names must be specified) or a string labeling the direction, e.g. “left”.

  • directed (bool, optional) – Whether the graph is directed or undirected. Directions can only be used when directed=True.

  • direction_names (iterable, optional) – A list (or tuple, etc) of string-valued direction names such as “left” or “right”. These strings label the directions referenced by index in either initial_connectivity or initial_edges, and this argument is required whenever such indices are used.

classmethod common_graph(cls, num_qubits=0, geometry='line', directed=True, qubit_labels=None, all_directions=False)

Create a QubitGraph that is one of several standard types of graphs.

Parameters
  • num_qubits (int, optional) – The number of qubits (nodes in the graph).

  • geometry ({"line","ring","grid","torus"}) – The type of graph. What these correspond to should be self-evident.

  • directed (bool, optional) – Whether the graph is directed or undirected.

  • qubit_labels (iterable, optional) – The labels for the qubits. Must be of length num_qubits. If None, then the integers from 0 to num_qubits-1 are used.

  • all_directions (bool, optional) – Whether to include edges with all directions. Typically it only makes sense to set this to True when directed=True also.

Returns

QubitGraph

map_qubit_labels(self, mapper)

Creates a new QubitGraph whose qubit (node) labels are updated according to the mapping function mapper.

Parameters

mapper (dict or function) – A dictionary whose keys are the existing self.node_names values and whose value are the new labels, or a function which takes a single (existing qubit-label) argument and returns a new qubit label.

Returns

QubitProcessorSpec

_to_nice_serialization(self)
classmethod _from_nice_serialization(cls, state)
copy(self)

Make a copy of this graph.

Returns

QubitGraph

_refresh_dists_and_predecessors(self)
__getitem__(self, key)
__setitem__(self, key, val)
__len__(self)
property node_names(self)

All the node labels of this graph.

These correpond to integer indices where appropriate, e.g. for :method:`shortest_path_distance_matrix`.

Returns

tuple

add_edges(self, edges)

Add edges (list of tuple pairs) to graph.

Parameters

edges (list) – A list of (qubit_label1, qubit_label2) 2-tuples.

Returns

None

add_edge(self, node1, node2, direction=None)

Add an edge between the qubits labeled by node1 and node2.

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

  • direction (str or int, optional) – Either a direction name or a direction indicex

Returns

None

remove_edge(self, node1, node2)

Add an edge between the qubits labeled by node1 and node2.

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

None

edges(self, double_for_undirected=False, include_directions=False)

Get a list of the edges in this graph as 2-tuples of node/qubit labels).

When undirected, the index of the 2-tuple’s first label will always be less than its second unless double_for_undirected == True, in which case both directed edges are included. The edges are sorted (by label index) in ascending order.

Parameters
  • double_for_undirected (bool, optional) – Whether, for the case of an undirected graph, two 2-tuples, giving both edge directions, should be included in the returned list.

  • include_directions (bool, optional) – Whether to include direction labels. If True and directions are present, a list of (node1, node2, direction_name) 3-tuples is returned instead of the usual (node1, node2) 2-tuples.

Returns

list

radius(self, base_nodes, max_hops)

Find all the nodes reachable in max_hops from any node in base_nodes.

Get a (sorted) array of node labels that can be reached from traversing at most max_hops edges starting from a node (vertex) in base_nodes.

Parameters
  • base_nodes (iterable) – A list of node/qubit labels giving the possible starting locations.

  • max_hops (int) – The maximum number of hops (see above).

Returns

list – A list of the node labels reachable from base_nodes in at most max_hops edge traversals.

connected_combos(self, possible_nodes, size)

Computes the number of different connected subsets of possible_nodes containing size nodes.

Parameters
  • possible_nodes (list) – A list of node (qubit) labels.

  • size (int) – The size of the connected subsets being sought (counted).

Returns

int

_indices_connected(self, i, j)

Whether nodes indexed by i and j are directly connected

is_connected(self, node1, node2)

Is node1 connected to node2 (does there exist a path of any length between them?)

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

bool

has_edge(self, edge)

Is edge an edge in this graph.

Note that if this graph is undirected, either node order in edge will return True.

Parameters

edge (tuple) – (node1,node2) tuple specifying the edge.

Returns

bool

is_directly_connected(self, node1, node2)

Is node1 directly connected to node2 (does there exist an edge between them?)

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

bool

_is_connected_subgraph(self, node_indices)

Whether the nodes indexed by the elements of node_indices form a connected subgraph.

is_connected_graph(self)

Computes whether this graph is connected (there exist paths between every pair of nodes).

Returns

bool

is_connected_subgraph(self, nodes)

Do a give set of nodes form a connected subgraph?

That is, does there exist a path from every node in nodes to every other node in nodes using only the edges between the nodes in nodes.

Parameters

nodes (list) – A list of node (qubit) labels.

Returns

bool

_brute_get_all_connected_sets(self, n)

Computes all connected sets of n qubits using a brute-force approach.

Note that for a large device with this will be often be an unreasonably large number of sets of qubits, and so the run-time of this method will be unreasonable.

Parameters

n (int) – The number of qubits within each set.

Returns

list – All sets of n connected qubits.

find_all_connected_sets(self)

Finds all subgraphs (connected sets of vertices) up to the full graph size.

Graph edges are treated as undirected.

Returns

dict – A dictionary with integer keys. The value of key k is a list of all the subgraphs of length k. A subgraph is given as a tuple of sorted vertex labels.

shortest_path(self, node1, node2)

Get the shortest path between two nodes (qubits).

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

list – A list of the node labels to traverse.

shortest_path_edges(self, node1, node2)

Like :method:`shortest_path`, but returns a list of (nodeA,nodeB) tuples.

These tuples define a path from node1 to node2, so the first tuple’s nodeA == node1 and the final tuple’s nodeB == node2.

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

list – A list of the edges (2-tuples of node labels) to traverse.

shortest_path_intersect(self, node1, node2, nodes_to_intersect)

Check whether the shortest path between node1 and node2 contains any of the nodes in nodes_to_intersect.

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

  • nodes_to_intersect (list) – A list of node labels.

Returns

bool – True if the shortest path intersects any node in nodeToIntersect.

shortest_path_distance(self, node1, node2)

Get the distance of the shortest path between node1 and node2.

Parameters
  • node1 (str or int) – Qubit (node) label.

  • node2 (str or int) – Qubit (node) label.

Returns

int

shortest_path_distance_matrix(self)

Returns a matrix of shortest path distances.

This matrix is indexed by the integer-index of each node label (as specified to __init__). The list of index-ordered node labels is given by :method:`node_names`.

Returns

numpy.ndarray – A boolean array of shape (n,n) where n is the number of nodes in this graph.

shortest_path_predecessor_matrix(self)

Returns a matrix of predecessors used to construct the shortest path between two nodes.

This matrix is indexed by the integer-index of each node label (as specified to __init__). The list of index-ordered node labels is given by :method:`node_names`.

Returns

numpy.ndarray – A boolean array of shape (n,n) where n is the number of nodes in this graph.

subgraph(self, nodes_to_keep, reset_nodes=False)

Return a graph that includes only nodes_to_keep and the edges between them.

Parameters
  • nodes_to_keep (list) – A list of node labels defining the subgraph to return.

  • reset_nodes (bool, optional) – If True, nodes of returned subgraph are relabelled to be the integers starting at 0 (in 1-1 correspondence with the ordering in nodes_to_keep).

Returns

QubitGraph

resolve_relative_nodelabel(self, relative_nodelabel, target_labels)

Resolve a “relative nodelabel” into an actual node in this graph.

Relative node labels can use “@” to index elements of target_labels and can contain “+<dir>” directives to move along directions defined in this graph.

Parameters
  • relative_nodelabel (int or str) – An absolute or relative node-label. For example: 0, “@0”, “@0+right”, “@1+left+up”

  • target_labels (list or tuple) – A list of (absolute) node labels present in this graph that may be referred to using the “@” syntax within relative_nodelabel.

Returns

int or str

move_in_directions(self, start_node, directions)

The node you end up on after moving in directions from start_node.

Parameters
  • start_node (str or int) – Qubit (node) label.

  • directions (iterable) – A sequence of direction names.

Returns

str or int or None – The ending node label or None if the directions were invalid.

move_in_direction(self, start_node, direction)

Get the node that is one step in direction of start_node.

Parameters
  • start_node (int or str) – the starting point (a node label of this graph)

  • direction (str or int) – the name of a direction or its index within this graphs .directions member.

Returns

str or int or None – the node in the given direction or None if there is no node in that direction (e.g. if you reach the end of a chain).

__str__(self)

Return str(self).