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.


3 Answers 3


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.


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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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