5

In this paper there is this sentence:

[...] the description of a $2^n\times2^n$ unitary matrix $U$ (which is a poly($n$)-size quantum circuit)

According to the meaning of "which" in English, in contrast to "that", the sentence means that the effect of any unitary matrix $U$ can be done by a quantum circuit composed by $m$ quantum gates, with $m$ polynomial in the number of qubits $n$. I assume that the quantum gates act on 1 or 2 qubits (or a fixed number of qubit), else the sentence is trivial ($U$ is a quantum gate itself).

However, I think that this is not true. In particular, I think that an $m$ exponential in $n$ is needed for preparing an arbitrary state, which is a simpler task than simulating the effect of an arbitrary $U$. Can you confirm and suggest a reference?

glS
  • 24,708
  • 5
  • 34
  • 108
Doriano Brogioli
  • 493
  • 2
  • 11
  • 3
    I think they meant a circuit U that is poly(n)-size. Here's the intuition as to why you would need an exponential number of qubits for an arbitrary U: even if you only had 1s and 0s in U, then there are still $2^n!$ possible $2^n$ x $2^n$ unitaries that you can have. However, there are only poly(n)! possible poly(n)-size quantum circuits you can build. Therefore, there cannot possibly exist a one-to-one mapping between the two which means you can't build an arbitrary U with a poly(n)-size quantum circuit even under the condition that U only consists of 1s and 0s. – Dani007 Dec 27 '21 at 21:23

2 Answers2

3

A canonical reference for gate decompositions is

Barenco et al., Elementary gates for quantum computation.

In particular, it also contains recipes to decompose an arbitrary $n$-qubit unitary into elementary gates (which, by parameter counting, requires about $4^n$ gates, assuming each gate has one real parameter.)

Norbert Schuch
  • 6,521
  • 16
  • 27
2

I believe this Q&A answers your question about decomposition in detail: Minimum number of 2 qubit gates to build any unitary

In short, you are correct that the lower bound for a number of 2-qubit gates necessary to implement an arbitrary unitary $U$ is $\Omega(4^n)$ where $n$ is the number of qubits.

I am not entirely sure what authors meant, but perhaps it is a statement of assumption, vs a general assertion (i.e. the input is an unitary $U$ that can be described by a circuit that is $poly(n)$. I'd definitely recommend reaching out to the authors for clarification!

3yakuya
  • 632
  • 3
  • 10