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

Question

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?

Answer 1

In Elementary gates for quantum computation it is conjectured that

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$.

Answer 2

There's a known theorem known as the Solovay-Kitaev theorem which can be used to deduce the order of the number of gates required to approximate any unitary operator of arbitrary dimension quantum systems.

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.