Make ControlledGate work with gates that only provide a decomposition

[Strilanc]

The following should work:

import cirq


class G(cirq.TwoQubitGate):
    def _decompose_(self, qubits):
        a, b = qubits
        yield cirq.X(a)**0.5
        yield cirq.H(b)
        yield cirq.CZ(a, b)


cg = cirq.ControlledGate(G())
x, y, z = cirq.LineQubit.range(3)
c = cirq.Circuit.from_ops(cg(x, y, z))
print(c.to_unitary_matrix())

but currently it raises an exception:

Operation without a known matrix or decomposition: cirq.ControlledGate(sub_gate=[...G...].on(cirq.LineQubit(0), cirq.LineQubit(1), cirq.LineQubit(2))

because ControlledGate doesn't have a _decompose_ method. This issue is to add that method.

[vtomole]

This is what i have in ControlledGate()

 def _decompose_(self, qubits):
        yield self.sub_gate._decompose_(qubits[1:])

But it's not working:

class G(cirq.SingleQubitGate):
    def _decompose_(self, qubits):
        a = qubits
        yield cirq.X(a[0])

eq = cirq.testing.EqualsTester()
eq.add_equality_group(cirq.ControlledGate(G()), cirq.CNOT) # Nope

What am i missing?

[balopat]

@vtomole - my guess is for your question:

1. the gate you are trying to compare to is not a CNOT - it's a "CG" - a controlled G gate, where G is defined as some generic gate that decomposes to an X gate on the first qubit - but it is not an X gate
2. I'm not entirely sure yet, but unless there is some deeper definition of equality is at play - the CNOT gate is not implemented as a cirq.ControlledGate(cirq.X) so your equality won't work even like this eq.add_equality_group(cirq.ControlledGate(cirq.X), cirq.CNOT) # Still Nope - it is cirq.CNotPowGate().

Besides, unless I'm missing something and this is trivial - it seems to me that there is no easy way to just simply reuse _decompose_ of the subgate, because in general decomposing a controlled gate would require somehow to understand the structure of the subgate and find/come up with a generic algorithm to create a set of gates that result in an equivalent unitary matrix to Id (+) Sub (linalg.block_diag(np.eye(sub_matrix.shape[0]), sub_matrix)).
After a quick search I found Barenko et al that is OK for some cases but not in general and this blogpost which pointed to Zhou et al which would be promising - but that uses this (odd?) X_a operation that uses an "extended Hilbert space" to swap things out...

[balopat]

It looks like figuring out exactly the decomposition contract would help here too: #930

[balopat]

After talking to @Strilanc I did miss something trivial - the sequence of controlled components controlled by the same qubit does equal to the controlled gate. Also learned the context for this issue is this stackexchange question.
I'm happy to work on this.

[vtomole]

@balopat Go for it :)

[Strilanc]

This ended up being more complicated than I expected, because it requires defining a controlled operation and understanding how the decomposition machinery works in detail.

    def _decompose_(self, qubits):
        control_qubit = qubits[0]
        result = protocols.decompose_once_with_qubits(self.sub_gate,
                                                      qubits[1:],
                                                      NotImplemented)
        if result is NotImplemented:
            return NotImplemented
        for op in result:
            yield ControlledOperation(control_qubit, op)