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.

Answer 3

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.

Answer 4

Just adding to Quantum_Brains' answer, the algorithm by Alok Shukla et al. has been implemented as UniformSuperPositionGate in Qiskit release 1.2. Therefore, you can directly use it in Qiskit. Here is the code from https://docs.quantum.ibm.com/api/qiskit/release-notes/1.2

from qiskit import QuantumCircuit 
from qiskit.circuit.library.data_preparation import UniformSuperpositionGate
 
M = 5
num_qubits = 3
usp_gate = UniformSuperpositionGate(M, num_qubits)
qc = QuantumCircuit(num_qubits)
qc.append(usp_gate, list(range(num_qubits)))
 
qc.draw()