Let be the function

We will try to find an such that . If is even, we obtain a nontrivial square root. In particular, by the given definition, is a periodic function with period . For that reason, if we find the period of , we will find a nontrivial square root candidate. Then, we define an operator that acts as and apply period finding to obtain the period (so is the encoding of in the form of a quantum gate).

The complete algorithm is illustrated in the following diagram in which we start by taking a random number :

As we can see, there are three questions to be answered in the algorithm. Let's code up some functions that answer them in this first exercise:

  • is_coprime: receives two integers and returns True if they are coprime or False otherwise.
  • is_odd: given an integer returns True if it is odd and False otherwise.
  • is_not_one: given and , determine if . Return False if they are equal.
Hint.

The value of is a positive integer. How can we express as a positive integer if we are working modulo ?

or to submit your code

To interact with codercises, please switch to a larger screen size.

Learning Objectives:

  • Define the relationship between factoring and period finding.
  • Describe the sequential structure of the Shor's algorithm.