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.
   • And Make And a leaf bloq #1346
   • Toffoli Make Toffoli a leaf bloq #1386
   • TwoBitCSwap Make TwoBitCSwap a leaf bloq #1387
   • other things in QECGatesCost GateCount: clifford, rotation, measurement
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. Edit: ✅ this is done
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

[mpharrigan]

For part (3), I propose using the cirq.CompilationTargetGateset infrastructure. It looks like one class (CompilationTargetGateset) has to handle all possible ops instead of each op knowing how to turn into each gateset; so that's how it will be structured

[fdmalone]

CSwapApprox is another @tanujkhattar, e.g. using QECGatesCost for SelectSwapQROM does not automatically yield the cost breakdown in terms of Ands and Toffolis (or just Toffolis) as it is usually quoted in the literature, but rather Ts and And's