# How do you build a circuit to make an equal superposition of $n$ outcomes?

Suppose we start with $$|00...0\rangle$$. We want to build an equal superposition over $$|0\rangle + ... + |n-1\rangle$$.

When $$n=2^m$$ for some $$m$$, I know I can do this using $$H^{\otimes m}$$.

What is the general circuit for this (i.e. in case $$n$$ is not power of 2)?

How to prepare a uniform superposition over a range.

Simple: Repeat until success

The simplest approach is to prepare an $$n$$-qubit quantum integer register $$k$$, where $$n=\lceil \lg_2 N \rceil$$, in the state $$|+\rangle^{\otimes n}$$. That can be done very cheaply using reset gates and Hadamard gates. Then use a comparison operation to measure whether $$k or not. If not, then retry. The main downside of this repeat-until-success approach is that it isn't reversible, and sometimes these sorts of preparation tasks occur inside subroutines where reversibility is needed due to controlling and uncomputing the preparation.

Example repeat-until-success circuit in Quirk, cycling over N=1 to N=127 (technically should only go from 65 to 127 for a 7 qubit system like this):

Flexible: Amplitude Amplification

There is a deterministic reversible circuit with the same cost as the repeat-until-success strategy. You can use a single step of amplitude amplification, with a less-than-N comparison as the oracle, to get to a uniform superposition over the range [0, N). This has a gate count of $$O(\lg N+\lg\frac{1}{\epsilon})$$, where the $$\epsilon$$ comes from how closely you approximate the rotation angle within the amplification.

• Remove any factors of two in $$N$$ by adding a qubit in the $$|+\rangle$$ state. $$N$$ is now odd. Skip the remaining steps if $$N=1$$.
• Let $$\theta = \arccos(1 - 2^{\lfloor \lg_2 N \rfloor} / N)$$.
• Perform one step of amplification. Use a diffusion angle of $$\theta$$. Use $$f(k) = k < N$$ as the oracle.
• The system is now in the desired state.

Example amplification circuit in Quirk, for N=100