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 ?

def is_coprime(a, N):
"""Determine if two numbers are coprime.

Args:
a (int): First number to check if is coprime with the other.
N (int): Second number to check if is coprime with the other.

Returns:
bool: True if they are coprime numbers, False otherwise.
"""

##################
# YOUR CODE HERE #
##################


def is_odd(r):
"""Determine if a number is odd.

Args:
r (int): Integer to check if is an odd number.

Returns:
bool: True if it is odd, False otherwise.
"""

##################
# YOUR CODE HERE #
##################


def is_not_one(x, N):
"""Determine if x is not +- 1 modulo N.

Args:
N (int): Modulus of the equivalence.

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.