Controlled versions of non-THRU bloqs
Opened this issue · 13 comments
With the discussion in #1272 #1273 , I have been reminded of how uncomfortable I feel about controlled versions of bloqs with RIGHT or LEFT (allocating / de-allocating) registers.
There are parts of the code that don't dis-allow this; Maybe we should dis-allow this.
Controlling a bloq can be thought of a special case of the Select operation: our control bit toggles between two possible operations, the identity (do nothing) and the operation in question. The two operations must have the same tensor shape.
From inspection of the tensor simulation code for Controlled, it 'supports' right- and left- registers. But it must make a choice for what the identity operation is. Assume the operation we're considering is a one-bit allocation. It says the "identity operation" is
It's a strange choice though. Assume our control bit is in equal superposition.
-
Controlled(OneState)->$\ket{0} + \ket{1}$ -
Controlled(ZeroState)->$\ket{0}$
This "preferred direction" seems odd
Controlled(ZeroState(), CtrlSpec()).call_classically(ctrl=0)KeyError Traceback (most recent call last)
Cell In[45], line 1
----> 1 Controlled(ZeroState(), CtrlSpec()).call_classically(ctrl=0)
File ~/qutran/qutran/qualtran/_infra/bloq.py:233, in Bloq.call_classically(self, **vals)
212 def call_classically(
213 self, **vals: Union['sympy.Symbol', 'ClassicalValT']
214 ) -> Tuple['ClassicalValT', ...]:
215 """Call this bloq on classical data.
216
217 Bloq users can call this function to apply bloqs to classical data. If you're
(...)
231 registers.
232 """
--> 233 res = self.as_composite_bloq().on_classical_vals(**vals)
234 return tuple(res[reg.name] for reg in self.signature.rights())
File ~/qutran/qutran/qualtran/_infra/composite_bloq.py:220, in CompositeBloq.on_classical_vals(self, **vals)
217 """Support classical data by recursing into the composite bloq."""
218 from qualtran.simulation.classical_sim import call_cbloq_classically
--> 220 out_vals, _ = call_cbloq_classically(self.signature, vals, self._binst_graph)
221 return out_vals
File ~/qutran/qutran/qualtran/simulation/classical_sim.py:174, in call_cbloq_classically(signature, vals, binst_graph)
172 continue
173 pred_cxns, succ_cxns = _binst_to_cxns(binst, binst_graph=binst_graph)
--> 174 _binst_on_classical_vals(binst, pred_cxns, soq_assign)
176 # Track bloq-to-dangle name changes
177 if len(list(signature.rights())) > 0:
File ~/qutran/qutran/qualtran/simulation/classical_sim.py:138, in _binst_on_classical_vals(binst, pred_cxns, soq_assign)
135 in_vals = {reg.name: _in_vals(reg) for reg in bloq.signature.lefts()}
137 # Apply function
--> 138 out_vals = bloq.on_classical_vals(**in_vals)
139 if not isinstance(out_vals, dict):
140 raise TypeError(f"{bloq.__class__.__name__}.on_classical_vals should return a dictionary.")
File ~/qutran/qutran/qualtran/_infra/controlled.py:397, in Controlled.on_classical_vals(self, **vals)
395 def on_classical_vals(self, **vals: 'ClassicalValT') -> Dict[str, 'ClassicalValT']:
396 ctrl_vals = [vals[reg_name] for reg_name in self.ctrl_reg_names]
--> 397 other_vals = {reg.name: vals[reg.name] for reg in self.subbloq.signature}
398 if self.ctrl_spec.is_active(*ctrl_vals):
399 rets = self.subbloq.on_classical_vals(**other_vals)
File ~/qutran/qutran/qualtran/_infra/controlled.py:397, in <dictcomp>(.0)
395 def on_classical_vals(self, **vals: 'ClassicalValT') -> Dict[str, 'ClassicalValT']:
396 ctrl_vals = [vals[reg_name] for reg_name in self.ctrl_reg_names]
--> 397 other_vals = {reg.name: vals[reg.name] for reg in self.subbloq.signature}
398 if self.ctrl_spec.is_active(*ctrl_vals):
399 rets = self.subbloq.on_classical_vals(**other_vals)
KeyError: 'q'
This "preferred direction" seems odd
Is there a more concrete example for why this is odd? Does this cause unintuitive behavior in a real world use case?
The original reasoning was -
- Any bloq with a RIGHT register can be thought of as a qubit allocation in
$\ket{0}$ state + a qubit initialization unitary. - If you performed a controlled operation for (1); you essentially control the unitary that initializes the qubit.
With this reasoning, the Controlled(OneState) corresponds to qubit allocation + CX and Controlled(ZeroState) corresponds to qubit allocation + C-I which is just identity.
Assuming qubit allocation is by default in the bb.allocate().
It just seems like a leaky abstraction to me to consider OneState() as a composite operation where the control bit only affects the second operation. I.e., I'd like to take the idea seriously that "allocations are nodes in the compute graph". If you were initializing a patch on the surface code to the plus state, you wouldn't start it in the zero state and do a hadamard.
bb.allocate() does indeed allocate qubits in the zero state #513
For a OneState(), it's fine to not support controlled bloqs; but this restriction becomes more annoying as we look at higher level bloqs. For example - State preparation bloqs often have RIGHT registers in which a state should be prepared. Controlled state preparation is a commonly used primitive in algorithms. A Controlled(state_preparation_bloq) would be a perfectly reasonable thing to state; but if we don't allow Controlled() on bloqs with non-THRU registers; what's the alternative? Do we need the implement get_ctrl_system for each controlled state prep bloq and implement a custom ControlledStatePrepBloq for each StatePrepBloq; that can handle arbitrary ctrl_spec ?
I can definitely be convinced that "controlled state preparation"'s non-controlled version prepares the zero state. Do you have any references (e.g. circuits from the literature) where it's tacitly assumed that a zero state is returned when the control line is inactive?
More evidence would be if we have state prep bloqs in Qualtran with right registers that we want to control. In the docs, we have https://qualtran.readthedocs.io/en/latest/bloqs/state_preparation/state_preparation_via_rotation_tutorial.html#using-the-bloq-in-a-circuit which can be interpreted either way
- the bloq only makes sense with thru registers and a user-provided input state; so that the controlled version makes sense. Looking at the circuit, if you were to control this whole circuit you'd just control the unitary part and e.g. always allocate the zero state and the phase gradient state
- the bloq should be re-written with RIGHT registers
As seen in #1305, there's really no where in the library where we control right registers. Except for And but the controlled version creates additional junk registers which is starting to really get outside the realm of what makes sense for a default-controlled implementation xref #1272
I always have a preference for including a restriction like this until we have a demonstrated use case to lift it; at which point we can lift it
Do you have any references (e.g. circuits from the literature) where it's tacitly assumed that a zero state is returned when the control line is inactive?
I think everywhere we do a controlled QROM read; this is the assumption because when costing algorithms people always assume QROAMClean variant with lowest toffoli counts; which only make sense for RIGHT registers. And therefore doing a controlled QROM gives us a target register in 0 state.
Controlled QROMs are used at multiple places in algorithms; for example:
Fig 5 of https://arxiv.org/pdf/2011.03494. As you would notice; the diagram explicitly shows that a bloq was initialized in the 0 state and used as a target for loading data QROAMClean and the same data lookup was uncomputed; post which the register was used as a target for a different data lookup.
Here is the cost explanation of the figure:
Notice that Step-6 makes sense only when you assume target was initially 0 and should be left in 0; i.e. the QROAMCleanAdjoint bloq which has target as a LEFT register.
The correct way to draw this figure in qualtran would use QROAMClean and QROAMAdjoint and have RIGHT and LEFT registers showing data lookups and uncomputation of data lookups. And we would need controlled versions of both.
I always have a preference for including a restriction like this until we have a demonstrated use case to lift it
I think there are enough examples that indicate we shouldn't have this restriction. The only reason we don't have existing tests in Qualtarn is because we don't have that many end to end implementations of algorithms where we use these (relatively newly implemented) bloqs. Hopefully the example I give above is convincing enough.
Thanks, I'm coming around to the idea that general-purpose controlled versions of allocating-bloqs-with-a-decomposition makes sense with an important caveat.
Controlled(QROAMClean()).decompose_bloq() is [ZeroState.controlled(), QROAMCleanUnitary.controlled()]. ZeroState.controlled() should probably return (uncontrolled) ZeroState.
Now consider a composite bloq that allocates e.g. a plus state and does a unitary operation that we want to enclose in a bloq with a right register. Going off the same figure: imagine we had a SwapTest bloq that decomposes into [PlusState, CSwap]. The decomposition of the controlled version of this would be
[PlusState.controlled(), CSwap.controlled()]. The second thing is trivially CCSwap. What should the first thing be? I'm inclined to say that it should be PlusState().
in summary, we can't completely get away from the question of what does AtomicAllocation.controlled() mean? Since PlusState doesn't decompose into Alloc, Hadamard, I think it's strange for the inactive-control version to be a zero state
for resource counting purposes, I'm actually okay with keeping the current behaviour of returning Controlled(...). we just need resource counting code to recognize that Controlled(And) and Controlled(MultiAnd) are just the original and count + 1 or 0.
As to whether we should support Controlled of bloqs that have LEFt/RIGHT registers ... I will leave that to you
Apart from this, Controlled(T) should be a leaf bloq, Craig had a decomposition that uses 4
resource counting code to recognize that Controlled(And) and Controlled(MultiAnd) are just the original and count + 1 or 0.
I'd like to slow the increase of business logic in the gate counting code.
And.controlled() and MultiAnd(...).controlled()
It feels like this should be easy to support: just return a MultiAnd with the extra control values! But this actually breaks the "contract" for controlled gates. It changes the signature outside of the expected changes based on CtrlSpec.qdtypes. Specifically: every time you increase the number of controls, you get new junk soquets (in addition to the expected new control soquets). Anything using the get_ctrl_system protocol---specifically the decompose method of Controlled---will not know what to do with these new soquets. This is a deal breaker. For automated controlling of circuits containing And, we'd need to encode that they come in pairs: #1221
Controlled(And)
As nour points out, we could theoretically put custom logic in the resource counting code to count gates here. This would not support decomposition. Classical simulation would be possible but is currently broken. Tensor simulation works, since it's well defined what the RIGHT target bit should be for a new, inactive control (i.e. zero)
Controlled(MultiAnd)
If it weren't for the junk register, this could be supported by all the protocols; but it would be an inefficient construction. Using MultiAnd(n).controlled() -> MultiAnd(n+1) would be way more efficient
Controlled(BloqWithRR)
(i.e. a non-atomic bloq with a right register)
This could be supported by taking our definition of Controlled: the decomposition is controlled versions of all the (sub)bloqs in the original decomposition. Importantly, this means you will ultimately get to the point where you are doing AtomicAllocation.controlled() as part of the definition of Controlled(BloqWithRR) so we can't ignore this question.
AtomicAllocation.controlled()
It's really unclear what this should be.
One approach (sortof cirq/nisq style) would be to mandate that there is only one atomic allocation operation: allocate zero. ZeroState.controlled() is always OneState as [ZeroState, XGate] and OneState.controlled() would give
Another option would be to treat allocation operations like bookkeeping operations. It doesn't make sense for an allocation (or split) not to happen or else you wouldn't have any soquets to plug in to subsequent operations. Specifically: PlusState().controlled() would return an uncontrolled PlusState() and pass through the control line:
The classical simulation code would need to be updated to support the definition we choose. It currently breaks because if the control bit is inactive, it won't return the allocated value.
From a practical perspective,
- the classical simulation is broken for right registers
- the tensor simulation uses the definition that I find distasteful and is liable to change
- there's nowhere in the library that uses
Controlledon a right-register-having bloq - it's easier to relax a restriction than impose a new one later
I'd advocate for merging #1305 until there's a clear design and need for Controlled(BloqWithRR) and keeping this issue open to track