app.processing.optimize.algos

Optimization algorithms.

Following task has to be solved:

Given:

• set of nodes, each node has:

  • amount of required reusable ancilla qubits

  • amount of required dirty ancilla qubits

  • amount of returned reusable ancilla qubits

  • amount of returned dirty ancilla qubits

  • amount of returned ‘reusable if uncomputed, else dirty’ qubits

• set of connections between these nodes

Wanted:

• set of ancilla edges that reuse dirty/reusable ancillas

  • topological sort has to be possible after!

• dict that tells whether to uncompute a given node

• optimize on minimal amount of required qubits (that could not be satisfied via ancilla connections)

Note on ancilla qubit types:

• returned reusable qubits can be used as required dirty and required reusable

• returned dirty qubits can be used as required dirty

• returned uncomputable can be used as:

  • required dirty in any case

  • required dirty and required reusable if uncompute is executed

Module Contents

class app.processing.optimize.algos.OptimizationAlgo(graph: app.processing.graph.ProgramGraph)

Abstract parent of optimization algorithms.

• Specify the interface.

• Handle special user-required ancilla nodes.

Parameters:

graph (app.processing.graph.ProgramGraph)

class app.processing.optimize.algos.NoPred(graph: app.processing.graph.ProgramGraph)

Implementation of the ‘no predecessor’ idea with dummy selection.

Other Algorithms should inherit from this and only override the heuristic methods.

Basic idea:

1. Create a set of all nodes that have no predecessor

2. Keep track of the resources the already fixed nodes have: dirty, uncomputable, reusable

   • all initialized to zero

3. While the set is not empty:

   1. Choose one node from this set.

      • how to choose is the hard part that has to be done via heuristic

   2. Remove all edges from this node.

   3. Check for new nodes without predecessors, add them to the set.

   4. Try to satisfy the requirements of the current node via the available resources.

      • Add ancilla edges here

      • Possibility to uncompute in previous nodes

      • Needs heuristic: What nodes to uncompute first?

   5. Add the resources this node gives to the available resources.

4. (Optional): Raise error if there are nodes that were not processed.

   • This would mean that the graph has no topological sort.

Parameters:

• ancilla_edges – ancilla edges to return

• uncomputes – whether to uncompute a node

• reusable – list of nodes that have reusable qubits.

• dirty – list of nodes that have dirty qubits.

• uncomputable – list of nodes that have uncomputable qubits.

• nopred – list of nodes without predecessors (ProcessedProgramNode is not hashable).

• need_dirty – current requirement of dirty qubits

• need_reusable – current requirement of reusable qubits

• graph (app.processing.graph.ProgramGraph)

remove_node(node: app.processing.graph.ProcessedProgramNode) → list[app.processing.graph.ProcessedProgramNode]

(Virtually) remove node from graph.

Don’t remove the node itself, but all connections outgoing from him. It is not possible that the node is incoming edges (invariant of this algo).

Parameters:

node (app.processing.graph.ProcessedProgramNode) – The node to remove.

Returns:

Nodes that have no predecessor because of this.

Return type:

list[app.processing.graph.ProcessedProgramNode]

pop_nopred() → app.processing.graph.ProcessedProgramNode

Remove and return the next nopred node.

This is a dummy implementation! Overwrite this method is sub-classes.

Returns:

Chosen node.

Return type:

app.processing.graph.ProcessedProgramNode

pop_uncomputable() → app.processing.graph.ProcessedProgramNode

Remove and return the next node to be uncomputed.

Chooses the node with the fewest uncomputable qubits, i.e. the cheapest to uncompute.

Returns:

Chosen node.

Return type:

app.processing.graph.ProcessedProgramNode

satisfy_dirty_qubit_requirement() → None

Try to satisfy requirement for dirty qubits.

Add ancilla edges from previous nodes for this case. Use the qubits in the order: dirty -> uncomputable -> reusable

Return type:

None

satisfy_reusable_qubit_requirement() → None

Try to satisfy requirement for dirty qubits.

Add ancilla edges from previous nodes for this case. Try to satisfy with reusable qubits, uncompute nodes if that is not enough.

Return type:

None

compute() → tuple[list[app.processing.graph.AncillaConnection], dict[app.processing.graph.ProgramNode, bool]]

Execute the optimization.

Returns:

Added ancilla edges and dict specifying whether to uncomute nodes.

Return type:

tuple[list[app.processing.graph.AncillaConnection], dict[app.processing.graph.ProgramNode, bool]]

class app.processing.optimize.algos.NoPredCheckNeedDiffScore(graph: app.processing.graph.ProgramGraph)

NoPred variant with the check-need strategy + diff score.

Check need strategy: All possible nodes are divided in one of two categories:

1. satisfied: the requirement of that node are satisfied by the available resources

2. unsatisfied: the requirement of that node can’t be satisfied

We always prefer nodes that are in the first category.

Diff score: Sort the nodes based on provided resources - required resources.

Parameters:

• weight_reusable – weight of reusable qubits in diff-score

• weight_uncomp – weight of uncomputable qubits in diff-score

• weight_dirty – weight of dirty qubits in diff-score

• graph (app.processing.graph.ProgramGraph)

pop_nopred() → app.processing.graph.ProcessedProgramNode

Remove and return the next nopred node.

This is a dummy implementation! Overwrite this method is sub-classes.

Returns:

Chosen node.

Return type:

app.processing.graph.ProcessedProgramNode