What is the complexity of splitting a state into a superposition of $n$ computational basis states?

Question

$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$ I'm looking for (unitary$^1$) transformations$^2$, to create a superposition of any $n$ computational basis states with equal coefficients. I'm further interested in the complexity of these implementations and/or a gate count.

Building up on this question, on how to create superpositions of 3 states, I wonder how it scales to split up into any number of $n$ computational basis states. For simplicity let's always start with $\ket{00...0}$. Here are my thoughts:

1. $n=5$: Split $\ket{000}\rightarrow \sqrt\frac25\ket{000}+ \sqrt\frac35\ket{001}$ by a local $Y$-gate , then implement a controlled (trigger when the rightmost bit is $0$) split like $\ket{000}\rightarrow \sqrt{\frac12}(\ket{000}+\ket{010})$ and finally a controlled (trigger when the leftmost bit is $1$) split like $\ket{001}\rightarrow \sqrt{\frac13}(\ket{001}+\ket{011}+\ket{111})$. For reference see here.
2. $n=6$: same as for $n=5$ but after an local split into 2 equal halves on the first (rightmost/top) qubit, 2 controlled splits into 3 states are involved.
3. $n=7$: again split in two parts with the weigths $\sqrt\frac37 :\sqrt\frac47$ and further implement controlled splits...
4. $n=8$: trivial
5. $n=9$: this takes 4 qubits. Split into 3 on the first 2 qubits and then have controlled splits into another 3 on the last 2 qubits.

I haven't counted CNOTs and local operations (necessary for answering the scaling question), but the pattern looks like something, how to decompose numbers. Is there a generic way to come up with a circuit to split into $n$ computational basis states?

If you can improve my suggested implementations, let me know...

Answer 1

I'm not quite sure why using Grover is cheating, or what the motivation is for discounting measurement. However, there is a way of thinking about an algorithm without either. It also runs as $O(m^2)$ where $m=\lceil\log_2(n)\rceil$.

Consider the value $n$. We write $n-1$ in binary as $x$, comprising $m$ bits. We know that the first (most significant) bit of $x$ must be 1.

We're going to describe an iterative protocol. In the first step, we start with $|0\rangle^{\otimes m}$, and convert the first qubit to $$ \sqrt{\frac{2^{m-1}}{n}}|0\rangle+\sqrt{\frac{n-2^{m-1}}{n}}|1\rangle. $$ Controlled off the first qubit being 0, we apply Hadamard on all other qubits. This has got all the terms $|0y\rangle$ for $y\in\{0,1\}^{m-1}$ correct. Now we just have to worry about the $|1y\rangle$ terms. If the second bit of $x$ is 1, then we essentially just repeat the first step but for the $m-1$ least significant bits, and controlling every operation off the first qubit being in 1. If the second bit of $x$ is 0, then we move onto the third bit, but now controlling everything off the first qubit being 1 and the second qubit being 0 (except that we don't actually need that control because it's always 0 if the first qubit is 1). We can now just repeat this for the entire sequence.

For example, if $n=14$ ($x=1101$), you'd do something like \begin{align*} |0\rangle^{\otimes 4}&\rightarrow \sqrt{\frac{6}{14}}|1000\rangle+\frac{1}{\sqrt{14}}(|0000\rangle+|0001\rangle+|0010\rangle+|0011\rangle+|0100\rangle+|0101\rangle+|0110\rangle+|0111\rangle) \\ &\rightarrow \sqrt\frac{6}{14}|1\rangle(\sqrt\frac{2}{6}|100\rangle+\frac{1}{\sqrt{6}}(|000\rangle+|001\rangle+|010\rangle+|011\rangle))+\frac{1}{\sqrt{14}}(\ldots) \\ &\rightarrow\sqrt\frac{6}{14}|1\rangle\sqrt\frac{2}{6}|10\rangle\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)+\ldots \end{align*} To see the complexity, we've got to loop over the $m$ bits of $x$, and each step, at worst, we have to perform a multi-controlled not, which can be decomposed in terms of $O(m)$ controlled-nots. In this circuit diagram, I defined $U$ such that $U(x)|0\rangle=x|0\rangle+\sqrt{1-x^2}|1\rangle$. The slices correspond to the stated outputs in the example, and the dashed box hopefully guides the eye about the recursive structure. Note that for the very last gate, $U(1/\sqrt{2})=H$. I should also note that there are some case specific optimisations that can be made (all the gates on the last qubit can be combined as a single, uncontrolled, Hadamard) but that only obfuscates the algorithmic structure.

Answer 2

For large $N$ the most efficient method I am aware of is to prepare a uniform superposition over $2^{\lceil \log_2(N) \rceil}$ values with a bunch of Hadamard gates, then use a perfectly tuned Grover diffusion step to remove the unwanted states between $N$ and $2^{\lceil \log_2(N) \rceil}$. The cost of this approach is $O(\log N + \log 1/\epsilon)$ gates (the $1/\epsilon$ is from arbitrary angle rotations being approximated using a fixed gate set).

This method is explained in Figure 12 of https://arxiv.org/abs/1805.03662. Beware that there is a sign error in the figure. The numerator in the angle calculations should be $L - 2^{\lfloor \log(L)\rfloor}$ instead of $ 2^{\lfloor \log(L)\rfloor} - L$.

Here is a working example in Quirk, preparing a uniform superposition over 100 values. 100 is $25*2^2$, so this really reduces to the $N=25$ case with two $|+\rangle$ qubits. The perfect angle for the diffusion is $\arccos(1 - 16/25)$, where the 25 comes from $N=25$ and 16 is the smallest power of 2 less than $N$.

You can confirm that the construction works by clicking on the image to open quirk, changing the three "25"s in the circuit to "23"s, and seeing that the new output is a uniform superposition up to 4*23 = 92.

Answer 3

I'd have thought your easiest method would be to prepare a uniform superposition of $m=\lceil\log_2 n\rceil$ qubits using hadamard gates. Then introduce an ancilla. You can then compute a function $f(x):\{0,1\}^m\rightarrow\{0,1\}$ for which $\sum_{x\in\{0,1\}^m}=n$. Any such function will do (this is the same marking function that you'd have in Grover's search).

Now, we simply measure the ancilla in the $Z$ basis. If it is in the state $|1\rangle$, you've got the state that you want. If it is in the state $|0\rangle$, you've failed and you have to try again. However, the probability of failure is less than $\frac12$. Thus, on average, you only need two runs to be successful.

As an example, take something like $n=7$. Here, we have $m=3$ and $f(x)$ is just $$ f(x)=\left\{\begin{array}{cc} 0 & x=111 \\ 1 & \text{otherwise} \end{array}\right. $$ This is just a controlled-controlled-controlled-not targetting the ancilla.

I haven't thought it through particularly carefully, but I think you can achieve a marking function $f(x)$ using $O(m^2)$ controlled-nots (because you shouldn't need more than $m$ multi-controlled-nots).