3
$\begingroup$

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}$?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Do you mean $x_{i+1}=x_0x_i\text{ mod }21=x_0^{i+2}\text{ mod }21$ (i.e. without the $f$)? $\endgroup$
    – DaftWullie
    Jan 18, 2019 at 16:03
  • $\begingroup$ 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}$. $\endgroup$
    – R. Chopin
    Jan 19, 2019 at 12:31
  • $\begingroup$ So what do you get for $i=-1$? $\endgroup$
    – DaftWullie
    Jan 19, 2019 at 12:51
  • $\begingroup$ I don't understand: $f$ is only defined for $i \geq 0$. Can you clarify? $\endgroup$
    – R. Chopin
    Jan 21, 2019 at 0:46
  • $\begingroup$ 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$. $\endgroup$
    – DaftWullie
    Jan 21, 2019 at 8:08

1 Answer 1

Reset to default
4
$\begingroup$

Do you want to know about this specific sequence, or more generally?

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ $\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? $\endgroup$
    – R. Chopin
    Jan 19, 2019 at 12:37
  • 1
    $\begingroup$ It doesn’t work because you don’t get distinct answers for each $i$ and hence the U that you define is not unitary. $\endgroup$
    – DaftWullie
    Jan 19, 2019 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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