Branch and Bound

Branch and bound algorithm for optimal contraction of a tensor network.

class mrmustard.path.branch_and_bound.Graph(*args, backend=None, **kwargs)

Power pack for nx.DiGraph with additional attributes and methods.

Parameters:

• solution (tuple[Edge, ...]) – The sequence of edges contracted to obtain this graph.

• costs (tuple[int, ...]) – The costs of contracting each edge in the current solution.

property cost: int

Returns the total cost of the graph.

component(n)

Returns the GraphComponent associated with a node.

Parameters:

n – The node index.

Return type:

GraphComponent

components()

Yields the GraphComponents associated with the nodes.

Return type:

Generator[GraphComponent, None, None]

optimize_fock_shapes(components, verbose=False)

Optimizes the Fock shapes of the components in this circuit. It starts by matching the existing connected wires and keeps the smaller shape, then it enforces the BSgate symmetry (conservation of photon number) to further reduce the shapes across the circuit. This operation acts in place.

Parameters:

• components (list[CircuitComponent])

• verbose (bool)

class mrmustard.path.branch_and_bound.GraphComponent(ansatz, wires, shape, name='', cost=0)

A lightweight “CircuitComponent” without the actual ansatz. Basically a wrapper around Wires, so that it can emulate components in a circuit. It exposes the ansatz, wires, shape, name and cost of obtaining the component from previous contractions.

Parameters:

• ansatz (str) – The name of the ansatz of the component.

• wires (Wires) – The wires of the component.

• shape (list[int]) – The fock shape of the component.

• name (str) – The name of the component.

• cost (int) – The cost of obtaining this component.

classmethod from_circuitcomponent(c)

Creates a GraphComponent from a CircuitComponent.

Parameters:

c (CircuitComponent) – A CircuitComponent.

contraction_cost(other)

Returns the computational cost in approx FLOPS for contracting this component with another one.

Three cases are possible:

1. If both components are in Fock ansatz the cost is the product of the values along both shapes, counting only once the shape of the contracted indices. E.g. a tensor with shape (20,30,40) contracts its 1,2 indices with the 0,1 indices of a tensor with shape (30,40,50,60). The cost is 20 x 30 x 40 x 50 x 60 = 72_000_000 (note 30,40 were counted only once).

2. If the ansatze are a mix of Bargmann and Fock, we add the cost of converting the Bargmann to Fock, which is the product of the shape of the Bargmann component.

3. If both are in Bargmann ansatz, the contraction can be a simple a Gaussian integral which scales like the cube of the number of contracted indices, i.e. ~ just 8 in the example above.

Parameters:

other (GraphComponent) – GraphComponent

Returns:

contraction cost in approx FLOPS

Return type:

int

mrmustard.path.branch_and_bound.assign_costs(graph, debug=0)

Assigns to each edge in the graph the cost of contracting the two nodes it connects.

Parameters:

• graph (Graph) – A graph.

• debug (int) – Whether to print debug information

Return type:

None

mrmustard.path.branch_and_bound.children(graph, cost_bound)

Returns a set of graphs obtained by contracting each edge. Only graphs with a cost below cost_bound are returned. Two nodes are contracted by removing the edge between them and merging the two nodes into a single node. The shape of the new node is the union of the shapes of the two nodes without the wires that were contracted (this is all handled by the wires).

Parameters:

• graph (Graph) – A graph.

• cost_bound (int) – The maximum cost of the children.

Returns:

The set of graphs obtained by contracting each edge.

Return type:

set[Graph]

mrmustard.path.branch_and_bound.contract(graph, edge, debug=0)

Contracts an edge in a graph and returns the contracted graph. Makes a copy of the original graph.

Parameters:

• graph (Graph) – A graph.

• edge (tuple[int, int]) – An edge to contract.

• debug (int) – Whether to print debug information.

Returns:

A new graph with the contracted edge.

Return type:

Graph

mrmustard.path.branch_and_bound.grandchildren(graph, cost_bound)

A set of grandchildren constructed from each child’s children. Only grandchildren with a cost below cost_bound are returned. Note that children without further children are included, so with a single call to this function we get all the descendants up to the grandchildren level including leaf nodes whether they are children or grandchildren.

Parameters:

• graph (Graph) – A graph.

• cost_bound (int) – The maximum cost of the grandchildren

Returns:

The set of grandchildren below the cost bound.

Return type:

set[Graph]

mrmustard.path.branch_and_bound.heuristic(graph, code, verbose)

Simplifies the graph by contracting all pairs of nodes that match the given pattern.

Parameters:

• graph (Graph) – A graph.

• code (str) – A pattern indicating the type of nodes to contract.

• verbose (bool) – Whether to print the progress.

Return type:

Graph

mrmustard.path.branch_and_bound.optimal_contraction(graph, n_init, heuristics, verbose)

Finds the optimal path to contract a graph.

Parameters:

• graph (Graph) – The graph to contract.

• n_init (int) – The number of random contractions to find an initial cost upper bound.

• heuristics (tuple[str, ...]) – A sequence of patterns to reduce in order.

• verbose (bool) – Whether to print the progress.

Returns:

The optimally contracted graph with associated cost and solution

Return type:

Graph

mrmustard.path.branch_and_bound.optimize_fock_shapes(graph, iteration, verbose)

Iteratively optimizes the Fock shapes of the components in the graph.

Parameters:

• graph (Graph) – The graph to optimize.

• iteration (int) – The iteration number.

• verbose (bool) – Whether to print the progress.

Return type:

Graph

mrmustard.path.branch_and_bound.parse_components(components)

Parses a list of CircuitComponents into a Graph.

Each node in the graph corresponds to a GraphComponent and an edge between two nodes indicates that the GraphComponents are connected in the circuit. Whether they are connected by one wire or by many, in the graph they will have a single edge between them.

Parameters:

components (list[CircuitComponent]) – A list of CircuitComponents.

Return type:

Graph

mrmustard.path.branch_and_bound.random_solution(graph)

Returns a random solution to contract a given graph.

Parameters:

graph (Graph) – The initial graph.

Returns:

The contracted graph

Return type:

Graph

mrmustard.path.branch_and_bound.validate_components(components)

Raises an error if the components will not contract correctly.

Parameters:

components (list[CircuitComponent]) – A list of CircuitComponents.

Return type:

None

code/path/branch_and_bound

 

Download Python script

 

Download Notebook

 

View on GitHub