BloqInstance.i index should not be an arbitrary index and should preserve insertion ordering

[tanujkhattar]

I think it would be nice if BloqInstance.i has some semantic meaning in the context of a CompositeBloq. Some possible options are:

• i'th instance of that particular bloq in the CompositeBloq DAG (ordered based on (topological, insertion) order)
• i'th node in some topological sorting of the DAG represented by CompositeBloq

It seems like these properties break down because of

Qualtran/qualtran/_infra/composite_bloq.py

Lines 346 to 352 in 79a880b

	# We take particular care during flattening to preserve the `binst.i` of bloq instances
	# that are not flattened. We do this by initializing the bloq builder's `i` counter
	# to one greater than the existing maximum value, so all calls to `add_from` will result
	# in new, higher `binst.i` values.
	# pylint: disable=protected-access
	bb._i = max(binst.i for binst in self.bloq_instances) + 1

Is there a particular reason we chose to preserve this property where binst.i of bloqs which are not flattened is preserved? @mpharrigan

I'm particularly interested to query the following property:

• Given two nodes x and y in the binst_graph of a composite bloq, I want to know which of these two bloqs (or their parents therefore, if we have flattened a composite bloq) was inserted earlier by the user when constructing the composite bloq? i.e. I want a way to preserve insertion ordering of bloq instances and query this property efficiently given access to bloq instances and a composite bloq / binst_graph

This is useful for a PR I'm working on to provide a greedy topological sorting with a heuristic that aims to help minimize qubit allocations / deallocations and would be useful for qubit count costs (xref #1097) and translation of a composite bloq to a cirq circuit (xref comment by Anurudh #963 (comment))

[mpharrigan]

As noted, that's to support drawing circuits where you can flatten only parts of it while keeping the identity of the unmodified parts the same

[tanujkhattar]

Do the drawings specifically depend upon the value of binst.i ? Can you point me to where that happens?

[mpharrigan]

It's used in the prototype interactive drawing musical_score.js which will tween between the top-level circuit and a partially decompose&flattened one. binst.i is the "key" that d3.js uses to know which things in the original circuit correspond to which in the decomposed one

[tanujkhattar]

One way to satisfy both the requirements would be to make binst.i a tuple instead of an index; then as we decompose we can keep appending to the tuple and the property that binst1.i < binst2.i preserves insertion ordering would also be satisfied. We can cache the hash if we think this would add a performance bottleneck. WDYT ?

[mpharrigan]

I think there are ways to preserve the insertion index. An easy one would be to have the CompositeBloq._bloq_instances attribute be an ordered list. In general, I'd be happier if the insertion order was kept within the context of the container rather than on the BloqInstance itself. Another option would be to have an additional field on BloqInstance that is the insertion order. Keeping the i as an arbitrary identifier that is preserved through flattening makes conceptual sense to me.