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

pygsti.layouts.prefixtable

Module Contents

Classes

Functions

Parameters

Returns

Parameters

Returns

Parameters

Returns

Parameters

Returns

Parameters

Parameters

Parameters

Parameters

Returns

Parameters

Returns

Returns

Parameters

Parameters

Parameters

Returns

Returns

Parameters

Parameters

Returns

Parameters

Parameters

Returns

Returns

Parameters

Returns

`pygsti.layouts.prefixtable`