10.4 Periodicity

Suppose that the input to the $\operatorname { Q F T } , \left| \alpha \right. = \left( \alpha _ { 0 } , \alpha _ { 1 } , \dots , \alpha _ { M - 1 } \right)$ , is such that $\alpha _ { i } = \alpha _ { j }$ whenever $i \equiv j$ mod k, where k is a particular integer that divides M. That is, the array α consists of $M / k$ repetitions of some sequence $( \alpha _ { 0 } , \alpha _ { 1 } , \ldots , \alpha _ { k - 1 } )$ of length k. Moreover, suppose that exactly one of the k numbers $\alpha _ { 0 } , \ldots , \alpha _ { k - 1 }$ is nonzero, say $\alpha _ { j }$ . Then we say that $\left| \alpha \right.$ is periodic with period k and offset $j .$

Figure 10.5 Examples of periodic superpositions.
period 3					···
period 3	0	3	6	9		M-6	M-3
period 4					···
period 4	1		5	9		M-7	M-3

It turns out that if the input vector is periodic, we can use quantum Fourier sampling to compute its period! This is based on the following fact, proved in the next box:

Suppose the input to quantum Fourier sampling is periodic with period $k ,$ for some k that divides M. Then the output will be a multiple of $M / k$ , and it is equally likely to be any of the k multiples of $M / k$

Now a little thought tells us that by repeating the sampling a few times (repeatedly preparing the periodic superposition and doing Fourier sampling), and then taking the greatest common divisor of all the indices returned, we will with very high probability get the number $M / k -$ and from it the period k of the input!

Box: The Fourier transform of a periodic vector

Suppose the vector $| \pmb { \alpha } \rangle = ( \alpha _ { 0 } , \alpha _ { 1 } , \dots , \alpha _ { M - 1 } )$ is periodic with period k and with no offset (that is, the nonzero terms are $\alpha _ { 0 } , \alpha _ { k } , \alpha _ { 2 k } , . . . )$ . Thus,

\left| \boldsymbol {\alpha} \right\rangle = \sum_ {j = 0} ^ {M / k - 1} \sqrt {\frac {k}{M}} \left| j k \right\rangle .

We will show that its Fourier transform $\vert \beta \rangle = ( \beta _ { 0 } , \beta _ { 1 } , \dots , \beta _ { M - 1 } )$ is also periodic, with period $M / k$ and no offset.

Claim $\begin{array} { r } { | \beta \rangle = \frac { 1 } { \sqrt { k } } \sum _ { j = 0 } ^ { k - 1 } \left| \frac { j M } { k } \right. } \end{array}$

Proof

In the input vector, the coefficient $\alpha _ { \ell }$ is $\sqrt { k / M }$ if k divides $\ell ,$ and is zero otherwise. We can plug this into the formula for the jth coefficient of $| \beta \rangle$

\beta_ {j} = \frac {1}{\sqrt {M}} \sum_ {\ell = 0} ^ {M - 1} \omega^ {j \ell} \alpha_ {\ell} = \frac {\sqrt {k}}{M} \sum_ {i = 0} ^ {M / k - 1} \omega^ {j i k}.

The summation is a geometric series, $1 + \omega ^ { j k } + \omega ^ { 2 j k } + \omega ^ { 3 j k } + \cdot \cdot \cdot$ , containing $M / k$ terms and with ratio $\omega ^ { j k }$ (recall that $\omega$ is a complex Mth root of unity). There are two cases. If the ratio is exactly 1, which happens if $j k \equiv 0$ mod $M$ , then the sum of the series is simply the number of terms. If the ratio isn’t 1, we can apply the usual formula for geometric series to find that the sum is $\begin{array} { r } { \frac { 1 - \omega ^ { j k ( M / k ) } } { 1 - \omega ^ { j k } } = \frac { 1 - \omega ^ { M j } } { 1 - \omega ^ { j k } } = 0 } \end{array}$

Therefore $\beta _ { j }$ is $1 / \sqrt { k }$ if M divides $j k _ { ; }$ , and is zero otherwise.

More generally, we can consider the original superposition to be periodic with period $k ,$ but with some offset $l < k :$

\left| \boldsymbol {\alpha} \right\rangle = \sum_ {j = 0} ^ {M / k - 1} \sqrt {\frac {k}{M}} \left| j k + l \right\rangle .

Then, as before, the Fourier transform $| \beta \rangle$ will have nonzero amplitudes precisely at multiples of $M / k$

Claim $\begin{array} { r } { | \beta \rangle = \frac { 1 } { \sqrt { k } } \sum _ { j = 0 } ^ { k - 1 } \omega ^ { l j M / k } | \frac { j M } { k } \rangle } \end{array}$

The proof of this claim is very similar to the preceding one (Exercise10.5).

We conclude that the QFT of any periodic superposition with period k is an array that is everywhere zero, except at indices that are multiples of $M / k ,$ and all these k nonzero $c o e f f \it$ cients have equal absolute values. So if we sample the output, we will get an index that is a multiple of $M / k _ { : }$ , and each of the k such indices will occur with probability $1 / k .$

Let’s make this more precise.

Lemma

Suppose s independent samples are drawn uniformly from

0, \frac {M}{k}, \frac {2 M}{k}, \ldots , \frac {(k - 1) M}{k}.

Then with probability at least $1 - k / 2 ^ { s }$ , the greatest common divisor of these samples is $M / k .$

Proof

The only way this can fail is if all the samples are multiples of $j \cdot M / k$ , where $j$ is some integer greater than 1. So, fix any integer $j \geq 2$ . The chance that a particular sample is a multiple of $\dot { \mathrm { ~ \it ~ j M / k ~ } }$ is at most $1 / j \leq 1 / 2 ;$ and thus the chance that all the samples are multiples of $j M / k$ is at most $1 / 2 ^ { s }$

So far we have been thinking about a particular number $j ;$ the probability that this bad event will happen for some $j \leq k$ is at most equal to the sum of these probabilities over the different values of ${ \mathrm { ~ . ~ } } j .$ , which is no more than $k / 2 ^ { s }$ .

We can make the failure probability as small as we like by taking s to be an appropriate multiple of log M.