Qubit counting

[mpharrigan]

The bloq counts protocol can get you the number of operations the algorithm must perform; which gives you the time cost of an algorithm. The other cost is the number of qubits required, sometimes called circuit width

Qualtran uses implicit allocations and de-allocations. Explicitly allocating memory addresses is part of the translation-to-assembly step and requires unrolling the full algorithm in gorey detail. This is probably slow. We should try it anyways to see how slow.

For large algorithms, we can provide approximations or bounds on qubit count which (I think) roughly corresponds to topologically grouping bloqs or operating them each in sequence. We care about the "max width" of an algorithm because our qubits are physically present in a static architecture. Do we care about other qubit counting quantities like "average width" or something? The max width is a property that must be equal to or greater than the sum of a bloq’s register sizes (max over LEFT vs RIGHT). The max width can be manually annotated. The default fallback for max width is the max over the max-width of a bloq’s decomposition. When optimizing for circuit depth, we sum over the max-width of topological groups in the decomposition. When optimizing for qubit count, we consider each sub-bloq sequentially.

Should we provide some sort of annotation or mixin for bloqs that don’t allocate; i.e. their max width is equivalent to their min width (i.e. their register sizes)?

[mpharrigan]

This is provided via the QubitCounts() cost key