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.


2 Answers 2


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.

Your Answer

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

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