app.processing.optimize.algos
=============================

.. py:module:: app.processing.optimize.algos

.. autoapi-nested-parse::

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

.. py:class:: OptimizationAlgo(graph: app.processing.graph.ProgramGraph)



   Abstract parent of optimization algorithms.

   - Specify the interface.
   - Handle special user-required ancilla nodes.


.. py:class:: 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.

   :param ancilla_edges: ancilla edges to return
   :param uncomputes: whether to uncompute a node
   :param reusable: list of nodes that have reusable qubits.
   :param dirty: list of nodes that have dirty qubits.
   :param uncomputable: list of nodes that have uncomputable qubits.
   :param nopred: list of nodes without predecessors (ProcessedProgramNode is not hashable).
   :param need_dirty: current requirement of dirty qubits
   :param need_reusable: current requirement of reusable qubits


   .. py:method:: 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).

      :param node: The node to remove.
      :return: Nodes that have no predecessor because of this.



   .. py:method:: pop_nopred() -> app.processing.graph.ProcessedProgramNode

      Remove and return the next nopred node.

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

      :return: Chosen node.



   .. py:method:: 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.

      :return: Chosen node.



   .. py:method:: 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



   .. py:method:: 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.



   .. py:method:: compute() -> tuple[list[app.processing.graph.AncillaConnection], dict[app.processing.graph.ProgramNode, bool]]

      Execute the optimization.

      :return: Added ancilla edges and dict specifying whether to uncomute nodes.



.. py:class:: 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.

   :param weight_reusable: weight of reusable qubits in diff-score
   :param weight_uncomp: weight of uncomputable qubits in diff-score
   :param weight_dirty: weight of dirty qubits in diff-score


   .. py:method:: pop_nopred() -> app.processing.graph.ProcessedProgramNode

      Remove and return the next nopred node.

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

      :return: Chosen node.