`QubitCount` values are wrong (underestimated) for flattened bloqs

[tanujkhattar]

Example code:

from qualtran.bloqs.state_preparation import PrepareUniformSuperposition
from qualtran.resource_counting import get_cost_value, QubitCount
from qualtran.drawing import show_bloqs

bloq = PrepareUniformSuperposition(n=3,cvs=(1,))
cbloq = bloq.decompose_bloq()
cbloq_flat = cbloq.flatten()
print(get_cost_value(bloq, QubitCount()))
print(get_cost_value(cbloq, QubitCount()))
print(get_cost_value(cbloq_flat, QubitCount()))
show_bloqs([bloq, cbloq, cbloq_flat])

Output:

7
6
3

The correct answer for all 3 cases should be 7. The fully flattened bloq seems to completely ignore the allocations / deallocations happening in the decomposition and reports the answer to be 3 (which is equal to the number of qubits in the signature). This trend also continues for larger values of n. For example:

bloq = PrepareUniformSuperposition(n=10000,cvs=(1,))
cbloq = bloq.decompose_bloq()
cbloq_flat = cbloq.flatten()
print(get_cost_value(bloq, QubitCount()))
print(get_cost_value(cbloq, QubitCount()))
print(get_cost_value(cbloq_flat, QubitCount()))
print(bloq.signature.n_qubits())

Output:

27
22
15
15

[mpharrigan]

The QubitCount cost tries to recursively call decompose_bloq to approximate the qubit count. Since CompositeBloq does not support decompose_bloq, it falls back to just using the signature values.

I think it would be natural to support CompositeBloq in get_cost_value but some care will have to be taken to get the caching right

If you call the qubit counting function on cbloq_flat it will overrestimate the count because it allocates everything up front. Maybe #1099 will help that

[mpharrigan]

Related #1073

[tanujkhattar]

Okay, that makes sense. I agree that get_cost_value should support CompositeBloq.

I think the right way to go is to add a cached hash to CompositeBloq and in general cache the hash of all Bloqs. If the user has already paid the cost of constructing a CompositeBloq, then constructing and storing a hash for it should only be a comparable cost. We can also consider constructing the hash and storing it when we call bb.finalize and construct the CompositeBloq in the first place. A BloqBuilder can maintain the hash of the bloq constructed so far to minimize the additional cost.

If we do this, then there's no reason why users cannot use CompositeBloqs as subbloqs when constructing larger composite bloqs (which is also not supported right now, correct?). I can totally imagine a workflow where a users has a method get_cbloq_for_uniform_state_prep instead of defining a class BloqForUniformStatePrep -- both the methods should be supported for resource estimation I think.

If you call the qubit counting function on cbloq_flat it will overrestimate the count because it allocates everything up front. Maybe #1099 will help that

Yes, the linked PR should definitely help with that. The cirq interop functionality already makes use of it to arrive at the right counts. Also, overestimating is better than underestimating in my opinion.

[mpharrigan]

which is also not supported right now, correct

I don't think it's explicitly disallowed and will probably work; but it isn't tested thoroughly. This is the question underpinning #1073 as well. I'll post my thoughts on that issue since it's a bigger question than the specific bug in this issue, which I can fix