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)?


1 Answer 1


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<N$ 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):

enter image description here

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

enter image description here


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.