Recursive decomposition of controlled gates

[tigerjack]

Is your feature request related to a problem? Please describe. It seems impossible to decompose, through the given linker, a generic controlled gate in terms of the gate itself and other gates. A standard example is given in the figure below, where W can be either Y or Z.

Another example is the decomposition of the multi-controlled X gate, in which I would like to not decompose the X and X.ctrl(1) gates, while at the same time decompose a generic X.ctrl(n) gate, with n>1.

Describe the solution you'd like I would like to be able to decompose those circuits

Describe alternatives you've considered I tried using the solution offered in the very_advanced_linker notebooks, through the usage of classes and QRoutines. This is a minimal working example for the X gate. The latest to_circ results in an infinite loop.

class XMulti(QRoutine):
    def __init__(self):
        super().__init__()
        wr = self.new_wires(1)
        self.apply(X, wr)

    def ctrl(self, nbctrls=1):
        qr = QRoutine()
        wr = qr.new_wires(nbctrls)
        wt = qr.new_wires(self.arity)
        match nbctrls:
            case 0:
                return self
            case 1:
                qr.apply(CNOT, 0, 1)
            case 2:
                # my implementation of CCNOT
                pass
            case _:
                raise Exception("Not implemented yet")
        return qr

@build_gate("X", [], arity=1)
def x():
    return XMulti()

pr = Program()
ctrls = pr.qalloc(3)
#pr.apply(X.ctrl(2), ctrls[:3])
#pr.apply(X.ctrl(1), ctrls[:2])
pr.apply(X, ctrls[0])

cr = pr.to_circ()
cr = pr.to_circ(link=[x])

[ArnaudAtos]

Hi @tigerjack, Using the linker in this specific case will not work. Indeed, the linker replaces gates recursively:

1. the input circuit is composed of a X gate
2. the linker replaces the X gate using the XMulti routine
3. the XMulti routine is composed of a X gate, so the linker go to the step 2

The infinite loop is frustrating but the best thing we can do is to raise an exception if the number of iterations exceed a threshold. @JayEviden we'll need to work on a fix to raise an exception instead of falling in an infinite loop

To avoid this recursion, you can replace the X in the constructor of XMulti by:

• a RX(π/2) gate
• an AbstractGate with a matrix definition (so the gate can be emulated)

My XMulti implementation would be:

class XMulti(QRoutine):
    def __init__(self):
        super().__init__()
        wr = self.new_wires(1)
        self.apply(RX(pi/2), wr)

    def ctrl(self, nbctrls=1):
        qr = QRoutine()
        wr = qr.new_wires(nbctrls)
        wt = qr.new_wires(self.arity)
        match nbctrls:
            case 0:
                return self
            case 1:
                qr.apply(CNOT, 0, 1)
            case 2:
                # my implementation of CCNOT
                pass
            case _:
                raise Exception("Not implemented yet")
        return qr

If you have access to a Qaptiva Machine, you can also have a look to PatternManager (and qat.pbo module) which is better suited for this use case.

[ArnaudAtos]

PS: the very_advanced_linker notebook works because the CCNOT is not described by the same object as X.ctrl(2):

• CCNOT is a predefined gate
• X.ctrl(2) is a predefined gate controlled twice

[tigerjack]

@ArnaudAtos Thanks for your support! Wouldn't it be better to treat basic gates and controlled gates separately when the @build_gate name is C-something?If I remember correctly, in this case the (multi-)controlled gate is never replaced, unless you specifically instantiate a QRoutine with all the base cases as I did in my example. That is, the C-RY gate below is never replaced

@build_gate('C-RY', [float])
def my_cry(angle):
    pass

cr = pr.to_circ(link=[my_cry])

The rationale is that, in many cases, you may want to decompose the (multi-)controlled version of a gate, rather than the gate itself.

The hack you propose should work indeed, but it makes everything non-trivial. For example, what I do now for the same example you provided is the following:

1. in the __init__, I have a custom abstract gate NOT (instead of your RX)
2. I use the linker as I did for the controlled-X gates replacement
3. I have another @build_gate("NOT"): return X that I use in an additional linking stage to replace the NOT gates with X gates

I will have a look at the qat.pbo module (I can access a QLM-1.7 machine, I don't know if it was modified in the meantime).