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?