DRAFT: feat: Prototype dataflow analysis for static circuit extraction

[doug-q]

Based on #1603.

Includes an rough inliner and call graph.

See the new snapshots for current capabilities.

[doug-q]

I think the 125 files changed is because I merged main. Annoying.

[doug-q]

Ok... so my overall thought is this is not really a dataflow analysis. What you want is the part of dataflow analysis that does "join" at the exit of every conditional, and indeed on every control-flow merge; and possibly for TailLoops; but the things you want to join are circuits, not any kind of value that's per-qubit. (Because that join/merge logic currently only exists in dataflow analysis, "give a man a hammer and everything looks like a nail", but the other bits of the dataflow framework are really not helping here, and it'd be better to do something else - another datalog, probably, with just the bit you need. If you really want analysis like "only these cases are reachable" we should determine that using DF and then simplify the Hugr with this knowledge.)

I disagree. What is your criteria for being a dataflow analysis? Mine is: A well defined join and transfer function.

I have pushed and the test cases are now working. I had to add handling for "arguments of public functions are top". I do not claim that my interpret_leaf_op is understandable yet! (but it seems mostly correct)

[acl-cqc]

What is your criteria for being a dataflow analysis?

An abstract value per wire (perhaps only a subset of wires, i.e. only those of type Qubit). Here you want an abstract value per circuit (per sibling subgraph).

I think the analysis framework you want is:

• client provides a type of values V. Yes, these will need join.
• client provides a function interpret_dfg(parent: Node, child_results: Map<Node, V>) -> V which is called with a map whose keys are the container nodes in the dfg.
  • For "nested DFG" nodes, the value in the map is the result of calling interpret_dfg, so we could rely on interpret_dfg to recursively call itself, but I think this just makes the rules more complicated
  • The framework handles Conditional nodes by recursing on each child Case, and then joining the resulting V's
  • The framework handles CFG nodes similarly by merging at CF joins and copying at control-flow splits. (There is some value in doing Tag/Value/Sum analysis on wires here but I think that could be done separately as a first step)
  • The framework handles TailLoop's...somehow (I mean, any quantum op in a tailloop will report "no static circuit" unless it's a never-iterates loop, right?)

The use-case here then instantiates V == Circuit == Hugr<RootNode=DFG>, and interpret_dfg inlines the map (replacing each container node keyed in the Map with the DFG value from the Map)

I think this is necessary to handle qalloc/qfree which are not represented in the outputs (where you suggest "this might require Dense Analysis")

[acl-cqc]

Ok, so qalloc/qfree could be represented in the containing region's outputs mentioning (in their gating_nodes) 2-qubit ops with the ancillae. But then you've got only a nodeindex, not a description of the op (and the history of the ancilla), so if you had a conditional which in each arm did qalloc, ..., qfree with (case 1) the same, or (case 2) different ops, to combine the ancilla with the conditional's input-and-output qubit, we still need to do some graph traversal (not here) to identify or distinguish the two arms?

[acl-cqc]

Data flows along wires, hence dataflow analysis attaches values (modelling data) to those wires. In order to split a circuit into per-wire "Vertical slices" we have to break up the definitive model of a circuit (i.e. a Hugr) into some per-wire variant. Your QbHistory, with the qubit indices for each gate, is quite a detailed model (given linearity) and as such goes further than I'd anticipated.

• qalloc is currently still a problem - replace qalloc() with if p {qalloc()} else {qalloc()} and we'll fail to extract a static circuit. This is soluble by building a yet-more-detailed model of the circuit.

• qfree is harder to solve, as there is no output wire from the circuit to which to attach a value describing what was freed. I haven't got a good answer to how to deal with this. Consider fn circuit(q0) { let temp = qalloc() in if p {h(temp); cx(q0, temp); qfree(temp)} else {rz(temp); ry(temp); cx(q0, temp); qfree(temp);} }

  One thing I like about the 'rewriting' approach is that it combines analysis with transformation, and I think generalizes fairly straightforwardly to handle both of those cases. But any analysis is likely to have shortcomings, which is why I prefer an input/ready-flattened format that is agnostic to analysis technique. That doesn't rule out the analysis you have here!

[doug-q]

Data flows along wires, hence dataflow analysis attaches values (modelling data) to those wires. In order to split a circuit into per-wire "Vertical slices" we have to break up the definitive model of a circuit (i.e. a Hugr) into some per-wire variant. Your QbHistory, with the qubit indices for each gate, is quite a detailed model (given linearity) and as such goes further than I'd anticipated.

• qalloc is currently still a problem - replace qalloc() with if p {qalloc()} else {qalloc()} and we'll fail to extract a static circuit. This is soluble by building a yet-more-detailed model of the circuit.
• qfree is harder to solve, as there is no output wire from the circuit to which to attach a value describing what was freed. I haven't got a good answer to how to deal with this. Consider fn circuit(q0) { let temp = qalloc() in if p {h(temp); cx(q0, temp); qfree(temp)} else {rz(temp); ry(temp); cx(q0, temp); qfree(temp);} }

One thing I like about the 'rewriting' approach is that it combines analysis with transformation, and I think generalizes fairly straightforwardly to handle both of those cases. But any analysis is likely to have shortcomings, which is why I prefer an input/ready-flattened format that is agnostic to analysis technique. That doesn't rule out the analysis you have here!

I agree that qalloc and qfree are problematic, and that this approach only works when they are simply arranged with all qallocs at the beginning and all the qfrees at the end. I don't think this is unreasonable for extracting a static circuit, but perhaps I'm wrong. The reason I have inlining here is so that I get all the qallocs into main. The raw guppy calls functions that call call qalloc, which defeats the analysis for the same reasons as you describe above.

We are surely in agreement that we should do transformations on the hugr first to make the analysis work better.

[acl-cqc]

Yeah ok so I think the things I would disagree with are not actually in this PR - they are the architecture, what analysis/transformation goes where in the pipeline, what the intermediates exchanged look like.

That you can use dataflow analysis to extract (some) static circuits, I do not dispute :-) :-). Whether it's the best tool for the job - well that depends what else is in the toolbox, and right now the toolbox doesn't have a lot else in it and dataflow analysis is the most powerful tool in there.

We are surely in agreement that we should do transformations on the hugr first to make the analysis work better.

Generally I would follow the school of thought that analysis enables transformation, rather than the other way around...