pass: Extract static circuit

[doug-q]

We need a pass that fallibly extracts a static circuit from a Hugr. If there is no static circuit, because of gate execution inside Conditional, CFG, TailLoop etc, the pass fails.

With #1476 and #1603 we have dataflow analysis.

Define a "qubit history" lattice, a list of gates. join(x,y) is TOP if x != y and x otherwise. A gate propagates the input histories with itself appended.

If all qubit-consuming ops have well defined(i.e. non-TOP non-BOTTOM) histories on their input qubits then those qubits form a static circuit.

From the examples below, note:

• The angles of a gate do not affect the history
• For multi-qubit gates we need to track which other qubits are gated, and the order matters. For some gates the order doesn't matter. Initially we can conservatively treat all gates as non-commutative.
• Each qalloc should be assigned an identity which is used to track how qubits are ordered in multi-qubit gates
• The gates are defined in downstream extensions, so for this to live here in hugr we need to define an interface so that we can operate on arbitrary extension ops. If this is too hard we can move to tket2.

Examples

q0 = qalloc() # 0
q1 = qalloc() # 1
cx(q0,q1) #2
rx(q0, rand()) #3
print(measure(q0),measure(q1)) #4

In the above example:

• Assign all qallocs a unique id: let's say #0 has id 0 and #1 has id 1
• After #0 the qubit history of q0 is []
• After #1 the qubit history of q1 is []
• After #2 the qubit history of q0 is [cx(0,1)], the qubit history of q1 is [cx(0,1)]
• After #3 the qubit history of q0 is [cx(0,1),rx]
• #4 consumes both q0 and q1, both of which have well-defined histories, so this is a static circuit

q0 = qalloc() # 0
q1 = qalloc() # 1
if rand():
  cx(q0,q1) #2
rx(q0, rand()) #3
print(measure(q0),measure(q1)) #4

In this example, the input history of q0 in #3 is join([],[cx(0,1)]), i.e. TOP. Thus q0 in #4 does not have a well-defined history so this is not a static circuit.

q0 = qalloc() # 0
q1 = qalloc() # 1
cx(q0,q1) #2
if rand():
  rx(q0, 1) #3.0
else:
  rx(q0, 2) #3.1
print(measure(q0),measure(q1)) #4

In this example, the input history of q0 in #4 is join([cx(0,1), rx],[cx(0,1), rx]), i.e. [cx(0,1), rx]. Thus q0 in #4 does \have a well-defined history so this is a static circuit(!).

[cqc-alec]

Just to check my understanding, in the last example, if #3.1 had a different angle would it still count as a static circuit?

[doug-q]

Just to check my understanding, in the last example, if #3.1 had a different angle would it still count as a static circuit?

It was supposed to have a different angle! Thanks, I've edited. Angles do not form part of the history, so yes , it is still a static circuit.

A justification for angles not forming part of the history: We want to use this by extracting a static circuit, optimising it, then replacing the original circuit with the optimised circuit. The optimised circuit can be inserted in a DFG "at the end"(more precise definition needed) of the program, where the angles are guaranteed to have been computed. I think angles shouldn't depend on measurements, which is not captured above. I think this is a detail which can be worked out.

One could define join so that angles are tracked, but such that only the angles goes to TOP when they do not match in otherwise matching histories.

[acl-cqc]

I think the challenge of transforming a circuit into a flat representation is independent of the challenge of optimizing/scheduling/etc. that flattened representation, and if we keep it that way, we can be quite flexible in what transformations we deploy towards the first.

In particular, if you are doing DF analysis on a lattice of "circuit history" (!), that'd give you sufficient info to transform the conditional of two identical gate sets, into a single set of gates with classical inputs computed by the conditional. But there might be other easier ways to get there (e.g. repeatedly just pull a common gate out of the bottom of the conditional).

[acl-cqc]

In this example, the input history of q0 in #4 is join([cx(0,1), rx],[cx(0,1), rx]), i.e. [cx(0,1), rx]. Thus q0 in #4 does \have a well-defined history so this is a static circuit(!).

The input history of q0 is join([cx(0,1), rx], [cx(0,2), rx]). At least you will need the result of the join to record the conditionals that lead to picking 1 vs 2.