Use MultiControlX for all controlled-x-like gates

[mpharrigan]

I was thinking the natural thing to do here should be to return an instance of the MultiControlX gate if you do Toffoli().controlled(), but then I checked that we don't return MultiControX from XGate.controlled() or CNOT.controlled() either.

This works for now. Eventually, it'll be nice to have the same bloq constructed upon calling

>>> XGate().controlled(CtrlSpec(cvs=[1, 1, 1, 1, 1]))
>>> CNOT().controlled(CtrlSpec(cvs=[1, 1, 1, 1]))
>>> Toffoli().controlled(CtrlSpec(cvs=[1, 1, 1]))

and the natural bloq to return for all three would be MultiControlX(cvs=(1, 1, 1, 1, 1)).

Originally posted by @tanujkhattar in https://github.com/quantumlib/Qualtran/pull/1552#discussion_r1955339975

[daxfohl]

FWIW I've been thinking the same thing for Cirq. Things like ControlledGate(CZ, [1,1,1]) end up being a pain in decomposition and require special handling in ControlledGate._decompose_, which could be avoided if we did something like this.

[mpharrigan]

Yeah, to be clear this applies to the thing you get by default with CNOT().controlled(...). We'll always have different spellings for the same thing, like CNOT() vs MultiControlX([1]) or even Controlled(XGate()) whose bloq objects will not compare as equal; but each of which behave exactly according to the Bloq API.

[daxfohl]

Yeah I was thinking in Cirq it might be nice to have a canonicalize method on ControlledGate that would return self.subgate.controlled(self.controls). Especially in decomposition, we could try that first, which may circumvent the need to decompose at all if the canonical gate is in the gateset.

[mpharrigan]

Since this came up in #1768, I'll provide a summary of the current state of things

• MultiControlX suggests to use XGate().controlled() instead of it.
• XGate().controlled() uses the general behavior of wrapping with ControlledViaAnd(XGate(), ctrl_spec) which works with any control spec
  • except! it will return CNOT() for XGate.controlled(). This is important to make ControlledViaAnd work
  • also except: it will return Toffoli() for CtrlSpec(cvs=(1,1)). I think this is fine
• CNOT().controlled() special cases Toffoli() but otherwise does ControlledViaAnd(CNOT()) which isn't ideal: it should use ControlledViaAnd(XGate()) with extra cvs
• #1771 changes Toffoli.controlled() to always give ControlledViaAnd(XGate(), ...); a step towards making this issue a reality