pygsti.baseobjs.qubitgraph
¶
Defines the QubitGraph class and supporting functions
Module Contents¶
Classes¶
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).