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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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