Pytket circuit extraction

[aborgna-q]

Problem

Given a hugr containing a program definition, extract as much as possible into a pytket circuit.

• The program is a DFG container. It may not be the root of the hugr.
• The input Hugr is read-only, no further rewrites should be made.
• We may inline functions / transform cfgs into structured control flow before running the extraction, but if present in the kernel they may be wrapped as unsupported ops.

Usecases

The definition of "as much as possible" is a bit vague. We basically have two usecases here:

• Return a single pytket circuit to the user that corresponds to the top-level definition in the hugr.
  Any internal unsupported ops will be ignored even if they contained valid circuit operations somewhere in their definition.

• Extract "maximal circuit-like subgraphs" to run optimisation on.
  This would return a series of circuits plus some reference to where they come from.
  We would then return circuits for unused function or DF blocks inside CFG graphs that can be rewritten on their own, before merging them translating them back and updating the original hugr.

The first point can be seen as a special case of the second, where we ignore all non-root subcircuits.

Supported types

As the types available in a pytket circuit are limited, we are restricted in the set of hugr types we support;

• Currently implemented:
  • Bools
  • prelude.qubit
  • tket2.rotation.rotation and arithmetic.float.types.float64
• Unimplemented:
  • Tuples of any supported type. Decoded as independent wires.
  • collections.array.array of any supported type and non-parametric length. Decoded as independent wires.
  • arithmetic.int.types.int.
    Decoded into independent bools.

Any operation containing an unsupported type in its signature is itself unsupported.

Supported operations

As defined before, supported operations must only contain supported types in their signature. Furthermore, we need to know how to translate them into their pytket equivalent.

Leaf ops

For leaf operations, we hardcode the translation of some operations.

• Currently implemented:
  • Tk2Op: Most quantum operations have a direct counterpart. Some special cases add tracked qubits to the extracted circuit.
  • OpaqueTk1Op: These are wrappers created when decoding a pytket gate with no corresponding native Hugr op. These can always be decoded.
  • FloatOps / RotationOp: These get translated into sympy expressions on the operation parameters.
  • Const
• Unimplemented:
  • LogicOp/IntOp
  • ArrayOpDef
  • TupleOpDef
  • NoopDef

Other ops

Non-leaf operations each require specific routines to handle them.
There are all currently unimplemented or WIP.

• Call: Can be wrapped in a pytket CircBox and recursively encoded as long as there are no recursive calls.
  That is simple to check by keeping a call stack.
  The encoded results can optionally be cached for performance.

• Dfg: Similar to a function call, but without the recursion failure mode.

• Conditionals on boolean values: Each branch may be wrapped in a Conditional box.

When a node has a qubit in the same position in both its input and output ports we assume that it returns the same qubit.
Any output qubit not in the input forces a new element to be added to the pytket circuit's qb register.

Unsupported operations

Some operations like CFG regions, TailLoops, Conditionals on arbitrary sums, or unknown leaf ops will not be supported by the extraction. This also includes operations with non-local input connections whose origin has not been processed.

We can replace these unsupported ops with a opaque Barriers, which can carry arbitrary data and it's left untouched by circuit optimisations.

What gets encoded in the opaque data of a circuit depends on the usecase. If we are temporarily converting the hugr to optimise parts of it and re-insert them back, we only need to track some minimal sub-circuit description (nodes + boundaries).

If we are returning a standalone circuit that will be independently manipulated by the users we must encode all of the unsupported hugr subgraph in a way that can be decoded and independently re-integrated into a single hugr.
This can be done by adding a single barrier at the beginning of the circuit (on all/any inputs) containing the necessary hugrs.

The algorithm

This section gives a simple overview of the encoding algorithm.

Given a dataflow region in a hugr, we traverse its DAG in any topological order.

At each step, we track

• The set of seen qubits, with their pytket register index and last processed wire in the Hugr.
• The set of processed bit/int wires with their corresponding output ports ands corresponding pytket register bits. We may optionally trim these elements once all readers have been processed, to be able to re-use pytket bit elements.
• The set of processed float/rotation wires with their corresponding sympy expression.
• The set of processed wires with unsupported types, and partially defined connected SiblingSubgraphs of unsupported operations.
  The wire->subgraph mapping would benefit from a union-find structure since we'll need to merge subgraphs.
• The list of encoded pytket commands
• Other circuit metadata (name, global phase)

We start by initializing the listed state with the inputs to the hugr region.

For each operation, traversed in topological order,

• If it's a supported operation,
  • If it's a leaf operation,
    • Convert the operation into pytket, and add it to the list of pytket commands.
  • If it's a Conditional,
    • Recurse and extract each branch
    • Wrap each resulting list of commands into Conditional boxes.
  • If it's a Dfg or Call,
    • Recurse and extract the internal dfg
    • Wrap the resulting commands into a CircBox
• If it's an unsupported operation,
  • If it has incoming unsupported wires,
    • Find the corresponding unsupported subgraphs
    • If more than one, take the union of them
    • Add the op to the subgraph
  • If there are input/output wires with supported type, add a barrier operation on all of them indicating the corresponding subgraph input/outputs.
  • If the user is interested in all internal pytket subgraphs, and the operation is a hierarchical parent,
    • DFS-traverse its hierarchy, collecting descendant dataflow containers
    • Store them in a queue to be processed later

An auxiliary method can be defined to translate supported hugr wires into corresponding qubits/bits/parameters.

If we were asked to to return all internal pytket-like subcircuits, continue processing the queue of dataflow containers with the same algorithm.

[aborgna-q]

Addressed on #849 and subsequent PRs.