pygsti.layouts.prefixtable

Defines the PrefixTable class.

Module Contents

Classes

PrefixTable

An ordered list ("table") of circuits to evaluate, where common prefixes can be cached.

PrefixTableJacobian

An ordered list ("table") of circuits to evaluate, where common prefixes can be cached.

TreeNode

Parameters

RootNode

Class for representing a root node for a tree, along with the corresponding metadata

ChildNode

Class for representing a child node for a tree, along with the corresponding metadata

Tree

Container class for storing a tree structure (technically a forest, as there

Functions

tree_partition_kundu_misra(tree, max_weight[, ...])

Algorithm for optimal minimum cardinality k-partition of tree (a partition

class pygsti.layouts.prefixtable.PrefixTable(circuits_to_evaluate, max_cache_size)

Bases: object

An ordered list (“table”) of circuits to evaluate, where common prefixes can be cached.

Creates a “prefix table” for evaluating a set of circuits.

The table is list of tuples, where each element contains instructions for evaluating a particular operation sequence:

(iDest, iStart, tuple_of_following_items, iCache)

Means that circuit[iDest] = cached_circuit[iStart] + tuple_of_following_items, and that the resulting state should be stored at cache index iCache (for later reference as an iStart value). The ordering of the returned list specifies the evaluation order.

iDest is always in the range [0,len(circuits_to_evaluate)-1], and indexes the result computed for each of the circuits.

Parameters

circuit_parameter_sensitivities :

A map between the circuits in circuits_to_evaluate and the indices of the model parameters to which these circuits depend.

Returns

tuple

A tuple of (table_contents, cache_size) where table_contents is a list of tuples as given above and cache_size is the total size of the state cache used to hold intermediate results.

sorted_circuits_to_evaluate
orig_indices
circuit_reps
contents
cache_size = '0'
circuits_evaluated
num_state_propagations()

Return the number of state propagation operations (excluding the action of POVM effects) required for the evaluation strategy given by this PrefixTable.

num_state_propagations_by_circuit()

Return the number of state propagation operations per-circuit (excluding the action of POVM effects) required for the evaluation strategy given by this PrefixTable, returned as a dictionary with keys corresponding to circuits and values corresponding to the number of state propagations required for that circuit.

num_state_propagations_by_circuit_no_caching()

Return the number of state propagation operations per-circuit (excluding the action of POVM effects) required for an evaluation strategy without caching, returned as a dictionary with keys corresponding to circuits and values corresponding to the number of state propagations required for that circuit.

num_state_propagations_no_caching()

Return the total number of state propagation operations (excluding the action of POVM effects) required for an evaluation strategy without caching.

find_splitting_new(max_sub_table_size=None, num_sub_tables=None, initial_cost_metric='size', rebalancing_cost_metric='propagations', imbalance_threshold=1.2, minimum_improvement_threshold=0.1, verbosity=0)

Find a partition of the indices of this table to define a set of sub-tables with the desire properties.

This is done in order to reduce the maximum size of any tree (useful for limiting memory consumption or for using multiple cores). Must specify either max_sub_tree_size or num_sub_trees.

Parameters
max_sub_table_sizeint, optional

The maximum size (i.e. list length) of each sub-table. If the original table is smaller than this size, no splitting will occur. If None, then there is no limit.

num_sub_tablesint, optional

The maximum size (i.e. list length) of each sub-table. If the original table is smaller than this size, no splitting will occur.

imbalance_thresholdfloat, optional (default 1.2)

This number serves as a tolerance parameter for a final load balancing refinement to the splitting. The value coresponds to a threshold value of the ratio of the heaviest to the lightest subtree such that ratios below this value are considered sufficiently balanced and processing stops.

minimum_improvement_thresholdfloat, optional (default .1)

A parameter for the final load balancing refinement process that sets a minimum balance improvement (improvement to the ratio of the sizes of two subtrees) such that a rebalancing step is considered worth performing (even if it would otherwise bring the imbalance parameter described above in imbalance_threshold below the target value) .

verbosityint, optional (default 0)

How much detail to send to stdout.

Returns
list

A list of sets of elements to place in sub-tables.

find_splitting(max_sub_table_size=None, num_sub_tables=None, cost_metric='size', verbosity=0)

Find a partition of the indices of this table to define a set of sub-tables with the desire properties.

This is done in order to reduce the maximum size of any tree (useful for limiting memory consumption or for using multiple cores). Must specify either max_sub_tree_size or num_sub_trees.

Parameters
max_sub_table_sizeint, optional

The maximum size (i.e. list length) of each sub-table. If the original table is smaller than this size, no splitting will occur. If None, then there is no limit.

num_sub_tablesint, optional

The maximum size (i.e. list length) of each sub-table. If the original table is smaller than this size, no splitting will occur.

verbosityint, optional

How much detail to send to stdout.

Returns
list

A list of sets of elements to place in sub-tables.

class pygsti.layouts.prefixtable.PrefixTableJacobian(circuits_to_evaluate, max_cache_size, parameter_circuit_dependencies=None)

Bases: object

An ordered list (“table”) of circuits to evaluate, where common prefixes can be cached. Specialized for purposes of jacobian calculations.

Creates a “prefix table” for evaluating a set of circuits.

The table is list of tuples, where each element contains instructions for evaluating a particular operation sequence:

(iDest, iStart, tuple_of_following_items, iCache)

Means that circuit[iDest] = cached_circuit[iStart] + tuple_of_following_items, and that the resulting state should be stored at cache index iCache (for later reference as an iStart value). The ordering of the returned list specifies the evaluation order.

iDest is always in the range [0,len(circuits_to_evaluate)-1], and indexes the result computed for each of the circuits.

Parameters

circuit_parameter_sensitivities :

A map between the circuits in circuits_to_evaluate and the indices of the model parameters to which these circuits depend.

Returns

tuple

A tuple of (table_contents, cache_size) where table_contents is a list of tuples as given above and cache_size is the total size of the state cache used to hold intermediate results.

unique_parameter_circuit_dependency_classes
contents_by_parameter
cache_size_by_parameter
parameter_circuit_dependencies = '[]'
class pygsti.layouts.prefixtable.TreeNode(value, children=None, orig_indices=None)

Parameters

valueany

The value to be stored in the node.

childrenlist, optional (default is None)

A list of child nodes. If None, initializes an empty list.

orig_indiceslist, optional (default is None)

A list of original indices. If None, initializes an empty list.

value
children = '[]'
orig_indices = '[]'
add_child(child_node)

Add a child node to the current node.

Parameters
child_nodeTreeNode

The child node to be added.

remove_child(child_node)

Remove a child node from the current node.

Parameters
child_nodeTreeNode

The child node to be removed.

get_child_node(value)

Get the child node associated with the input value. If that node is not present, return None.

Parameters
valueany

The value to search for in the child nodes.

Returns
TreeNode or None

The child node with the specified value, or None if not found.

add_orig_index(value)

Add an original index to the node.

Parameters
valueint

The original index to be added.

traverse()

Traverse the tree in pre-order and return a list of node values.

Returns
list

A list of node values in pre-order traversal.

get_descendants()

Get all descendant node values of the current node in pre-order traversal.

Returns
list

A list of descendant node values.

total_orig_indices()

Calculate the total number of orig_indices values for this node and all of its descendants.

print_tree(level=0, prefix='')

Print the tree structure starting from the current node.

Parameters
levelint, optional (default 0)

The current level in the tree.

prefixstr, optional (default “”)

The prefix for the current level.

class pygsti.layouts.prefixtable.RootNode(value, cost=0, tree=None, children=None, orig_indices=None)

Bases: TreeNode

Class for representing a root node for a tree, along with the corresponding metadata specific to root nodes.

Initialize a RootNode with a value, optional cost, optional tree, optional children, and optional original indices.

Parameters

valueany

The value to be stored in the node.

costint, optional (default is 0)

The initial cost associated with the root node.

treeTree, optional (default is None)

The tree to which this root node belongs.

childrenlist, optional (default is None)

A list of child nodes. If None, initializes an empty list.

orig_indiceslist, optional (default is None)

A list of original indices. If None, initializes an empty list.

cost = '0'
tree = 'None'
class pygsti.layouts.prefixtable.ChildNode(value, parent=None, children=None, orig_indices=None)

Bases: TreeNode

Class for representing a child node for a tree, along with the corresponding metadata specific to child nodes.

Parameters

valueany

The value to be stored in the node.

parentTreeNode, optional (default is None)

The parent node.

childrenlist, optional (default is None)

A list of child nodes. If None, initializes an empty list.

orig_indiceslist, optional (default is None)

A list of original indices. If None, initializes an empty list.

parent = 'None'
get_ancestors()

Get all ancestor nodes of the current node up to the root node.

Returns
list

A list of ancestor nodes.

calculate_promotion_cost()

Calculate the cost of promoting this child node to a root node. This corresponds to the sum of the cost of this node’s current root, plus the total number of ancestors (less the root).

promote_to_root()

Promote this child node to a root node, updating the tree structure accordingly.

get_root()

Get the root node of the current node.

Returns
RootNode

The root node of the current node.

class pygsti.layouts.prefixtable.Tree(roots=None)

Container class for storing a tree structure (technically a forest, as there can be multiple roots).

Parameters

roots: list of RootNode, optional (default None)

List of roots for this tree structure.

roots = '[]'
root_set
get_root_node(value)

Get the root node associated with the input value. If that node is not present, return None.

Parameters
valueany

The value to search for in the root nodes.

Returns
RootNode or None

The root node with the specified value, or None if not found.

add_root(root_node)

Add a root node to the tree.

Parameters
root_nodeRootNode

The root node to be added.

remove_root(root_node)

Remove a root node from the tree.

Parameters
root_nodeRootNode

The root node to be removed.

total_orig_indices()

Calculate the total number of original indices for all root nodes and their descendants.

traverse()

Traverse the entire tree in pre-order and return a list of node values.

Returns
list

A list of node values in pre-order traversal.

count_nodes()

Count the total number of nodes in the tree.

print_tree()

Print the entire tree structure.

calculate_cost()

Calculate the total cost of the tree, including root costs and promotion costs for child nodes. See RootNode and ChildNode.

to_networkx_graph()

Convert the tree to a NetworkX directed graph with node and edge attributes.

Returns
networkx.DiGraph

The NetworkX directed graph representation of the tree.

pygsti.layouts.prefixtable.tree_partition_kundu_misra(tree, max_weight, weight_key='cost', test_leaves=True, return_levels_and_weights=False, precomp_levels=None, precomp_weights=None)

Algorithm for optimal minimum cardinality k-partition of tree (a partition of a tree into cluster of size at most k) based on a slightly less sophisticated implementation of the algorithm from “A Linear Tree Partitioning Algorithm” by Kundu and Misra (SIAM J. Comput. Vol. 6, No. 1, March 1977). Less sophisiticated because the strictly linear time implementation uses linear-time median estimation routine, while this implementation uses sorting (n log(n)-time), in practice it is likely that the highly-optimized C implementation of sorting would beat an uglier python implementation of median finding for most problem instances of interest anyhow.

Parameters

treenetworkx.DiGraph

An input graph representing the directed tree to perform partitioning on.

max_weightint

Maximum node weight allowed for each partition.

weight_keystr, optional (default ‘cost’)

An optional string denoting the node attribute label to use for node weights in partitioning.

test_leavesbool, optional (default True)

When True an initial test is performed to ensure that the weight of the leaves are all less than the maximum weight. Only turn off if you know for certain this is true.

return_levels_and_weightsbool, optional (default False)

If True return the constructed tree level structure (the lists of nodes partitioned by distance from the root) and subtree weights.

precomp_levelslist of sets, optional (default None)

A list where each set contains nodes that are equidistant from the root.

precomp_weightsdict, optional (default None)

A dictionary where keys are nodes and values are the total weights of the subtrees rooted at those nodes.

Returns

partitioned_treenetworkx.DiGraph

A new DiGraph corresponding to the partitioned tree. I.e. a copy of the original tree with the requisite edge cuts performed.

cut_edgeslist of tuples

A list of the parent-child node pairs whose edges were cut in partitioning the tree.