I'm curious about how to form arbitrary-sized uniform superpositions, i.e., $$\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\vert x\rangle$$ for $N$ that is not a power of 2.

If this is possible, then one can use the inverse of such a circuit to produce $\sqrt{p}\vert 0\rangle+\sqrt{1-p}\vert 1\rangle$ (up to some precision). Kitaev offers a method for the reverse procedure, but as far as I can tell there is no known method to do one without the other.

Clearly such a circuit is possible, and there are lots of general results on how to asymptotically make any unitary I want, but it seems like a massive headache to distill those results into this one simple, specific problem.

Is there a known, efficient, Clifford+T circuit that can either produce arbitrary uniform superpositions or states like $\sqrt{p}\vert 0\rangle+\sqrt{1-p}\vert 1\rangle$?

  • 1
    $\begingroup$ what do you mean by "efficient" in regards to producing $\sqrt{p}|0\rangle+\sqrt{1-p}|1\rangle$ given that there's no scaling involved in such a question $\endgroup$ – DaftWullie Feb 8 '19 at 12:08
  • $\begingroup$ The scaling would be fidelity with the required state, since we likely can't produce exactly the right state. Can we get $\epsilon$ close with only $O(\log(1/\epsilon))$ gates, say? $\endgroup$ – Sam Jaques Mar 12 '19 at 9:21
  • $\begingroup$ Yes: arxiv.org/abs/1212.6964 (don't ask me how it works!) $\endgroup$ – DaftWullie Mar 12 '19 at 9:49
  • 1
    $\begingroup$ @SamJaques I had a similar question, quantumcomputing.stackexchange.com/questions/12104/… $\endgroup$ – Condo Mar 31 at 15:35
  • 1
    $\begingroup$ @SamJaques yeah! and as you might already know the Ross-Sellingers heuristic algorithm will get you a short gate sequence (length $O(\log(1/\epsilon)$) for basically any precision $\epsilon$ with expected runtime $O(poly(log(1/\epsilon))$. $\endgroup$ – Condo Apr 3 at 16:12

As long as you want to set arbitrary states for a single qubit, like in your example, the solution is straightforward and it makes use of standard 2x2 $R_y$ gate. In there if you set

$\theta = 2\arctan(\sqrt{1-p}/\sqrt{p})$

and apply $R_y(\theta)$ in the form $$ \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2)\\ \sin(\theta/2) & \cos(\theta/2) \end{pmatrix} $$

to an input qubit in superimposed state (i.e. passed through a H gate), you get what you're looking for.

Of course things get more complicated in case you want to set an arbitrary state over a qubit register of size > 1. In that case there are algorithms like Ventura's one (Initializing the Amplitude Distribution of a Quantum State) which can do it with polynomial complexity.

  • $\begingroup$ Sure, but is there a way to construct $R_y(\theta)$ for arbitrary $\theta$ out of Clifford+T? Or do we just assume a gate set that includes $R_y(\theta)$ for all $\theta$? Is this realistic; if we can do noisy arbitrary rotations, can we distill them? $\endgroup$ – Sam Jaques Feb 8 '19 at 13:35
  • $\begingroup$ I think the "Is this realistic" depends on the level at which you're computing. If you're computing on actual physical qubits, you probably have these arbitrary rotations available. If you're using logical qubits, such as in a fault-tolerant computation, you probably don't have them available. $\endgroup$ – DaftWullie Feb 8 '19 at 13:44
  • $\begingroup$ So in all the algorithms intended for fault-tolerant computations that depend on creating arbitrary-sized superpositions, what are they supposed to do? $\endgroup$ – Sam Jaques Feb 8 '19 at 20:16
  • $\begingroup$ Well, Solovay–Kitaev tells you that you can produce a gate $R_y(\theta)$ for any $\theta$ with precision $\varepsilon$ with $\log(1/\epsilon)$ gates, so even logical qubits are not an issue. $\endgroup$ – Léo Colisson Mar 18 '19 at 12:35
  • $\begingroup$ @LéoColisson actually Solovay-Kitaev only gets you a gate sequence of length $O(\log^c(1/\epsilon)$ for $c>1$, it's not until the number-theoretic approximation algorithms like Ross-Sellinger that we get gate sequences of length $O(\log(1/\epsilon)$. $\endgroup$ – Condo Apr 3 at 16:17

I did not thought much about that issue, so my answer may not be the best one, but it has the advantage of being quite simple to understand, it is exact even if you restrict yourself to Clifford+T, and can be generalized to more complicated relations. On the other side, this is not a unitary process because you need to repeat it a polynomial number of times until you get your expected states (see other answers if you want to have a unitary process).

Let $k = \lceil\log N\rceil$ be the smallest number of bits used to represent $N$. Then, you create the state $$\sum_{x =0}^{2^k-1} |x\rangle$$ by applying $k$ Hadamard gates on $k$ states initialized to $|0\rangle$. Then, if we define $f(x) = 1$ iff $x < N$, and $f(x)=0$ otherwise (here you can put any relation you like depending on the states you are interested in, you just want to have a constant fraction of $x$ such that $f(x)=1$ to ensure the algorithm is efficient, which is the case here because at least half of the $x$ have this property by definition of $k$). Then, you add one auxiliary qubit, and you apply the unitary associated to $f$ (which is $U_f |x\rangle|b\rangle =|x\rangle|b \oplus f(x)\rangle$ and can be done with Clifford+T operations) in order to obtain the state: $$\sum_{x=0}^{2^k-1}|x\rangle |f(x)\rangle$$ Then, you measure this second register. If you obtain a $1$, the state you obtain is: $$\sum_{x \in \{x \mid f(x)=1\}} |x\rangle = \sum_{x = 0}^{N-1} |x\rangle$$ (so you have the expected state) Otherwise, you start again from scratch (the probability to obtain the expected state depends on the fraction of $x$ such that $f(x) = 1$. In our case, this is lower bounded by $1/2$ by definition of $k$ so you need to repeat it only a few times before you succeed)

  • $\begingroup$ In other words, if $N=2^n+d$ then you can do a Hadamard transform on $n+1$ qubits; you can evaluate in an ancilla register whether your state so constructed is $\gt 2^n+d$ and post-select to throw away when this happens? $\endgroup$ – Mark S Apr 3 at 22:24
  • $\begingroup$ Yes exactly. Note that you can test if a state is smaller than $N$ by doing a few AND/OR on the most significant bits: If I denote by $x_i$ the $i$-th bit of $x$, it gives something like $x_0 = 0$ or $(x_0 = 1 $ and $x_1 = 0$) or $(x_0 = 1$ and $x_1 = 1$ and $x_1 = 0$)... Then, you need to implement the Unitary that corresponds to that circuit. $\endgroup$ – Léo Colisson Apr 4 at 9:05
  • $\begingroup$ This is nice and I can imagine very useful in certain contexts, though there are other contexts (like the diffusion operator in Grover's algorithm or quantum walks) where we need to apply the adjoint. With the measurement, I don't see how this can be done. $\endgroup$ – Sam Jaques Apr 12 at 16:34

I'm curious about how to form arbitrary-sized uniform superpositions [...] for $N$ that is not a power of 2.

In https://arxiv.org/abs/1805.03662 it's explained how to do this by using a single perfectly-tuned round of amplitude amplification from an easily-solved nearby $N^\prime$ that is a power of 2.

uniform superposition

Example Quirk Circuit

enter image description here

You only need a single round because the overlap between the desired state and the nearby easily prepared state is so large. Major advantages of this construction are that 1) it always succeeds (don't need to retry until success) and 2) it is reversible.

You probably noticed the uniform prep circuit I gave contains an arbitrary rotation with a weird angle. Since your ultimate goal was to avoid synthesizing such a rotation, maybe it's not so satisfying to you as an answer!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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