T Complexity ignoring cliffords

[mpharrigan]

I notice in a lot of places we have placeholder T complexity that includes the correct T complexity but doesn't do accounting for cliffords. This is good and fine, except I think we need a sentinel value to indicate that cliffords are not zero; they're just not accounted for

t1 = TComplexity(t=123, cliffords=Ignore)
t1 + TComplexity(t=1, cliffords=5)
>>> TComplexity(t=124,  cliffords=Ignore)

this is like an even bigger O notation

[mpharrigan]

@NoureldinYosri @tanujkhattar @fdmalone

[NoureldinYosri]

An Ingore sentinal value will have a certain behavour. while computing the complexity through decompose adding cliffords should give the sentinal value if any of the summands is a sentinal. but in testing.assert_decompose_is_consistent_with_t_complexity should it fail if recieves the sentinal value on one side and not the other. what if both sides are = Ignore.

This is why I think the sentinal value will be exactly what NaN is in C++ espcially as the library grows.

NaN == NaN => False
NaN != NaN => True
NaN + x = x + NaN = NaN

However if we are going to accept that those counts as possibly inacurate then why not just overload the comparison operators to ignore them? and to make sure that the clifford counts are still somewhat accurate we can make testing.assert_decompose_is_consistent_with_t_complexity check that the clifford difference is relatively small.

[mpharrigan]

yes, that's what I had in mind

why not just overload the comparison operators to ignore them I imagine a user can use the TComplexity objects in ways other than using the comparison operators. For example, they could look at them.

check that the clifford difference is relatively small.

This would need to be made precise. We need to support actual big-O notation in our resource estimates. Whether we use sympy or something else and whether we overload the existing protocol or introduce another one is a design decision.

[tanujkhattar]

I think having some estimate for cliffords is better than getting back a NaN or equivalent? We can include an additional flag that indicates whether the clifford counts are approximate or exact, but I think it would be annoying for me to get back a NaN if among the 100 different primitive gates used in my resource estimation circuit only 1 has a placeholder clifford count instead of exact clifford counts.

I'd much rather get back a TComplexity(t=123, cliffords=1234, approximate=True) instead of TComplexity(t=124, cliffords=Ignore). The comparators can be written such that clifford comparison is ignored when the approximate flag is true for both the values.

[fdmalone]

What if the clifford count is unknown? Would we set to zero and approximate=True? For example, say a paper only quotes the T complexity and doesn't provide a circuit construction, should we just figure out the missing bits?

[mpharrigan]

another approach would be to record a lower bound of zero (or whatever). This is more specific than just an "approximate" flag

[rroodll]

Does anyone have a current update for this Issue? We are discussing the future of resource estimation and knowing the status of the clifford's=Ignore (plus any other metrics you may be adding soonish)

Thanks, Rob

[mpharrigan]

We (still) don't distinguish between "zero" and "unknown", and I don't have anything to share for concrete plans to extend this right now.