# How to prepare a superposed state where its terms are elements of a sequence?

Define the recursive sequence $$x_{i+1} = x_0 x_i \mod 21$$, where $$x_0 = 2$$, and hence $$x_1 = x_0 x_0 = 4$$, and so on, generating the sequence $$[2, 4, 8, 16, 11, 1]$$, where the brackets mean it cycles on forever. This sequence has 6 elements so $$3$$ q-bits suffice to put each of these numbers in a superposition. My objective is to get $$\newcommand{\qr}[1]{\left|#1\right\rangle}$$

$$\qr2 + \qr4 + \qr8 + \qr{16} + \qr{11} + \qr1.$$

Being a superposition, I think I'll have to fill it with other terms until I complete a power of 2, so zeros would be fine:

$$\qr2 + \qr4 + \qr8 + \qr{16} + \qr{11} + \qr1 + \qr0 + \qr0.$$

How can I prepare such state from, say, $$\qr{00000}$$?

• Do you mean $x_{i+1}=x_0x_i\text{ mod }21=x_0^{i+2}\text{ mod }21$ (i.e. without the $f$)? – DaftWullie Jan 18 '19 at 16:03
• Yes, this function doesn't need to be presented recursively as I did and that does indeed help quite a bit here. But, by the way, you should've written $x_{i+1} = x_0 x_i = x_0^{i + 1}$ and not $x_0^{i+2}$. – R. Chopin Jan 19 '19 at 12:31
• So what do you get for $i=-1$? – DaftWullie Jan 19 '19 at 12:51
• I don't understand: $f$ is only defined for $i \geq 0$. Can you clarify? – R. Chopin Jan 21 '19 at 0:46
• Well, that's not stated anywhere. Implicit in your notation is that you want a sequence $x_0,x_0^2,x_0^3,\ldots$ starting from $x_0$. So, if I want to use the stated formula, to get $x_0$, I need $i=-1$. Or, for $x_1=x_0^2$, I need $i=0$. – DaftWullie Jan 21 '19 at 8:08

Specifically, this is essentially a W state, about which there have been several questions in the past. You just need one extra term (effectively $$|32\rangle$$) that you could later change into $$|11\rangle$$, leaving the others untouched.
Let's say I've got a state $$(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|16\rangle+|32\rangle)/\sqrt{6}$$ This is the same as $$(|000001\rangle+|000010\rangle+|000100\rangle+|001000\rangle+|010000\rangle+|100000\rangle)/\sqrt{6}.$$ We do controlled-nots, controlled off the first qubit targetting qubits 3, 5 and 6. This changes $$|100000\rangle$$ into $$|101011\rangle$$. Now we do a controlled-controlled-not controlled by qubits 3 and 5, targetting qubit 1. This changes the $$|101011\rangle$$ into $$|001011\rangle$$ without changing anything else. Thus, we're left with $$|0\rangle(|10000\rangle+|01000\rangle+|00100\rangle+|00010\rangle+|00001\rangle+|01011\rangle)/\sqrt{6},$$ which is the state you want.
More generally, meaning a state of the form $$\frac{1}{\sqrt{r}} \sum_{i=0}^{r-1}|a^i\text{ mod }N\rangle,$$ I advise looking at the order finding algorithm for quantum computers. You're basically talking about preparing one of the eigenvectors of the order finding unitary. While you would like to be able to prepare such a state in order to find the order $$r$$, we don't know how to do that without first finding $$r$$. But, when you've run the order finding algorithm, and it randomly outputs a value of $$s/r$$, the state of the second register is in the eigenvector related to $$s/r$$. $$\frac{1}{\sqrt{r}} \sum_{k=0}^{r-1}e^{-2\pi i k s/r}|a^k\text{ mod }N\rangle$$ Once you've got that, and you know the value $$s/r$$, you should easily be able to compensate for the phases.
• $\newcommand{\qr}[1]{|#1\rangle}$I'm interested in sequences of precisely the form $x_0 x_i \mod N$, so not more generally. This example illustrates the sequence I'm studying. I would love to quickly find the order of $x_0$, but let's leave that for another question. With your observation that we can express the sequence in closed form, I think I can answer the question this way. Using a circuit $U_f$ that implements $f(i) = x_0^{i+1} = 2^{i+1}$, compute $U_f (H^{\otimes 5} \qr{00000})$. This will prepare the superposition that I like, answering the question. What do you think? – R. Chopin Jan 19 '19 at 12:37
• It doesn’t work because you don’t get distinct answers for each $i$ and hence the U that you define is not unitary. – DaftWullie Jan 19 '19 at 12:48