15
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 2019 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, 2019 at 15:19
  • 1
    $\begingroup$ Any 2-qubit unitary can be implemented with at most 3 CNOT gates ([source][1]), 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. [1]: arxiv.org/pdf/quant-ph/0308006.pdf $\endgroup$
    – John
    Sep 12, 2019 at 15:00
  • $\begingroup$ @gIS, would you be able to point me to where in Nielsen and Chuang the problem of sufficient number of gates is covered? $\endgroup$
    – as2457
    Nov 7, 2019 at 10:25

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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