# How many two-qubit gates are required to implement a general N-qubit unitary?

Is there a known formula or a scaling behaviour for how many two-qubit gates are required to construct a general N-qubit unitary?

I suppose there are several cases to consider:

• Exact representation of the gates
• Approximate decompositions to a given accuracy
• Any subclass of unitaries that have more efficient decompositions
• With vs without ancillary qubits.

edit: As a starting point, I know an optimal decomposition of a general two-qubit gate (into CNOT and single-qubit) and I consider single-qubit operations as "free" (they can be absorbed into the two-qubit gates, and for practical implementations they have lower error rates).

edit: In Nielsen and Chuang they say that there always exists an $$n\times n$$ unitary that requires n-1 2-qubit gates. Are n-1 gates sufficient for a general $$n\times n$$ unitary?

• Do you mean the minimum number of one- and two-qubit gates required for a given unitary, or an estimate on the number of such gates that are sufficient to decompose an arbitrary $n$ qubit unitary? The latter problem is solved and explained in full in Nielsen and Chuang, while the former is a pretty hard question, the answer to which will strongly depends on the problem settings. Exact and approximate cases might also came with very different answers, so you might want ask about them in two different topics. Also, are you considering single-qubit operations as "free" here?
– glS
Jun 18 '19 at 14:30
• @gIS I am mostly interested in the minimum (as long as the argument is constructive), but also estimates. I am also interested in both exact and approximate, but I appreciate your point that these might be significantly different problems. Also I do indeed consider single-qubit operations to be free. In particular, I know an optimal decomposition of a general 2-qubit gate, into which any additional single-qubit operations can be absorbed. I will add some clarification to the question. Jun 19 '19 at 15:19
• Any 2-qubit unitary can be implemented with at most 3 CNOT gates ([source]), and hence the scaling using arbitrary 2-qubit gates is the same as using just CNOT gates, up to a factor of 3. That being said I do not know the exact answer to your question, but my guess is that it is exponential in the amount of qubits. This is indeed what you get if you use the cosine-sine decomposition to write your unitary as a series of controlled unitaries. : arxiv.org/pdf/quant-ph/0308006.pdf
– John
Sep 12 '19 at 15:00
• @gIS, would you be able to point me to where in Nielsen and Chuang the problem of sufficient number of gates is covered? Nov 7 '19 at 10:25

based on dimension counting, ... a lower bound on the number of two-bit gates required to produce an arbitrary $$n$$-bit unitary transformation [is]: $$\Omega(n) =\frac19 4^n−\frac13n−\frac19$$.
As an example, suppose we have a quantum system with states in $$\mathbb C^n$$. We take a universal family of gates (the OP wants 1 and 2 qubit ones, so...) say $$\{CNOT, H, X, Z, R(\pi/8)\}$$. Then one can approximate any unitary operator $$U$$ with accuracy $$\epsilon$$ with $$\mathcal O(n^2\log^4\frac1{\epsilon})$$ gates.