Chapter 9, Shor’s Algorithm

1. We start by finding values of 3n % 14:


Next, we calculate the following:



When we calculate 14/13, we find that it isn’t an integer. But 14/2 = 7. So, 14 = 2·7.

2. We start by finding values of 2n % 35:


Next, we calculate the following:



When we calculate 35/13 and 35/3, we find that these aren’t integers. But 35/5 = 7. So, 35 = 5·7.

3. Dividing 71 by 8 gives us 8 with a remainder of 7. So, is the same as . According to Figures 9.9 and 9.13, is equal to .
4. The QFT and QFT† matrices are shown here:

5. The 2 × 2 QFT matrix is the Hadamard matrix because the second roots of unity are 1 and -1.
6. The missing values are shown here:
   
7. In the coprime powers sequence for 22 (with coprime 3), the period is 5. But 5 isn’t divisible by 2. You can’t find 35/2 + 1 or 35/2 &...