Difficulty of creating arbitrary amplitude-encoded quantum states

Question

Let $b \in \mathbb{C}^N$ be some vector, which we want to encode as a quantum state $\sum_{j=0}^{N-1} b_j |j \rangle$.

The problem of achieving this encoding seems to be difficult in many cases, however it is not clear to me why that is the case...

Answer 1

Here's a crude argument (which one can undoubtedly pick holes in, but I think helps with intuition)...

Let's say you want to create an arbitrary state of $n$ qubits, so $N=2^n$. This means that you have roughly $2^n$ complex parameters (up to global phase and normalisation considerations).

Now, you want to build this state our of a particular collection of gates, such as arbitrary single-qubit rotations + controlled-not. Each of the single-qubit gates takes an input of 4 real parameters: three that specify the direction of the rotation, and one for the angle of rotation. Controlled-not doesn't have any real parameters. Both also have integer parameters specifying which qubits they act on, but I'm ignoring those for now.

So, to get enough freedom to specify those $2^n$ complex parameters, you're (roughly speaking) going to need about $2^n/2$ gates (I've translated 4 real parameters into 2 complex parameters, but even there I'm technically over-counting because of normalisation). The point is that you're going to need exponentially many gates, so it's a hard problem.