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


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


Your Answer

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

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