# Understanding operations of quantum computing advantages

For example, let us examine the case of quantum (discrete) fourier transform.

There are $2^N$ samples. How do we initialize these $2^N$ samples into $N$ qubits? I have a hard time understanding this.

-

## 1 Answer

Usually a quantum computer is specified as a quantum circuit performing a specific task, with a simple input. In this context, the initialization of any random quantum state of $N$ qubits would be the construction of a unitary transformation mapping some easy state to it, e.g. $|00\cdots 0\rangle$.

When you start out with a finite set of gates, you cannot for any given state construct a circuit that exactly maps $|00\cdots 0\rangle$ to it, but you can approximate any state as closely as you want. The Solovay-Kitaev theorem states that the number of gates required to approximate any unitary transformation on a can be approximated to within any $\varepsilon > 0$ in operator norm in a number of gates that is of the order of $\log^2\varepsilon$. That implies that to map $|00\cdots 0\rangle$ to within $\varepsilon$ of your target state you can do with in the order of $\log^2\varepsilon$ gates for fixed $N$. This is not too bad.

The number of gates required to approximate any unitary transformation up to within a fixed $\varepsilon$ unfortunately is polynomial in $2^N$ and can be considered intractable.

Of course, initializing a single state is easier than approximating an entire unitary transformation, as you are not interested in what happens to the orthogonal complement. This should still be at least linear in $2^N$ in the general case.

In "practice" one restricts to states and unitary transformations that can be obtained by a circuit whose size is polynomial in $N$.

-