Any unitary $U$ acting on $N$ qubits can be decomposed in a finite product $U=U_1U_2...U_n$ where every $U_i$ acts on only 2 qubits, for example through decomposition in CNOT, phase shifts and 1 qubit rotations.

Is there a theorem that gives $n_{min}$ the minimum number of 2 qubit gates to build any fixed size unitary ?

(Given that every qubit need to be used at least once $n_{min}\geq N$)


2 Answers 2


Theoretical lower bound

In contrast to the answer by Bertrand, I will assume that along with a $CNOT$ gate we have arbitrary single-qubit unitaries on our disposal. In this case, one can derive the theoretical lower bound on the number of $CNOTs$ neseccary to decompose an arbitrary $n$-qubit unitary $$ L:=\#\text{CNOTs} \geq \frac14\left(4^n-3n-1\right) \label{TLB} $$ In fact, the derivation of this bound is quite intuitive and I will sketch the proof. A general $d\times d$ unitary has $d^2$ real parameters. For $n$ qubits $d=2^n$. Single one-qubit gate has 3 real parameters. However, we can not just keep stacking 1-qubits gates like here

enter image description here $\approx$ enter image description here

because any sequence of one-qubit gates applied to the same qubit can be reduced to a single one-qubit gate and hence can have no more than 3 parameters. That means, that without CNOTs we can only have 3n parameters in our circuit, 3 for each one-qubit gate. This is definitely not enough to describe an arbitrary unitary on $n$ qubits which has $d^2=4^n$ parameters.

Now, adding a single CNOT allows to insert two more 1-qubit unitaries after it, like that

enter image description here

At the first glance this allows to add 6 more parameters. However, each single-qubit unitary can be represented via the Euler angles as a product of only $R_z$ and $R_x$ rotations either as $U=R_z R_x R_z$ or $U=R_x R_y R_z$ (I do not specify angles). Now, $CNOT$ can be represented as $CNOT=|0\rangle\langle 0|\otimes I+|1\rangle\langle 1|\otimes X$. It follows that $R_z$ commutes with the control of $CNOT$ and $R_x$ commutes with the target of $CNOT$, hence they can be dragged to the left and joined with preceding one-qubit gates. So in fact each new $CNOT$ gate allows to add only 4 real parameters:

enter image description here

That's it, there are no more caveats. Thus, the total number of parameters we can get with $L$ CNOTs is $3n+4L$ and we need to describe a $d\times d$ unitary which has $4^n$ parameters. In fact, the global phase of the unitary is irrelevant so we only need $3n+4L \geq 4^n-1$. Solving for $L$ gives the theoretical lower bound. Pretty cool!

Exact compilation

There is an algorithm, called quantum Shannon decomposition (see paper), which gives an exact compilation of any unitary with the number of $CNOTs$ roughly twice as much as required by the theoretical lower bound.

Approximate compilation

In a couple of recent papers (ref 1, ref 2) a numerical optimization approach was explored. It was found that (at least for small qubit numbers) the theoretical lower bound can always be achieved with an exceptional fidelity (hinting that the exact compilation can also be possible). What I find especially interesting about these results is that they also generalize to limited connectivity, apparently without any overhead. For example, the number of $CNOTs$ needed to decompose a random 5-qubit unitary on a line topology (where only neighboring qubits can interact) is the same as on the fully connected topology.

Special gates

A very important disclaimer is in order here. Formally, the set of unitaries which does not have to obey the theoretical lower bound has measure zero in the space of all unitaries of a given size. However, in actual quantum algorithms most of the time only very specific gates are used (say multi-controlled gates) and those do fall in this special set where the theoretical lower bound does not apply. This means that for most multi-qubit gates of practical interest much more efficient decompositions exist.

  • $\begingroup$ Hi Nikita, thank you very much for your answer. Are there some papers on the last point you mentioned? $\endgroup$ Commented Nov 21, 2022 at 14:14
  • $\begingroup$ @Blubsiwubsi Hi! What are you looking for, exactly? To see that most gates appearing in the algorithms are way below the theoretical lower bound is basically trivial. E.g. look at the quantum Fourier transform on $n$ qubits and verify that the number of CNOT gates the is way below $4^{n-1}$. $\endgroup$ Commented Nov 21, 2022 at 14:30
  • $\begingroup$ Thanks for the quick answer. Ofcourse, I totally forgot about QFT. I just recently read this paper and they decomposed quantum algorithm for genome analysis and the corresponding circuit CNOT count was above the lower bound. So I was just wondering if we really can say that "for most multi-qubit gates" the decomposition can be done efficient. I would say we really do not know, since we do not have a lot of quantum algorithms (ye). $\endgroup$ Commented Nov 21, 2022 at 15:18

Let me try to reformulate your question: Given a Universal Set of Quantum Gates $\mathcal{G}$; and some $n$-bit Unitary $U$. Can we find some $q$ such that $q$ is the minimum number of gates selected from $\mathcal{G}$ to have the effect of $U$ on $n$ qubits? (Note: I changed some variables since typically $n$ is the number of bits and $N=2^n$ is the dimensions of our Hilbert Space).

Finding a direct and general expression for such an $q$ would be extremely difficult and it's namely because of all possible gatesets that we may be provided with. Think in the classical case how a universal set of gates can be $\{AND, OR, NOT\}$ or $\{NAND\}$ or $\{MUX\}$ or... For some boolean expression; if you are given a certain universal gateset it completely changes your optimization strategy and correspondingly your minimum number of gates used. The same is true for the quantum case; there really isn't some magical and general formula (although there are definitely specific examples for which $q$ can be found)...but there is something close!

The Solovay-Kitaev Theorem is incredibly important to quantum computing and it is related to the question you ask. It states the following: There exists some constant $c$ such that for any unitary $U\in SU(2)$ there is a set of $S$ gates from any Universal Set of Gates $\mathcal{G}$ such that $|S|=O(\log^c(\frac{1}{\epsilon}))$ for some $\epsilon>0$.

  • 4
    $\begingroup$ It is worthwhile to note that the Solovay-Kitaev theorem is about approximating unitaries with a given gate set. In contrast, answering the original question is rather simple since it was posed on exact synthesis. And in this case, there is simply no lower bound for arbitrary unitaries from $SU(2)$. $\endgroup$ Commented Sep 25, 2021 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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