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:

        |        |        |

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.

  • $\begingroup$ 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) $\endgroup$ – Anti Earth Feb 14 at 18:07
  • $\begingroup$ 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. $\endgroup$ – Anti Earth Feb 15 at 0:37
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney Feb 15 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.