# Creating a uniform superposition of a subset of basis states

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.

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.

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