Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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