`t_complexity` doesn't work for StatePreparationAliasSampling

[mstechly]

When I run this:

bloq = StatePreparationAliasSampling.from_lcu_probs([0.25, 0.5, 0.25], probability_epsilon=0.05)
bloq.t_complexity()

I get the following error:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/_infra/bloq.py", line 420, in t_complexity
    return t_complexity(self)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 240, in t_complexity
    ret = _t_complexity_for_gate_or_op(stc)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/cachetools/__init__.py", line 675, in wrapper
    v = func(*args, **kwargs)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 224, in _t_complexity_for_gate_or_op
    return _t_complexity_from_strategies(gate_or_op, strategies)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 204, in _t_complexity_from_strategies
    ret = strategy(stc)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 163, in _from_bloq_build_call_graph
    r = t_complexity(bloq)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 240, in t_complexity
    ret = _t_complexity_for_gate_or_op(stc)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/cachetools/__init__.py", line 675, in wrapper
    v = func(*args, **kwargs)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 224, in _t_complexity_for_gate_or_op
    return _t_complexity_from_strategies(gate_or_op, strategies)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 204, in _t_complexity_from_strategies
    ret = strategy(stc)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/cirq_interop/t_complexity_protocol.py", line 157, in _from_bloq_build_call_graph
    _, sigma = stc.call_graph(max_depth=1, generalizer=cirq_to_bloqs)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/_infra/bloq.py", line 327, in call_graph
    return get_bloq_call_graph(self, generalizer=generalizer, keep=keep, max_depth=max_depth)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/resource_counting/bloq_counts.py", line 225, in get_bloq_call_graph
    _build_call_graph(bloq, generalizer, ssa, keep, max_depth, g=g, depth=0)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/resource_counting/bloq_counts.py", line 120, in _build_call_graph
    callee_counts = _generalize_callees(bloq.build_call_graph(ssa), generalizer)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/bloqs/multiplexers/unary_iteration_bloq.py", line 622, in build_call_graph
    unary_iteration_loops(0, {}, total_bits(self.control_registers))
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/bloqs/multiplexers/unary_iteration_bloq.py", line 618, in unary_iteration_loops
    unary_iteration_loops(nested_depth + 1, selection_reg_name_to_val, num_controls=1)
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/bloqs/multiplexers/unary_iteration_bloq.py", line 603, in unary_iteration_loops
    for bloq, count in self.nth_operation_callgraph(**selection_reg_name_to_val):
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/bloqs/data_loading/qrom.py", line 236, in nth_operation_callgraph
    return {(CNOT(), sum(int(d[selection_idx]).bit_count() for d in self.data))}
  File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion/lib/python3.9/site-packages/qualtran/bloqs/data_loading/qrom.py", line 236, in <genexpr>
    return {(CNOT(), sum(int(d[selection_idx]).bit_count() for d in self.data))}
AttributeError: 'int' object has no attribute 'bit_count'

Extra comments:

1. I want to do the same on the decomposed version of this bloq (.decompose_bloq()), and both fail the same way.
2. Is t_complexity the main way to get the costs of a given bloq or is there some other way?

[tanujkhattar]

Works fine for me

Can you check your python version? int.bit_count() was introduced in Python 3.10 so maybe you are using an older version?

https://docs.python.org/3/library/stdtypes.html#int.bit_count

1. I want to do the same on the decomposed version of this bloq (.decompose_bloq()), and both fail the same way.

That should also work as expected once the python version is fixed.

2. Is t_complexity the main way to get the costs of a given bloq or is there some other way?

For now, t_complexity is the way to go, but it'll soon be upgraded to use the new costs framework (see #913)

[mstechly]

Indeed, this is 3.9 vs 3.10 problem, thanks Tanuj!
FYI pyproject.toml suggests 3.9 is fine (target_version = ['py39', 'py310']) + from what I see you don't even run CI on 3.9, so perhaps consider dropping it?

[mstechly]

Another a problem with t_complexity, but now in HamiltonianSimulationByGQSP.
When I use either numeric or symbolic version of this bloq, t_complexity doesn't work:

import sympy
from qualtran.bloqs.hamiltonian_simulation.hamiltonian_simulation_by_gqsp import HamiltonianSimulationByGQSP
from qualtran.bloqs.hubbard_model import get_walk_operator_for_hubbard_model

walk_op = get_walk_operator_for_hubbard_model(2, 2, 1, 1)
t, inv_eps = sympy.symbols("t N")
symbolic_hamsim_by_gqsp = HamiltonianSimulationByGQSP(walk_op, t=t, precision=1 / inv_eps)
symbolic_hamsim_by_gqsp.t_complexity()

