Creating a uniform superposition of a subset of basis states

Question

Assume we have an n qubit system and $K \subset \{1,...,2^n\}, K \neq \emptyset $ I want to describe a circuit that takes the input $|0\rangle....|0\rangle$ to the state $|\psi\rangle = \frac{1}{\sqrt{|K|}}\sum_{k\in K} |k\rangle$

I was thinking of using Grover search to estimate $|\psi\rangle$. I believe it will work fine but this does not require us to know all of $K$ which we do. So I assume there is a better way of doing this. I hope to find a generic process that will work for every subset $K$ without any assumptions.

Answer 1

If $K$ is very small in comparison to its superset $2^n$ then maybe Grover search makes sense. If the size of $K$ is fairly large, say it is at least 1/4 of $2^n$ then a simpler method could be used.

First, implement a binary function $f(x)=1$ for $x \in K$ and $f(x)=0$ otherwise. This is the same as the oracle in Grover, but instead of implementing Grover iterates, we put the first partition of the state $|0\ldots0\rangle |0\rangle$ into a uniform superposition as follows: $$ |0\ldots 0\rangle |0\rangle \rightarrow \frac{1}{\sqrt{2^n}}\sum_{x=1}^{2^n} | x \rangle |0\rangle.$$ Then apply $U_f$ to get: $$\frac{1}{\sqrt{2^n}} \sum_{x=1}^{2^n} | x \rangle |f(x)\rangle.$$ Measure the second qubit. If the output is $1$ (this happens with the probability at least 1/4) then your post measurement state (ignoring the measured qubit) is $$\frac{1}{\sqrt{|K|}} \sum_{k \in K} | k \rangle.$$ If the output is 0, repeat the procedure again.

Answer 2

To add some additional context to @MonteNero's answer:

The most efficient circuit that I'm aware of is in Fig. 12 of encoding electronic spectra.

In short, the circuit operates by:

1. Preparing a uniform superposition over $2^n$ basis states
2. Using an inequality test based on coherent arithmetic to flag whether a basis state is above or below $k$
3. Using a single round of amplitude amplification to boost the probability of finding "good" basis states. The diffusion operator is tweaked so that a single round suffices to produce the state we want with certainty.