show_call_graph(_modexp_small) fails with an error "CModMulK: base is not invertible for the given modulus"

[tanujkhattar]

from qualtran.bloqs.factoring.mod_exp import _modexp_small
bloq = _modexp_small.make()
show_call_graph(bloq)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
File ~/quantum/Qualtran/qualtran/resource_counting/_qubit_counts.py:111, in QubitCount.compute(self, bloq, get_callee_cost)
    110 try:
--> 111     cbloq = bloq.decompose_bloq()
    112     logger.info("Computing %s for %s from its decomposition", self, bloq)

File ~/quantum/Qualtran/qualtran/_infra/bloq.py:147, in Bloq.decompose_bloq(self)
    134 """Decompose this Bloq into its constituent parts contained in a CompositeBloq.
    135 
    136 Bloq users can call this function to delve into the definition of a Bloq. If you're
   (...)
    145         `build_composite_bloq` returns `NotImplemented`.
    146 """
--> 147 return _decompose_from_build_composite_bloq(self)

File ~/quantum/Qualtran/qualtran/_infra/bloq.py:56, in _decompose_from_build_composite_bloq(bloq)
     55 bb, initial_soqs = BloqBuilder.from_signature(bloq.signature, add_registers_allowed=False)
---> 56 out_soqs = bloq.build_composite_bloq(bb=bb, **initial_soqs)
     57 return bb.finalize(**out_soqs)

File ~/quantum/Qualtran/qualtran/bloqs/mod_arithmetic/mod_multiplication.py:205, in CModMulK.build_composite_bloq(self, bb, ctrl, x)
    204 else:
--> 205     neg_k_inv = -pow(k, -1, mod=self.mod)
    207 # We store the result of the CtrlScaleModAdd into this new register
    208 # and then clear the original `x` register by multiplying in the inverse.

ValueError: base is not invertible for the given modulus

The above exception was the direct cause of the following exception:

RuntimeError                              Traceback (most recent call last)
File ~/quantum/Qualtran/qualtran/resource_counting/_qubit_counts.py:113, in QubitCount.compute(self, bloq, get_callee_cost)
    112     logger.info("Computing %s for %s from its decomposition", self, bloq)
--> 113     return _cbloq_max_width(cbloq._binst_graph, get_callee_cost)
    114 except (DecomposeNotImplementedError, DecomposeTypeError):

File ~/quantum/Qualtran/qualtran/resource_counting/_qubit_counts.py:60, in _cbloq_max_width(binst_graph, _bloq_max_width)
     56 if not isinstance(binst, DanglingT):
     57     # During the application of the binst, we have "observer" connections that have
     58     # width as well as the width from the binst itself. We consider the case where
     59     # the bloq may have a max_width greater than the max of its left/right registers.
---> 60     during_size = _bloq_max_width(binst.bloq) + sum(s.shape for s in in_play)
     61     max_width = smax(max_width, during_size)

File ~/quantum/Qualtran/qualtran/resource_counting/_costing.py:142, in _get_cost_value.<locals>._get_cost_val_internal(callee)
    141 def _get_cost_val_internal(callee: 'Bloq'):
--> 142     return _get_cost_value(callee, cost_key, costs_cache=costs_cache, generalizer=generalizer)

File ~/quantum/Qualtran/qualtran/resource_counting/_costing.py:146, in _get_cost_value(bloq, cost_key, costs_cache, generalizer)
    145 tstart = time.perf_counter()
--> 146 computed_cost = cost_key.compute(bloq, _get_cost_val_internal)
    147 tdur = time.perf_counter() - tstart

File ~/quantum/Qualtran/qualtran/resource_counting/_qubit_counts.py:117, in QubitCount.compute(self, bloq, get_callee_cost)
    116 except Exception as e:
--> 117     raise RuntimeError(
    118         f"An unexpected error occurred when trying to compute {self} for {bloq}: {e}"
    119     ) from e
    121 # Fallback:
    122 # Use the simple maximum of callees and of this bloq's signature. If there
    123 # are no callees, this will be the number of qubits implied by the signature.
    124 # In any case, this strategy is likely an under-estimate of the qubit count.

RuntimeError: An unexpected error occurred when trying to compute qubit count for CModMulK: base is not invertible for the given modulus

