Support for global quantum phase

[ss2165]

There is no phase tracking, and no phase gate in the standard set. It is not a natural fit because it is a non-dataflow global operation. Almost like metadata?

Phase only matters in certain kinds of circuit composition (e.g. quantum control).

[aborgna-q]

We should be keeping the pytket global phase on the circuit metadata. Do you have a failing example? https://github.com/CQCL/tket2/blob/main/tket2%2Fsrc%2Fserialize%2Fpytket%2Fencoder.rs#L57-L62

(There's currently no way for rewrites to modify the phase)

[ss2165]

This isn't a bug report about pytket compatibility, and is independent of pytket. What I mean is that a rewrite may only be valid up to phase if you keep track of the phase update, which we don't do.

[lmondada]

After many discussions, I have "boiled down" the choices to the following flowchart:

flowchart LR
    BB{Dynamic phase?}
    BB -->|No| Metadata
    BB -->|Yes| A
    A{Preserve phase by default?} -->|No| B{HUGR encodes whether phase was preserved?}
    A -->|Yes| dce{DCE phase preserving?}
    dce -->|No| static(Single AddPhase op)
    dce -->|Yes| edge{Order edges ok?}
    edge -->|Yes| static
    edge -->|No| lincont(Linear phase type)
    B -->|Yes| mult{Opt-specific phase representation or value-to-metadata hack?}
    mult -->|ok| Metadata(Metadata)
    mult -->|nope| X(unknown)
    B -->|No| dce

Let me explain each of the concepts in this diagram:

Decisions

Dynamic phase: Do we support programs in which contributions to the global phase is specified by a unknown runtime value? Most likely Yes at the guppy level (e.g. to turn a function that takes float arguments into a quantum controlled operation). At optimisation level tbd

Preserve phase by default: Whether HUGR transformations can be assumed to preserve global phase by default. This would mean every HUGR transformation logic must explicitly opt-out if it cannot guarantee phase preservation. There is concensus that this is a bad idea

HUGR encodes whether phase was preserved: Given a HUGR, can I tell from the data that a non-phase preserving pass has been applied? This would be a nice to have for correctness, but together with non-phase-preservation-by-default, this is a high bar to clear: we must detect simultaneously detect that a HUGR transformation has occurred while simultaneously allowing arbitrary transformations.

Opt-specific phase representation: We adopt two different ways to encode global phase: a guppy extension that represents phase as a runtime value and a metadata-based approach for optimisation. This creates duplication, but is arguably the best of both worlds:

• guppy has unlimited expressivity
• most optimisation routines do not need to care about the linear phase type, and can simply manipulate metadata. Optimisation over operations on the linear phase type would have to be written separately, as well as passes transforming metadata to linear phase type and reciprocally, constant-folding the phase type into metadata.

value-to-metadata hack: It might be possible to lower the linear phase type entirely to metadata, by adding an op taking an angle as input and no output that "loads" the phase into metadata. Presumably would involve introducing symbolic phases, ASTs of phases... sounds bad (and keeping both in parallel doesn't seem so bad to me)

DCE phase-preserving: whether dead code elimination should preserve global phase. Choosing not to preserve global phase during DCE makes the design of AddPhase easier, but we might not be willing to give up on DCE for phase-preserving optimisation, given how ubiquitous it is.

Order edges: Do we want a solution based on order edges? Order edges are a simple way to register global phase contributions from ops and ensuring ops are not dead-code eliminated, but their use is questionable because:

• what we are "ordering" are contributions to global phase, which by definition commute with each other,
• they muddle static analysis by not distinguishing between different causal orders (e.g. say there is an order edge from op1 to op2 that was added because of global phase; when we strip phase information, how do we know that the ops are no longer causally dependent?)
• there are vague plans/hopes to eventually move away from using order edges in HUGR.

These drawbacks might be effectively mitigated if we established a convention that phase ops may only have order edges that connect them to the input/output nodes of their DFG region.

Implementation choices

Metadata: by far the simplest from a HUGR transformation and optimisation perspective. Does not support dynamic phase. Ops have a metadata field indicating their contribution to global phase. If this metadata is absent on any op, we can infer that this region of the HUGR (and all its ancestors) has not a well-defined phase. HUGR transformation that wish to perserve phase must take care to set this metadata field correctly; any other transformation can simply ignore it.

EDGE CASE TO THINK ABOUT: if a HUGR transformation does not add any node, but is not phase-preserving, how do we detect that? If all ops had metadata information before the transformation, there will not be any op without it afterwards...

See also this earlier proposal.

Single AddPhase op: Add a single AddPhase op that takes an angle as input and has no output. HUGR transformations may insert any number of these, as required. If we wish to perform phase-preserving dead code elimination, order edges must be inserted to avoid elimination of AddPhase ops. Note that it cannot be inferred from a HUGR whether a non-phase-preserving transformation has been applied.

Linear phase type: A fancier version of the AddPhase op. Same expressivity but more type safe. On top of taking an angle as input, the op must produce a linear phase type as output. This type must be passed on to the region output, or explicitly discarded (in which case the op producing it is a no-op: the global phase is NOT applied). Additional bookkeeping ops would be required to make this work. For instance (taking as is a proposal from @acl-cqc, thank you!):

• AddPhase: Angle -> PhaseContext
• Join: PhaseContext, PhaseContext -> PhaseContext
• TempLocal: PhaseContext -> ()
• Poison: () -> PhaseContext

In this proposal, a global phase can be added to the computation using AddPhase. All such contributions must be joined together using Join, until the final PhaseContext can be passed to the region output node. If a computation is not reachable (or should not be executed for another reason), the PhaseContext can be discarded using TempLocal. Finally, if any part of the computation has an unknown global phase, it can produce a PhaseContext using Poison, which will propagate through Joins and result in an unknown phase for the region as a whole. Note that it cannot be inferred from a HUGR whether a non-phase-preserving transformation has been applied.

[cqc-alec]

I think there is a path to the AddPhase solution (called "Order edges" above) that does not require order edges, if we just say that DCE is a non-phase-preserving pass.

[lmondada]

we just say that DCE is a non-phase-preserving pass

Very good point. Will add.

EDIT: updated the flowchart and renamed "Order edges" solution to "Single AddPhase op".