# What are the interesting spikes in this after-QFT graph (page 241) of Programming Quantum Computers?

I'm reading Programming Quantum Computers trying to understand Shor's algorithm. I learned there that we prepare a state $$|x^i \bmod N\rangle$$, then apply the QFT to this state. The QFT changes the amplitudes from a uniform superposition to large amplitudes evenly spaced out by the period of $$x^i \bmod N$$. For example, here's a graph of the amplitudes after applying the QFT with $$N = 35$$. That's on page 241. The book says there are 12 spikes evenly spaced. I see a lot more than 12 spikes evenly spaced. Should I count just the highest ones and stop when I've counted 12? But isn't that subjective? How would I figure out that the number is really 12 from just looking at this graph without knowing the right answer? (In other words, how do I get 12 out of this?)

• @MariiaMykhailova, you can probably answer this. And --- thanks --- if you do! – user14021 Dec 5 '20 at 14:53
• You're right to count the local maxima. And you're right that it's subjective, but the point is that if you run the modular exponentiation and the QFT, say, $k$ times, you'll get $x_1, x_2,\ldots x_k$, with each $x_i$ likely corresponding to one of the local maxima. You can feed these to the classical parts of the algorithm. – Mark S Dec 5 '20 at 16:13
• That makes some sense, but it's not clear to me still. By the way, I know the continued fraction algorithm, but it's not clear how to use it to get the period here yet. I asked a question on this. Perhaps you could answer it. Thanks! – user14021 Dec 5 '20 at 16:53

## 1 Answer

Looking at the graphs you've reproduced, the left graph shows the evaluation of $$2^x\bmod 35$$ for $$x\in\{0,\dots 63\}$$ while the right graph illustrates the amplitude of the discrete Fourier transform for $$\hat{x}\in\{0,\dots 63\}$$. The comment that there are "12 evenly spaced spikes" indicates that the local maxima of the right graph repeat every $$64/12=5.33$$ values.

You are correct, you do not have access to $$\hat{x}$$ in a manner that lets you observe this periodicity in $$\hat{x}$$ immediately; however, what you do have access to is a way to sample $$\hat{x}_i$$ for multiple $$i$$ in a manner that returns $$\hat{x}_i$$ with probability given by the (square of the) height of the respective $$\hat{x}_i$$.

For example, if you were to run the modular exponentiation (left graph) followed by the QFT (right graph), and sample the first register, you are likely to get a value such as $$0$$ with higher probability than $$5$$, with higher probability than $$32$$, with higher probability than $$11$$, with higher probability than $$6$$, etc.

From these respective samplings of $$\hat{x}_i$$, you can run the classical portions (the continued fraction portion) of Shor's algorithm to deduce that, indeed, there were 12 evenly spaced spikes in $$\hat{x}$$, giving you the period of $$12$$ in $$2^x\bmod 35$$. There are a lot of details that I'm forgetting but the point is that you use the samples from your QFT as inputs to this classical portion.