The above exception was the direct cause of the following exception:

RuntimeError                              Traceback (most recent call last)
Cell In[22], line 3
      1 from qualtran.bloqs.factoring.mod_exp import _modexp_small
      2 bloq = _modexp_small.make()
----> 3 show_call_graph(bloq)

File ~/quantum/Qualtran/qualtran/drawing/_show_funcs.py:120, in show_call_graph(item, max_depth, agg_gate_counts)
    102 """Display a graph representation of the call graph.
    103 
    104 Args:
   (...)
    116 
    117 """
    118 if isinstance(item, Bloq):
    119     IPython.display.display(
--> 120         GraphvizCallGraph.from_bloq(
    121             item, max_depth=max_depth, agg_gate_counts=agg_gate_counts
    122         ).get_svg()
    123     )
    124 else:
    125     IPython.display.display(GraphvizCounts(item).get_svg())

File ~/quantum/Qualtran/qualtran/drawing/bloq_counts_graph.py:333, in GraphvizCallGraph.from_bloq(cls, bloq, max_depth, agg_gate_counts)
    330 from qualtran.resource_counting import QECGatesCost, QubitCount, query_costs
    332 call_graph, _ = bloq.call_graph(max_depth=max_depth)
--> 333 cost_data: Dict['Bloq', Dict[CostKey, Any]] = query_costs(
    334     bloq, [QubitCount(), QECGatesCost()]
    335 )
    336 formatted_cost_data = cls.format_cost_data(cost_data, agg_gate_counts=agg_gate_counts)
    337 return cls(g=call_graph, bloq_data=formatted_cost_data)

File ~/quantum/Qualtran/qualtran/resource_counting/_costing.py:249, in query_costs(bloq, cost_keys, generalizer)
    247 costs: Dict['Bloq', Dict[CostKey, CostValT]] = defaultdict(dict)
    248 for cost_key in cost_keys:
--> 249     cost_for_bloqs = get_cost_cache(bloq, cost_key, generalizer=generalizer)
    250     for bloq, val in cost_for_bloqs.items():
    251         costs[bloq][cost_key] = val

File ~/quantum/Qualtran/qualtran/resource_counting/_costing.py:220, in get_cost_cache(bloq, cost_key, costs_cache, generalizer)
    217 if isinstance(generalizer, collections.abc.Sequence):
    218     generalizer = _make_composite_generalizer(*generalizer)
--> 220 _get_cost_value(bloq, cost_key, costs_cache=costs_cache, generalizer=generalizer)
    221 return costs_cache

File ~/quantum/Qualtran/qualtran/resource_counting/_costing.py:146, in _get_cost_value(bloq, cost_key, costs_cache, generalizer)
    144 # part b. call the compute method and cache the result.
    145 tstart = time.perf_counter()
--> 146 computed_cost = cost_key.compute(bloq, _get_cost_val_internal)
    147 tdur = time.perf_counter() - tstart
    148 logger.info("Computed %s for %s in %g s", cost_key, bloq, tdur)

File ~/quantum/Qualtran/qualtran/resource_counting/_qubit_counts.py:117, in QubitCount.compute(self, bloq, get_callee_cost)
    115     pass
    116 except Exception as e:
--> 117     raise RuntimeError(
    118         f"An unexpected error occurred when trying to compute {self} for {bloq}: {e}"
    119     ) from e
    121 # Fallback:
    122 # Use the simple maximum of callees and of this bloq's signature. If there
    123 # are no callees, this will be the number of qubits implied by the signature.
    124 # In any case, this strategy is likely an under-estimate of the qubit count.
    125 min_bloq_size = bloq.signature.n_qubits()

RuntimeError: An unexpected error occurred when trying to compute qubit count for ModExp: An unexpected error occurred when trying to compute qubit count for CModMulK: base is not invertible for the given modulus

[tanujkhattar]

Same issue exists for the other bloq example - bloq = _modexp.make()

[tanujkhattar]

Looks like __post_init__ check is not being executed since the method should be called __attrs_post_init__. The bloq example has a combination of base (3) and exponent (15) such that their gcd is not 1 and therefore the parameters are not valid for _modexp_small