6

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
  • 27,510
  • 7
  • 37
  • 125
Doriano Brogioli
  • 511
  • 2
  • 14

2 Answers2

4

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
  • 8,142
  • 1
  • 19
  • 30
3

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
  • 672
  • 3
  • 10