Closed
Description
I was trying to cost out an algorithm that makes use of a multi-controlled Pauli gate and I ran into some issues. It sounds like we might benefit from making .controlled() work more robustly, or at least documenting the difficulties.
In particular, I expected that calling .controlled(...) on an XGate() would work, but I found that it did not.
Here is a minimal example. After importing,
from sympy import Symbol
import cirq
from qualtran import CtrlSpec, QUInt
from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma
from qualtran.bloqs.basic_gates import XGate
from qualtran.bloqs.mcmt import MultiControlPauli
from qualtran.symbolics import HasLength
from qualtran.cirq_interop.t_complexity_protocol import t_complexity
then running the code
my_gate = XGate().controlled(CtrlSpec(qdtypes=QUInt(8), cvs=1))
print(t_complexity(my_gate))
produced the error
---------------------------------------------------------------------------
DecomposeNotImplementedError Traceback (most recent call last)
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/controlled.py in build_call_graph(self, ssa)
390 try:
--> 391 sub_cg = self.subbloq.build_call_graph(ssa=ssa)
392 except DecomposeTypeError as e1:
11 frames
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/bloq.py in build_call_graph(self, ssa)
295 """
--> 296 return self.decompose_bloq().build_call_graph(ssa)
297
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/bloq.py in decompose_bloq(self)
146 """
--> 147 return _decompose_from_build_composite_bloq(self)
148
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/bloq.py 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)
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/bloq.py in build_composite_bloq(self, bb, **soqs)
130 """
--> 131 raise DecomposeNotImplementedError(f"{self} does not declare a decomposition.")
132
DecomposeNotImplementedError: XGate does not declare a decomposition.
The above exception was the direct cause of the following exception:
DecomposeNotImplementedError Traceback (most recent call last)
<ipython-input-2-67df516c94c5> in <cell line: 3>()
1 my_gate = XGate().controlled(CtrlSpec(qdtypes=QUInt(8), cvs=1))
2
----> 3 print(t_complexity(my_gate))
/usr/local/lib/python3.10/dist-packages/qualtran/cirq_interop/t_complexity_protocol.py in t_complexity(bloq)
262 from qualtran.resource_counting import get_cost_value, QECGatesCost
263
--> 264 return get_cost_value(bloq, QECGatesCost(legacy_shims=True)).to_legacy_t_complexity()
265
266 ret = _t_complexity_for_bloq(bloq)
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_costing.py in get_cost_value(bloq, cost_key, costs_cache, generalizer)
181 generalizer = _make_composite_generalizer(*generalizer)
182
--> 183 cost_val = _get_cost_value(bloq, cost_key, costs_cache=costs_cache, generalizer=generalizer)
184 return cost_val
185
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_costing.py 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)
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_bloq_counts.py in compute(self, bloq, get_callee_cost)
370 # Recursive case
371 totals = GateCounts()
--> 372 callees = get_bloq_callee_counts(bloq, ignore_decomp_failure=False)
373 logger.info("Computing %s for %s from %d callee(s)", self, bloq, len(callees))
374 for callee, n_times_called in callees:
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_call_graph.py in get_bloq_callee_counts(bloq, generalizer, ssa, ignore_decomp_failure)
150 return []
151 else:
--> 152 raise e
153
154
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_call_graph.py in get_bloq_callee_counts(bloq, generalizer, ssa, ignore_decomp_failure)
145
146 try:
--> 147 return _generalize_callees(bloq.build_call_graph(ssa), cast(GeneralizerT, generalizer))
148 except (DecomposeNotImplementedError, DecomposeTypeError) as e:
149 if ignore_decomp_failure:
/usr/local/lib/python3.10/dist-packages/qualtran/_infra/controlled.py in build_call_graph(self, ssa)
393 raise DecomposeTypeError(f"Could not build call graph for {self}: {e1}") from e1
394 except DecomposeNotImplementedError as e2:
--> 395 raise DecomposeNotImplementedError(
396 f"Could not build call graph for {self}: {e2}"
397 ) from e2
DecomposeNotImplementedError: Could not build call graph for C[8][XGate]: XGate does not declare a decomposition.
I got a slightly different error when I used a symbolic parameter:
k = Symbol("k", integer=True, positive=True)
my_symbolic_gate = XGate().controlled(CtrlSpec(qdtypes=QUInt(k), cvs=1))
print(t_complexity(my_symbolic_gate)
This yielded the error message
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-3-973900d6d987> in <cell line: 5>()
3 my_symbolic_gate = XGate().controlled(CtrlSpec(qdtypes=QUInt(k), cvs=1))
4
----> 5 print(t_complexity(my_symbolic_gate))
5 frames
/usr/local/lib/python3.10/dist-packages/qualtran/cirq_interop/t_complexity_protocol.py in t_complexity(bloq)
262 from qualtran.resource_counting import get_cost_value, QECGatesCost
263
--> 264 return get_cost_value(bloq, QECGatesCost(legacy_shims=True)).to_legacy_t_complexity()
265
266 ret = _t_complexity_for_bloq(bloq)
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_costing.py in get_cost_value(bloq, cost_key, costs_cache, generalizer)
181 generalizer = _make_composite_generalizer(*generalizer)
182
--> 183 cost_val = _get_cost_value(bloq, cost_key, costs_cache=costs_cache, generalizer=generalizer)
184 return cost_val
185
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_costing.py 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)
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/_bloq_counts.py in compute(self, bloq, get_callee_cost)
365 return GateCounts()
366
--> 367 if bloq_is_rotation(bloq):
368 return GateCounts(rotation=1)
369
/usr/local/lib/python3.10/dist-packages/qualtran/resource_counting/classify_bloqs.py in bloq_is_rotation(b)
230
231 if isinstance(b, Controlled):
--> 232 if b.ctrl_spec.num_qubits > 1:
233 return False
234
/usr/local/lib/python3.10/dist-packages/sympy/core/relational.py in __bool__(self)
514
515 def __bool__(self):
--> 516 raise TypeError("cannot determine truth value of Relational")
517
518 def _eval_as_set(self):
TypeError: cannot determine truth value of Relational
@mpharrigan suggested the alternative approach,
ccpauli_symb = MultiControlPauli(cvs=HasLength(k), target_gate=cirq.X)
print(t_complexity(ccpauli_symb).asdict())
which does work, except that I need to add .asdict() for things to print properly. I will open a separate issue for this.