Traceback

``` Traceback (most recent call last): File "", line 1, in File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/_infra/bloq.py", line 427, in t_complexity return t_complexity(self) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 168, in _from_bloq_build_call_graph r = t_complexity(bloq) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 171, in _from_bloq_build_call_graph ret += n * r File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 57, in __add__ self.t + other.t, self.clifford + other.clifford, self.rotations + other.rotations File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/decorators.py", line 236, in _func return func(self, other) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/decorators.py", line 106, in binary_op_wrapper return func(self, other) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/expr.py", line 198, in __add__ return Add(self, other) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/operations.py", line 98, in __new__ c_part, nc_part, order_symbols = cls.flatten(args) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/add.py", line 367, in flatten if o.contains(t): File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/series/order.py", line 452, in contains obj = self.func(expr, *self.args[1:]) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/series/order.py", line 203, in __new__ expr = expr.subs(s) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1040, in subs rv = rv._subs(old, new, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1154, in _subs rv = fallback(self, old, new) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1126, in fallback arg = arg._subs(old, new, **hints) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1154, in _subs rv = fallback(self, old, new) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1126, in fallback arg = arg._subs(old, new, **hints) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/basic.py", line 1152, in _subs rv = self._eval_subs(old, new) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/series/order.py", line 499, in _eval_subs return Order(newexpr, *zip(newvars, newpt)) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/core/cache.py", line 72, in wrapper retval = cfunc(*args, **kwargs) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/sympy/series/order.py", line 184, in __new__ raise NotImplementedError( NotImplementedError: Multivariable orders at different points are not supported. ```

from qualtran.bloqs.hamiltonian_simulation.hamiltonian_simulation_by_gqsp import HamiltonianSimulationByGQSP
from qualtran.bloqs.hubbard_model import get_walk_operator_for_hubbard_model

walk_op = get_walk_operator_for_hubbard_model(2, 2, 1, 1)
hubbard_time_evolution_by_gqsp = HamiltonianSimulationByGQSP(walk_op, t=5, precision=1e-7)
hubbard_time_evolution_by_gqsp.t_complexity()

Traceback

``` Traceback (most recent call last): File "", line 1, in File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/_infra/bloq.py", line 427, in t_complexity return t_complexity(self) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 168, in _from_bloq_build_call_graph r = t_complexity(bloq) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 168, in _from_bloq_build_call_graph r = t_complexity(bloq) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 168, in _from_bloq_build_call_graph r = t_complexity(bloq) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 168, in _from_bloq_build_call_graph r = t_complexity(bloq) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 245, in t_complexity ret = _t_complexity_for_gate_or_op(stc) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cachetools/__init__.py", line 675, in wrapper v = func(*args, **kwargs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 229, in _t_complexity_for_gate_or_op return _t_complexity_from_strategies(gate_or_op, strategies) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 209, in _t_complexity_from_strategies ret = strategy(stc) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/t_complexity_protocol.py", line 135, in _from_directly_countable op, _ = stc.as_cirq_op(qubit_manager=qm, **quregs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/_infra/controlled.py", line 464, in as_cirq_op sub_op, cirq_quregs = self.subbloq.as_cirq_op(qubit_manager, **cirq_quregs) File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/_infra/bloq.py", line 457, in as_cirq_op return BloqAsCirqGate.bloq_on( File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/cirq_interop/_bloq_to_cirq.py", line 119, in bloq_on all_quregs, out_quregs = _get_all_and_output_quregs_from_input( File "/Users/mstechly/Documents/code/2024-05-07-qualtran-conversion/Qualtran/qualtran/_infra/gate_with_registers.py", line 161, in _get_all_and_output_quregs_from_input qubit_manager.qfree(in_quregs[reg.name].flatten()) File "/Users/mstechly/.pyenv/versions/2024-05-07-qualtran-conversion-310/lib/python3.10/site-packages/cirq/ops/qubit_manager.py", line 100, in qfree raise ValueError(f"{q} was not allocated by {self}") ValueError: reg was not allocated by ```

I'm using 3.10, version from the current main branch (as there have been some recent changes in HamiltonianSimulationByGQSP).

[anurudhp]

Ah thanks for reporting this! I'll investigate.

[tanujkhattar]

Thanks for reporting @mstechly. I've opened #936 to track this. I'll go ahead and close this issue is StatePreparationAliasSampling is working as intended