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?

  • 2
    $\begingroup$ 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? $\endgroup$ – glS Jun 18 at 14:30
  • $\begingroup$ @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. $\endgroup$ – as2457 Jun 19 at 15:19

Your Answer

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

Browse other questions tagged or ask your own question.