# How many quantum gates are needed to prepare an arbitrary state?

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?

• 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. Dec 27, 2021 at 21:23

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!

A canonical reference for gate decompositions is

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