Decomposition of multi-controlled unitary single-qubit gates

[renatomello]

Currently, circuit transpilation into single- and two-qubit gates does not transpile multi-controlled single-qubit rotations. For instance,

from qibo import Circuit, gates

nqubits = 4
theta = 0.1

circuit = Circuit(nqubits)
circuit.add(gates.GIVENS(2, 3, theta).controlled_by(0, 1))
circuit.draw()
print()
decomposed = circuit.decompose()
decomposed.draw()

returns

0: ─o─
1: ─o─
2: ─G─
3: ─G─

0: ─────o──o──────
1: ─────o──o──────
2: ─H─o─RY─|──o─H─
3: ───X────RY─X───

without transpiling the multi-controlled RY gates.

To transpile such gates, we would like to implement the techniques in Vale et al. (2023). More specifically, generic multi-controlled $\textrm{SU}(2)$ rotations should follow Lemma 1 and Theorem 1. Real-valued $\textrm{SU}(2)$ rotations should follow Lemma 2 and Theorem 2. Two-qubit gate complexities should respect the upper bounds stated in Theorems 3, 4, and 5.

The authors of the paper have their own open-source implementation in https://github.com/qclib/qclib, which could serve as inspiration for the independent implementation here.

[ACE07-Sev]

Greetings,

Hope you're doing well. Before the event starts, I just wanted to ask a few questions to clarify some details if that's alright.

[renatomello]

Greetings,

Hope you're doing well. Before the event starts, I just wanted to ask a few questions to clarify some details if that's alright.

Ask away

[ACE07-Sev]

Cool. So, I have implemented the synthesis logic, just not sure where to put it. I noticed for MCX you put it directly in _base_decompose, but also have decomposition logic in decompositions.py.

I wanted to ask if it's alright that I follow the MCX approach (basically add _base_decompose for every 1q class), or whether you have some preference regarding where these should go.

Given the scale of the change, it would be great if we can get on the same page design-wise before the PR is made.

P.S: Kindly note that certain single controlled 1q gates like CH as far as I could see are also not available, so with MCX approach I could handle those as well, or I can add new dedicated classes for them like CNOT, CY, and CZ.

[renatomello]

Cool. So, I have implemented the synthesis logic, just not sure where to put it. I noticed for MCX you put it directly in _base_decompose, but also have decomposition logic in decompositions.py.

I wanted to ask if it's alright that I follow the MCX approach (basically add _base_decompose for every 1q class), or whether you have some preference regarding where these should go.

Given the scale of the change, it would be great if we can get on the same page design-wise before the PR is made.

P.S: Kindly note that certain single controlled 1q gates like CH as far as I could see are also not available, so with MCX approach I could handle those as well, or I can add new dedicated classes for them like CNOT, CY, and CZ.

I think what would require the least amount of changes for most gates is to slightly change how the decompose method of the abstract Gate class works

qibo/src/qibo/gates/abstract.py

Line 202 in 16f3491

def decompose(

It is there that the controls are added,

qibo/src/qibo/gates/abstract.py

Line 262 in 16f3491

gate.control_qubits += self.control_qubits

so one could add a second pass that decomposes the newly controlled gate into elementary gates.

Regarding the where the decompositions themselves would be, I would imagine that transpiler.decomposition.py is the best place. I would try to add two protected functions in that file, one for real-valued and another for complex-valued $\textrm{SU(2)}$ gates.
Then, these functions would be called inside Gate._base_decompose

qibo/src/qibo/gates/abstract.py

Line 487 in 16f3491

def _base_decompose(

Something like

func = _new_controlled_decomposition(...) if self.is_controlled_by else standard_decompositions

[ACE07-Sev]

one for real-valued and another for complex-valued SU(2) gates.

Apologies, I was under the impression that one would only need multi-controlled SU2 with real diagonal, since that allows for implementation of MCRX, MCRY, and MCRZ, and with those you can implement it for any other multi-controlled 1q gate, aka MCU3.

This is how qiskit does it as well, just checked again.

[renatomello]

one for real-valued and another for complex-valued SU(2) gates.

Apologies, I was under the impression that one would only need multi-controlled SU2 with real diagonal, since that allows for implementation of MCRX, MCRY, and MCRZ, and with those you can implement it for any other multi-controlled 1q gate, aka MCU3.

This is how qiskit does it as well, just checked again.

As long as it follows the theoretical gate count complexities, I'm fine with it.

[ACE07-Sev]

Mine is actually more efficient.

OrderedDict({'u3': 19, 'cx': 14})

vs qclib

OrderedDict({'u3': 40, 'cx': 24})

for MCH over 3 controls. Since H is not SU2, you have to use their ldmcu AFAIK and that is much more expensive than my implementation. I'll proceed with my current one.

[luffy-orf]

Hi @renatomello, Put up a PR for this Would love your feedback on it

[ACE07-Sev]

@renatomello I was wondering, is there a reason only _Rn_ and _Un_ templates use _controlled_gate for single-controlled routing and Gate doesn't?

[renatomello]

@renatomello I was wondering, is there a reason only _Rn_ and _Un_ templates use _controlled_gate for single-controlled routing and Gate doesn't?

I cannot think of one right now, no. Maybe there is and I'm just unaware of.