cotengra.pathfinders.path_simulated_annealing

Functions

compute_contracted_info(legsa, legsb, appearances, ...)

Compute the contracted legs, cost and size of a pair of legs.

linspace_generator(start, stop, num[, log])

Generate a sequence of num evenly spaced floats between start

_describe_tree(tree[, info])

_score_tree(scorer, tree[, target_size, ...])

_slice_tree_basic(tree, current_target_size, rng[, ...])

_slice_tree_reslice(tree, current_target_size, rng)

_slice_tree_drift(tree, current_target_size, rng)

simulated_anneal_tree(tree[, tfinal, tstart, tsteps, ...])

Perform a simulated annealing optimization of this contraction

_do_anneal(tree, *args, **kwargs)

parallel_temper_tree(tree_or_trees[, tfinal, tstart, ...])

Perform parallel tempering optimization of a contraction tree. This

Module Contents

cotengra.pathfinders.path_simulated_annealing.compute_contracted_info(legsa, legsb, appearances, size_dict)[source]

Compute the contracted legs, cost and size of a pair of legs.

Parameters:

  • legsa (dict[str, int]) – The legs of the first tensor.

  • legsb (dict[str, int]) – The legs of the second tensor.

  • appearances (dict[str, int]) – The total number of appearances of each index in the contraction.

  • size_dict (dict[str, int]) – The size of each index.

Returns:

  • legsab (dict[str, int]) – The contracted legs.

  • cost (int) – The cost of the contraction.

  • size (int) – The size of the resulting tensor.

cotengra.pathfinders.path_simulated_annealing.linspace_generator(start, stop, num, log=False)[source]

Generate a sequence of num evenly spaced floats between start and stop.

Parameters:

  • start (float) – The starting value.

  • stop (float) – The stopping value.

  • num (int) – The number of values to generate.

  • log (bool, optional) – Whether to generate the sequence in log space.

Yields:

float

cotengra.pathfinders.path_simulated_annealing._describe_tree(tree, info='concise')[source]
cotengra.pathfinders.path_simulated_annealing._score_tree(scorer, tree, target_size=None, coeff_size_penalty=1.0)[source]
cotengra.pathfinders.path_simulated_annealing._slice_tree_basic(tree, current_target_size, rng, unslice=1)[source]
cotengra.pathfinders.path_simulated_annealing._slice_tree_reslice(tree, current_target_size, rng)[source]
cotengra.pathfinders.path_simulated_annealing._slice_tree_drift(tree, current_target_size, rng)[source]
cotengra.pathfinders.path_simulated_annealing.simulated_anneal_tree(tree, tfinal=0.05, tstart=2, tsteps=50, numiter=50, minimize=None, target_size=None, target_size_initial=None, slice_mode='basic', seed=None, progbar=False, inplace=False)[source]

Perform a simulated annealing optimization of this contraction tree, based on “Multi-Tensor Contraction for XEB Verification of Quantum Circuits” by Gleb Kalachev, Pavel Panteleev, Man-Hong Yung (arXiv:2108.05665), and the “treesa” implementation in OMEinsumContractionOrders.jl by Jin-Guo Liu and Pan Zhang.

Parameters:

  • tfinal (float, optional) – The final temperature.

  • tstart (float, optional) – The starting temperature.

  • tsteps (int, optional) – The number of temperature steps.

  • numiter (int, optional) – The number of sweeps at each temperature step.

  • minimize ({'flops', 'combo', 'write', 'size', ...}, optional) – The objective function to minimize.

  • target_size (int, optional) – The target size to slice the contraction to. A schedule is used to reach this only at the final temperature step.

  • target_size_initial (int, optional) – The initial target size to use in the slicing schedule. If None, then the current size is used.

  • slice_mode ({'basic', 'reslice', 'drift', int}, optional) – The mode for slicing the contraction tree within each annealing iteration. ‘basic’ always unslices a random index and then slices to the target size. ‘reslice’ unslices all indices and then slices to the target size. ‘drift’ unslices a random index with probability 1/4 and slices to the target size with probability 3/4. It is therefore not guaranteed to reach the target size, but may be more explorative for long annealing schedules.

  • seed (int, optional) – A random seed.

  • progbar (bool, optional) – Whether to show live progress.

  • inplace (bool, optional) – Whether to perform the optimization inplace.

Return type:

ContractionTree

cotengra.pathfinders.path_simulated_annealing._do_anneal(tree, *args, **kwargs)[source]
cotengra.pathfinders.path_simulated_annealing.parallel_temper_tree(tree_or_trees, tfinal=0.01, tstart=1, tsteps=50, num_trees=8, numiter=50, minimize=None, target_size=None, target_size_initial=None, slice_mode='drift', parallel_slice_mode='temperature', swappiness=1.0, coeff_size_penalty=1.0, max_time=None, seed=None, parallel='auto', info=None, progbar=False, inplace=False)[source]

Perform parallel tempering optimization of a contraction tree. This anneals num_trees different trees at a range of temperatures between tfinal and tstart. After each step, trees are exchanged between neighboring temperatures according to the Metropolis-Hastings criterion.

Parameters:

  • tree_or_trees (ContractionTree or sequence of ContractionTree) – The tree or trees to optimize. If less than num_trees are given, then they will be cycled. If more than num_trees are given, then the length will override num_trees.

  • tfinal (float, optional) – The final temperature.

  • tstart (float, optional) – The starting temperature.

  • tsteps (int, optional) – The number of temperature steps, each with numiter iterations. After each step, trees are exchanged between neighboring temperatures.

  • num_trees (int, optional) – The number of trees and thus temperatures to optimize in parallel.

  • numiter (int, optional) – The number of iterations to perform at each step. The total number of sweeps (per parallel temperature) is numiter * tsteps.

  • minimize ({'flops', 'combo', 'write', 'size', ...}, optional) – The objective function to minimize.

  • target_size (int, optional) – The target size of the contraction.

  • slice_mode ({'basic', 'reslice', 'drift'}, optional) – The mode for slicing the contraction tree within each annealing iteration.

  • parallel_slice_mode ({'temperature', 'time', 'constant'}, optional) – The parallel mode for slicing the contraction tree. If ‘temperature’, then the target size decreases with temperature. If ‘time’, then the target size decreases with time. If ‘constant’, then the target size is constant.

  • seed (int, optional) – A random seed.

  • parallel ('auto', False, True, int, or distributed.Client) – Whether to parallelize the search.

  • progbar (bool, optional) – Whether to show live progress.

  • inplace (bool, optional) – Whether to perform the optimization inplace.