# Decompose a general two-qubit gate into general controlled-qubit gates

We often seek to decompose multi-qubit unitaries into single-qubit rotations and controlled-rotations, minimising the latter or restricting to gates like CNOTs.

I'm interested in expressing a general 2-qubit unitary in the minimum total number of gates, which can include controlled general unitaries. That is, express $$U_{4}$$ with as few as possible gates in $$\{U_2,\; |0⟩⟨0|\mathbb{1} + |1⟩⟨1|U_2\}$$. While I could simply take the shortest decomposition to CNOTs and rotations (Vatan et al) and bring some rotations into the CNOTs, I suspect another formulation could add more control-unitaries to achieve fewer total gates.

How can I go about performing this decomposition algorithmically for any 2-qubit unitary? This decomposition could be useful for easily extending distributed quantum simulators with the ability to effect general 2-qubit unitaries, which otherwise ad-hoc communication code.

A simple place to start would be to put all the controls on qubit #2, so that you can propagate all of the single-qubit operations on qubit #1 across the two-qubit operations and merge them together. That would give you a circuit with at most 8 gates:

--------C1-------C2-------C3---S5---
|        |        |
---S1---*---S2---*---S3---*----S4---


This is probably not minimal.

A general 4x4 unitary has 7+5+3+1=16 real parameters. Every single-qubit gate has three real parameters (Euler angles), and every two-qubit gate has four real parameters (Euler angles + phase kickback). So the above construction has 4*3 + 4*4 = 28 real parameters.

It is provable that you need at least three different controlled gates for some two-qubit operations. So the absolute best you could hope for is three of those and one single-qubit operation. But some of the degrees of freedom overlap, so I suspect you need more single-qubit gates.

• This is a great start (and looks like the quantum shannon decomp), thanks very much! I suspect one can go shorter by controlling on both qubits, as does the smallest (I think?) decomp of SWAP (3 CNOTs) – Anti Earth Feb 14 at 18:07
• As nicely explained here, the cosine-sine decomposition can decompose a 2-qubit U into 3 multiplexors (two of which feature 2 general unitaries, one of which features two Y rotations). Each multiplexor can be two controlled gates (one NOT-controlled, else an additional NOT is needed). So using controlled-unitaries and NOT gates, that's a worst case 9 ops. Allowing NOT-controlled (easy to code up) unitaries, that's 6 ops. Allowing multiplexors (not too difficult to code up), that's 3 ops. – Anti Earth Feb 15 at 0:37
• @AntiEarth My reading of your question was that you would count a "multiplexor" as two separate gates. You may want to clarify exactly what your constraints are. – Craig Gidney Feb 15 at 0:45