What is a complexity of producing arbitrary equally distributed superposition?

Question

In the article An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits I found statement (pg. 4):

Preparing an initial state takes $\log_2(N)$ steps.

In this case the initial state is uniformly distributed superposition of $n$ qubits where some states from computational basis are missing (example for two qubits: $\frac{1}{\sqrt{3}}(|00\rangle + |01\rangle+|11\rangle)$). Since $N=2^n$ the statement above means that complexity of preparing such state is linear in number of qubits.

In case all computational basis states are present in the required state, it is possible to use $H^{\otimes n}$ gate for preparing such state and in this case number of steps is even constant under assumpation that all Hadamard gates can be applied at once on all qubits.

However, since some computational basis states are missing, more complex circuit involving CNOT gates has to be constructed. In article Transformation of quantum states using uniformly controlled rotations, a general method how to produce arbitrary quantum state is proposed. Of course, this method is also suitable for preparing equally distributed states. However, the method leads to exponential incerease in gates number with increasing number of qubits.

So, my question is: What is a complexity of preparing uniformlly distributed states with some missing computational basis states? Is it really linear in number of qubits?

Answer 1

Because the family of states you are describing has $2^n$ entries, and each state must have a distinct circuit, you need $\tilde \Omega(n)$ gates for some of the states just to ensure the circuits are different.

If you limit your scope to >25% dense states with an efficient predicate, then you can use amplitude amplification over the predicate to prepare the superposition quickly. For example, you can prepare a uniform superposition of all states from $|0\rangle$ to $|k\rangle$ in this way in $O(\lg k + \lg \frac{1}{\epsilon})$ operations.