# 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$$
Please refer to Algorithm 1 in https://arxiv.org/abs/2306.11747. This is the most efficient deterministic method of preparing the uniform superposition states. Instead of using the probabilistic Amplitude Amplification method used in Fig 12, in the "encoding electronic spectra" paper referred by another answer, Algorithm 1 in https://arxiv.org/abs/2306.11747, uses Hadamard, Controlled Hadamard, and Controlled Rotation gates. Algorithm 1 only needs $$O(\log_2 K)$$ gates with a circuit depth of $$O(\log_2 K)$$ to create the uniform superposition states. No ancilla qubits are needed. It seems to be the optimal method for creating the quantum uniform superposition states.