More Leaf Bloqs

[mpharrigan]

One of the fundamental principles of qualtran (and programming languages in general) is composing basic operations to make composite operations that expresses a more complex behavior. Users can call Bloq.decompose_bloq() to turn a bloq into its composite parts. Bloq-authors can override Bloq.build_composite_bloq to define a bloq in terms of its decomposition.

Above, I snuck in the terms "basic operations" and "[more] complex behavior". Very often, the 'direction' of decomposition is clear: usually our subbloqs operate on fewer qubits, correspond to fewer (quantum) clock cycles to execute on a reasonable target architecture, or are more general-purpose and appear in more than one decomposition.

As we get closer to the bottom of the decomposition hierarchy, uncertainty about the target architecture can cause problems when writing a decomposition. Do we need to compile our And bloq to T or do we have a CCZ factory and we should keep them as toffolis? When compiling a toffoli to T gates, do we want to minimize depth or minimize qubits? Questions like this come up throughout the stack (i.e. what sort of adder do I want to use); but these issues become much more acute at the bottom of the stack.

There's clearly a bit of artistry here: but in a compiling/resource estimation paper: if you're swapping out e.g. different adders that goes into the "compiling" part, but if you're switching your Toffolis, that goes in the resource estimation part. I propose

1. Making more bloqs "leaf" bloqs that raise DecomposeTypeError if you try to decompose them. Specifically: I want to remove decompositions from Toffoli, And, TwoBitCSwap and most $\le 2$ qubit gates. These gates should be defined by their tensors/name rather than a decomposition.
2. Make sure the resource estimation framework can handle different "architecture" decision. For example: the default gate counts will have to return counts for all leaf bloqs. The cost model should handle multiplying the toffoli count by 4 or 7 when using a T factory. Helper functions should be in place
3. The constructions for e.g. using 4 T gates to do an And gate are really useful! These should be kept. Maybe on bespoke methods like decompose_to_t() etc

[mpharrigan]

@tanujkhattar see the above plan for what I was discussing today