# upgrade/update pip library
!pip install --upgrade pip

# install the last official version of the grader from IBM's Qiskit Community
!pip install git+https://github.com/qiskit-community/Quantum-Challenge-Grader.git@main

# import the quantum circuit, Aer,
# and execute instruction
# from the IBM' Qiskit library
from qiskit import QuantumCircuit, Aer, execute

# import the numpy library
import numpy as np

# import the plot histogram function
# from the IBM's Qiskit Visualization module
from qiskit.visualization import plot_histogram

# import the plotting from
# the Matplotlib's Pyplot module
import matplotlib.pyplot as plt

# import the GCD (Greatest Common Divisor)
# from the built-in mathematics module
from math import gcd

# define the function to genera the quantum circuit
# for the Quantum Fourier Transform (QFT) on n qubits
def qft(n):
    
    # creates a quantum circuit with n qubits,
    # implementing the Quantum Fourier Transform (QFT)
    circuit = QuantumCircuit(n)
    
    
    # define the function to perform the Swap gates
    # on the quantum registers of the quantum circuit
    # for the Quantum Fourier Transform (QFT) on n qubits
    def swap_registers( circuit, n ):
        
        # for a number of iterations equal to half of
        # the number of qubits used on the quantum circuit
        # for the Quantum Fourier Transform (QFT)
        for qubit in range( n // 2 ):
            
            # apply the Swap gate between the kth qubit and
            # the (n - k)th qubit on the quantum register defined before
            circuit.swap( qubit, ( n - qubit - 1 ) )
        
        
        # return the quantum circuit with the Swap gates
        # applied on the n qubits of the quantum register,
        # to implement the Quantum Fourier Transform (QFT)
        return circuit
    
    
    # define the function to perform the Controlled-Phase gates
    # on the quantum registers of the quantum circuit
    # for the Quantum Fourier Transform (QFT) on n qubits
    # (it is applied to the first n qubits,
    #  and without the Swap gates performed)
    def qft_rotations( circuit, n ):
       
        # if it is the last opposite iteration
        if n == 0:
            
            # return with the Controlled-Phase gates
            # on the quantum registers of the quantum circuit
            # for the Quantum Fourier Transform (QFT) on n qubits
            # (it is applied to the first n qubits,
            #  and without the Swap gates performed)
            return circuit
        
        
        # iterates on the opposite direction,
        # setting a new nth iteration
        n -= 1
        
        
        # apply the Hadamard gate to the kth qubit,
        # on the quantum register defined before,
        # and iterating on the opposite direction
        circuit.h(n)
        
        
        # for the remaining qubits to consider
        # i the kth opposite iteration
        for qubit in range(n):
            
            # apply the Controlled-Phase gate for
            # the theta angle equal to (pi / 2)^(n - k),
            # with control on the nth qubit and target on the kth qubit
            circuit.cp( ( np.pi / 2 )**( n - qubit ), qubit, n )
        
        
        # call this fuction recursively for
        # the next opposite iteration
        qft_rotations( circuit, n )
    
    
    # perform the Controlled-Phase gates
    # on the quantum registers of the quantum circuit
    # for the Quantum Fourier Transform (QFT) on n qubits
    # (it is applied to the first n qubits,
    #  and without the Swap gates performed)
    qft_rotations( circuit, n )
    
    # perform the Swap gates on the quantum registers of
    # the quantum circuit for the Quantum Fourier Transform (QFT) on n qubits
    swap_registers( circuit, n )
    
    
    # return the quantum circuit with n qubits,
    # implementing the Quantum Fourier Transform (QFT)
    return circuit


# define the function to genera the quantum circuit
# for the Inverse Quantum Fourier Transform (IQFT) on n qubits
def qft_dagger( circuit, n ):

    # note: do not forget to apply again the Swap gates
    #       to peform its inverse operation
    
    # for a number of iterations equal to half of
    # the number of qubits used on the quantum circuit
    # for the Inverse Quantum Fourier Transform (IQFT)
    for qubit in range( n // 2 ):

        # apply the Swap gate between the kth qubit and
        # the (n - k)th qubit on the quantum register defined before
        circuit.swap( qubit, ( n - qubit - 1 ) )
    
    
    # for each number of qubits of the quantum register defined before,
    # to consider in the current jth iteration
    for j in range(n):
        
        
        # for each mth qubit of the quantum register defined before,
        # to consider in the current iteration
        for m in range(j):
            
            # apply the Controlled-Phase gate for
            # the theta angle equal to -pi / ( 2^( j - m ) ),
            # with control on the mth qubit and target on the jth qubit
            qc.cp( -np.pi / float( 2**( j - m ) ), m, j )
            
        
        # apply the Hadamard gate to the jth qubit
        # on the quantum register defined before
        qc.h(j)

# define the size n of the quantum register to
# store the phase information
phase_register_size = 4

# create a quantum circuit with a quantum register
# with n qubits and a classical register with n bits,
# to implement the Quantum Phase Estimation (QPE) for n = 4 qubits
qpe4 = QuantumCircuit( ( phase_register_size + 1 ),
                         phase_register_size )


####################################################

#### insert your code here ####


# define the function to perform the Quantum Hadamard Transform on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE)
def apply_quantum_hadamard_transform( circuit, n ):    
    
    # for each qubit of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE) for n qubits
    for qubit_idx in range(n):
        
        # apply the Hadamard gate to the current ith qubit
        circuit.h(qubit_idx)


# define the function to perform the Controlled-Phase gates on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE),
# as part of the Quantum Fourier Transform (QFT)
def apply_controlled_phases( theta, circuit, n ):
    
    # for each ith step according to
    # the number of n qubits used
    for step in range(n):
        
        # compute the iteration parameter t
        # as a power of 2, according to the current step
        t = 2**step
        
        
        # for each iteration according to
        # the iteration parameter t
        for _ in range(t):

            # apply the Controlled-Phase gate for the theta angle,
            # with control on the ith qubit and target on the last qubit
            circuit.cp( theta, step, n )  


# define the function to perform the Swap gates on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE),
# as part of the Quantum Fourier Transform (QFT)
def apply_swaps( circuit, n ):
    
    # for a number of iterations equal to half of
    # the number of phase counting qubits used
    # on the resepective quantum circuit
    # for the Quantum Fourier Transform (QFT)
    for qubit_idx in range( phase_register_size // 2 ):
         
        # apply the Swap gate between the kth qubit and
        # the (n - k)th qubit on the quantum register defined before
        circuit.swap( qubit_idx, ( n - qubit_idx - 1 ) )
        

# define the function to perform
# the Inverse Quantum Fourier Transform (IQFT) on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE)
def apply_quantum_fourier_transform_inverse( circuit, n ):
    
    # for each qubit on the quantum register
    for j in range(n):
        
        # for each additional mth qubit ranging to
        # the current jth qubit being iterated before
        for m in range(j):
            
            # apply the Controlled-Phase gate for
            # the theta angle equal to -pi / ( 2^( j - m ) ),
            # with control on the mth qubit and target on the jth qubit
            circuit.cp( -np.pi / float( 2**( j - m ) ), m, j )

        # apply the Hadamard gate to the jth qubit (system's qubit)
        circuit.h(j)

        
# define the function to perform a measurement of
# all the n qubits on the quantum register of a quantum circuit,
# and storing the classical outcomes on the n bits of
# the classical register of that same quantum circuit
def measure_all_qubits(circuit, n):
    
    # for each pair of qubits and bits
    for j in range(n):
        
        # measure the current qubit on the quantum register,
        # and stores the classical outcome obtained
        # in the current bit on the classical register
        circuit.measure(j, j)


# define the function to perform the Quantum Phase Estimation (QPE)
# according to a theta angle given, on a quantum circuit of n qubits
def quantum_phase_estimation( theta, circuit, n ):
    
    # perform the Quantum Hadamard Transform on
    # the n qubits of the quantum register of
    # the quantum circuit implementing
    # the Quantum Phase Estimation (QPE)
    apply_quantum_hadamard_transform( circuit, n )
    
    # apply the Pauli-X gate to the last qubit on
    # the quantum register of the quantum circuit of
    # the Quantum Phase Estimation (QPE) 
    circuit.x(n)
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    circuit.barrier()
    
    
    # perform the Controlled-Phase gates on
    # the n qubits of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE),
    # as part of the Quantum Fourier Transform (QFT)
    apply_controlled_phases( theta, circuit, n )
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    circuit.barrier()
    
    # perform the Swap gates on the n qubits of
    # the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE),
    # as part of the Quantum Fourier Transform (QFT)
    apply_swaps( circuit, n )
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    circuit.barrier()
    
    
    # perform the Inverse Quantum Fourier Transform (IQFT) on
    # the n qubits of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE)
    apply_quantum_fourier_transform_inverse( circuit, n )

    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    circuit.barrier()
    
    
    # perform a measurement of all the n qubits on
    # the quantum register of the quantum circuit of
    # the Quantum Phase Estimation (QPE) and storing
    # the classical outcomes on the n bits of
    # the classical register of that same quantum circuit
    measure_all_qubits( circuit, n )

    
####################################################


# define the theta angle to be equal to (2 * pi) / 3
theta = ( 2 * np.pi ) / 3 


# perform the Quantum Phase Estimation (QPE)
# according to the theta angle defined,
# on the quantum circuit of n qubits defined before
quantum_phase_estimation( theta, qpe4, phase_register_size )


# draw the quantum circuit implementing
# the Quantum Phase Estimation (QPE) defined before
qpe4.draw("mpl")

# run this cell to simulate 'qpe4' and
# to plot the histogram of the result

# create the Aer Simulator object
sim = Aer.get_backend("aer_simulator")

# define the number of shots
shots = 20000


# execute the simulation for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation
count_qpe4 = execute( qpe4, sim, shots=shots ).result().get_counts()


# plot the histogram of the result counts of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n = 4 counting qubits
plot_histogram( count_qpe4, figsize=(9,5) )

# submit your answer

# import the grader for the exercise 1 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex1 

# grade the exercise 1 of the lab 3
grade_lab3_ex1( count_qpe4 )

# process the result count data to determine accuracy of
# the estimated phase and grab the highest probability measurement


# define the maximum number of counts which will be obtained
max_binary_counts = 0

# define the maximum binary value which will be obtained
max_binary_val = ""


# for each count obtained from the quantum simulation of
# the Quantum Phase Estimation (QPE)
for key, item in count_qpe4.items():
    
    # if the current number of counts is greater than
    # the current maximum number of counts obtained
    if item > max_binary_counts:
        
        # update the maximum number of counts obtained
        max_binary_counts = item
        
        # update the maximum binary value obtained
        max_binary_val = key

        
#########################################
        

#### your function to convert a binary    ####
#### string to a decimal number goes here ####

# define the function to convert
# a binary string to a decimal number
def bin_to_decimal( binary_string ):
    
    # return a binary string
    # converted to a decimal number
    return int( binary_string, 2 )


# calculate the estimated phase obtained
# from the quantum simulation of
# the Quantum Phase Estimation (QPE)
estimated_phase = ( bin_to_decimal(max_binary_val) / 2**phase_register_size )

# calculate the phase accuracy
# which can be obtained from
# the quantum simulation of
# the Quantum Phase Estimation (QPE)
# with the quantum circuit defined before,
# inverse of the highest power of 2
# (i.e. smallest decimal) this quantum circuit can estimate
phase_accuracy_window = 2**( -phase_register_size )

# submit your answer

# import the grader for the exercise 2 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex2 

# grade the exercise 2 of the lab 3
grade_lab3_ex2( [ estimated_phase, phase_accuracy_window ] )

# import the IBM's Provider from
# the Qiskit's IBM Provider module
from qiskit_ibm_provider import IBMProvider

# import the transpile function from
# the IBM's Qikist Compiler module
from qiskit.compiler import transpile


# create an IBM's Provider object
provider = IBMProvider()


# define the hub for the IBM's Provider
hub = "summer-school-6"

# define the group for the IBM's Provider
group = "group-3"

# define the project for the IBM's Provider
project = "7048813929"


# define the backend's name for the IBM's Provider
backend_name = "ibmq_manila"


# retrieve the backend from the IBM's Provider
backend = provider.get_backend( backend_name, instance=f"{hub}/{group}/{project}" )



##########################################

#### your code goes here ####


# define the initial maximum quantum circuit depth obtained
max_depth = 1e-20

# define the initial minimum quantum circuit depth obtained
min_depth = 1e20


# define the number of trials to transpile/optimize
# the quantum circuit for the Quantum Phase Estimation (QPE) 
num_trials = 10


# for each trial to transpile/optimize the quantum circuit
# for the Quantum Phase Estimation (QPE) 
for _ in range(num_trials):
    
    # transpile/optimize the quantum circuit
    # for the Quantum Phase Estimation (QPE),
    # for the current considering trial
    transpiled_qpe4 = transpile( qpe4, backend, optimization_level=3 )
    
    # retrieve the quantum circuit depth of
    # the transpiled/optimized quantum circuit
    # for the Quantum Phase Estimation (QPE) 
    transpiled_qpe4_depth = transpiled_qpe4.depth()
    
    
    # if the quantum circuit depth of
    # the transpiled/optimized quantum circuit
    # for the Quantum Phase Estimation (QPE)
    # is greater than the current maximum
    # quantum circuit depth obtained 
    if transpiled_qpe4_depth > max_depth:
        
        # update the maximum quantum circuit depth
        # obtained with the current quantum circuit depth
        max_depth = transpiled_qpe4_depth
        
        # update the quantum circuit with the maximum depth
        # with the current quantum circuit transpiled/optimized
        max_depth_qpe = transpiled_qpe4
    
    
    # if the quantum circuit depth of
    # the transpiled/optimized quantum circuit
    # for the Quantum Phase Estimation (QPE)
    # is lower than the current minimum
    # quantum circuit depth obtained 
    if transpiled_qpe4_depth < min_depth:

        # update the minimum quantum circuit depth
        # obtained with the current quantum circuit depth
        min_depth = transpiled_qpe4_depth
        
        # update the quantum circuit with the minimum depth
        # with the current quantum circuit transpiled/optimized
        min_depth_qpe = transpiled_qpe4

        
##########################################

# submit your answer

# import the grader for the exercise 3 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex3

# grade the exercise 3 of the lab 3
grade_lab3_ex3( [ max_depth_qpe, min_depth_qpe ] )

# define the number of shots
#shots = 2000

# OPTIONAL: run the minimum depth quantum circuit for
#           the Quantum Phase Estimation (QPE)

# execute and retrieve the job for the simulation
# for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the minimum quantum circuit depth
#job_min_qpe4 = backend.run( min_depth_qpe, sim, shots=shots )

# print the id of the job of the simulation
# for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the minimum quantum circuit depth
#print( job_min_qpe4.job_id() )


# gather the result counts data

# execute the simulation for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the minimum quantum circuit depth
#count_min_qpe4 = job_min_qpe4.result().get_counts()

# plot the histogram of the result counts of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n = 4 counting qubits,
# and using the minimum quantum circuit depth
#plot_histogram( count_min_qpe4, figsize=(9,5) )

# OPTIONAL: run the maximum depth quantum circuit for
#           the Quantum Phase Estimation (QPE)

# execute and retrieve the job for the simulation
# for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the maximum quantum circuit depth
#job_max_qpe4 = backend.run( max_depth_qpe, sim, shots=shots )

# print the id of the job of the simulation
# for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the maximum quantum circuit depth
#print( job_max_qpe4.job_id() )


# gather the result counts data

# execute the simulation for the Quantum Phase Estimation (QPE),
# with n = 4 counting qubits, and retrieve
# the result counts of this quantum simulation,
# using the maximum quantum circuit depth
#count_max_qpe4 = job_max_qpe4.result().get_counts()

# plot the histogram of the result counts of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n = 4 counting qubits,
# and using the maximum quantum circuit depth
#plot_histogram( count_max_qpe4, figsize=(9,5) )

# define the function to perform the Quantum Hadamard Transform on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE)
def apply_quantum_hadamard_transform( circuit, n ):
    
    # for each qubit of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE) for n qubits
    for qubit_idx in range(n):
        
        # apply the Hadamard gate to the current ith qubit
        circuit.h(qubit_idx)
        

# define the function to perform the Controlled-Phase gates on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE),
# as part of the Quantum Fourier Transform (QFT)
def apply_controlled_phases( theta, circuit, n ):
    
    # for each ith step according to
    # the number of n qubits used
    for step in range(n):
    
        # compute the iteration parameter t
        # as a power of 2, according to the current step
        t = 2**step

        
        # for each iteration according to
        # the iteration parameter t
        for _ in range(t):

            # apply the Controlled-Phase gate for the theta angle,
            # with control on the ith qubit and target on the last qubit
            circuit.cp( theta, step, n )  

            
# define the function to perform the Swap gates on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE),
# as part of the Quantum Fourier Transform (QFT)
def apply_swaps( circuit, n ):
    
    # for a number of iterations equal to half of
    # the number of phase counting qubits used
    # on the resepective quantum circuit
    # for the Quantum Fourier Transform (QFT)
    for qubit_idx in range( phase_register_size // 2 ):
        
        # apply the Swap gate between the kth qubit and
        # the (n - k)th qubit on the quantum register defined before
        circuit.swap( qubit_idx, ( n - qubit_idx - 1 ) )
        

# define the function to perform
# the Inverse Quantum Fourier Transform (IQFT) on
# the n qubits of the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE)
def apply_quantum_fourier_transform_inverse( circuit, n ):
    
    # for each jth qubit on the quantum register
    for j in range(n):
        
        # for each additional mth qubit ranging to
        # the current jth qubit being iterated before
        for m in range(j):
            
            # apply the Controlled-Phase gate for
            # the theta angle equal to -pi / ( 2^( j - m ) ),
            # with control on the mth qubit and target on the jth qubit
            circuit.cp( -np.pi / float( 2**( j - m ) ), m, j )

        
        # apply the Hadamard gate to the jth qubit
        circuit.h(j)


# define the function to perform a measurement of
# all the n qubits on the quantum register of a quantum circuit,
# and storing the classical outcomes on the n bits of
# the classical register of that same quantum circuit
def measure_all_qubits( circuit, n ):
    
    # for each pair of qubits and bits
    for j in range(n):    
        
        # measure the current qubit on the quantum register,
        # and stores the classical outcome obtained
        # in the current bit on the classical register
        circuit.measure(j, j)


# define the function to create a quantum circuit,
# implementing the Quantum Phase Estimation (QPE) on (n + 1) qubits
def qpe_circuit(register_size):
    
    #########################################
    
    #### your code goes here ####
    
    
    # define the theta phase angle to estimate
    theta = 1/7
    
    # create the quantum circuit with a quantum register with (n + 1) qubits
    # and a classical register with n bits, intended to implement
    # the Quantum Phase Estimation (QPE) on n qubits
    qpe = QuantumCircuit( ( register_size + 1 ), register_size )
    
    
    # perform the Quantum Hadamard Transform on
    # the n qubits of the quantum register of
    # the quantum circuit implementing
    # the Quantum Phase Estimation (QPE)
    apply_quantum_hadamard_transform( qpe, register_size )
    
    # apply the Pauli-X gate to the last qubit on
    # the quantum register of the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    qpe.x(register_size)
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    qpe.barrier()
    
    
    # perform the Controlled-Phase gates on
    # the n qubits of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE),
    # as part of the Quantum Fourier Transform (QFT)
    apply_controlled_phases( theta, qpe, register_size )
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    qpe.barrier()
    
    # perform the Swap gates on the n qubits of
    # the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE),
    # as part of the Quantum Fourier Transform (QFT)
    apply_swaps( qpe, register_size )
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    qpe.barrier()
    
    
    # perform the Inverse Quantum Fourier Transform (IQFT) on
    # the n qubits of the quantum register of the quantum circuit
    # implementing the Quantum Phase Estimation (QPE)
    apply_quantum_fourier_transform_inverse( qpe, register_size )
    
    # apply a barrier to the quantum circuit of
    # the Quantum Phase Estimation (QPE)
    qpe.barrier()
    
    
    # perform a measurement of all the n qubits on
    # the quantum register of the quantum circuit of
    # the Quantum Phase Estimation (QPE) and storing
    # the classical outcomes on the n bits of
    # the classical register of that same quantum circuit
    measure_all_qubits( qpe, register_size )
    
    
    # return the quantum circuit, implementing
    # the Quantum Phase Estimation (QPE) on n qubits
    return qpe
    
    #########################################

# run this cell to simulate 'qpe' and
# to plot the histogram of the result

# define several quantum register sizes
# equal to n, allowing to vary them
#reg_size = 4
reg_size = 5
#reg_size = 6
#reg_size = 7
#reg_size = 8

# create a quantum circuit for
# the Quantum Phase Estimation (QPE),
# given the quantum register defined before,
# with n counting qubits
qpe_check = qpe_circuit( reg_size )


# create the Aer Simulator object
sim = Aer.get_backend("aer_simulator")

# define the number of shots
shots = 10000


# execute the simulation for the Quantum Phase Estimation (QPE),
# with n counting qubits, and retrieve its result counts
count_qpe = execute( qpe_check, sim, shots=shots ).result().get_counts()

# plot the histogram of the result counts of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n counting qubits
plot_histogram( count_qpe, figsize=(9,5) )

# process the result count data to determine accuracy of
# the estimated phase and grab the highest probability measurement


# define the maximum number of counts which will be obtained
max_binary_counts = 0

# define the maximum binary value which will be obtained
max_binary_val = ""


# for each count obtained from the quantum simulation of
# the Quantum Phase Estimation (QPE)
for key, item in count_qpe.items():
    
    # if the current number of counts is greater than
    # the current maximum number of counts obtained
    if item > max_binary_counts:
                
        # update the maximum number of counts obtained
        max_binary_counts = item
        
        # update the maximum binary value obtained
        max_binary_val = key

        
#########################################
        

#### your function to convert a binary    ####
#### string to a decimal number goes here ####

# define the function to convert
# a binary string to a decimal number
def bin_to_decimal( binary_string ):
    
    # return a binary string
    # converted to a decimal number
    return int( binary_string, 2 )


# calculate the estimated phase obtained
# from the quantum simulation of
# the Quantum Phase Estimation (QPE)
estimated_phase = ( bin_to_decimal(max_binary_val) / 2**reg_size )

# print the estimated phase obtained
# from the quantum simulation of
# the Quantum Phase Estimation (QPE)
print("Estimated Phase:", estimated_phase)


# calculate the phase accuracy
# which can be obtained from
# the quantum simulation of
# the Quantum Phase Estimation (QPE)
# with the quantum circuit defined before,
# inverse of the highest power of 2
# (i.e. smallest decimal) this quantum circuit can estimate
phase_accuracy_window = 2**( -reg_size )

# print the phase accuracy
# which can be obtained from
# the quantum simulation of
# the Quantum Phase Estimation (QPE)
# with the quantum circuit defined before,
# inverse of the highest power of 2
# (i.e. smallest decimal) this quantum circuit can estimate
print("Phase Accuracy Window:", phase_accuracy_window)


# define the theta phase angle,
# which was pretended to be estimated
theta = 1 / 7

# compute the accuracy of the estimated phase,
# as the distance between the estimated phase 
# and the theta phase angle, which was pretended to be estimated
accuracy_estimated_phase = abs( theta - estimated_phase )

# print the accuracy of the estimated phase,
# as the distance between the estimated phase 
# and the theta phase angle, which was pretended to be estimated
print("Accuracy of the Estimated Phase:", accuracy_estimated_phase)

### put your answer here ###

# to estimate accurately the phase information to be within 2^(-6)
# we need n + 1 = 6 (=) n = 5 qubits to store the phase information
required_register_size = 5

### submit your answer ###

# import the grader for the exercise 4 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex4

# grade the exercise 4 of the lab 3
grade_lab3_ex4( required_register_size )

# create 7 mod 15 unitary operator
# for a quantum circuit
N = 15

# define the number of m qubits required
# for the 7 mod 15 operator to be executed
m = int( np.ceil( np.log2( N ) ) )

# create the quantum circuit with
# a quantum register of m qubits
# to implement the 7 mod 15 unitary operator
U_qc = QuantumCircuit( m )


# apply the Pauli-X gate to all the m qubits of
# the quantum register of the quantum circuit
# implementing the 7 mod 15 unitary operator
U_qc.x( range(m) )


# apply the Swap gate between the 2nd qubit and
# the 3rd qubit on the quantum register of
# the quantum circuit implementing
# the 7 mod 15 unitary operator
U_qc.swap(1, 2)

# apply the Swap gate between the 3rd qubit and
# the 4th qubit on the quantum register of
# the quantum circuit implementing
# the 7 mod 15 unitary operator
U_qc.swap(2, 3)

# apply the Swap gate between the 1st qubit and
# the 4th qubit on the quantum register of
# the quantum circuit implementing
# the 7 mod 15 unitary operator
U_qc.swap(0, 3)


# convert the quantum circuit implementing
# the 7 mod 15 unitary operator to
# a quantum unitary gate 
U = U_qc.to_gate()


# define the name of the 7 mod 15
# unitary operator created before
U.name ="{}Mod{}".format(7, N)

# your code goes here

# print the number of qubits
print("Num. qubits: m =", m);



# define the quantum circuits for the inputs
# |1> = |0001>, |2> = |0010>, and |5> = |0101>


#########################################


# create the a quantum circuit with m qubits,
# for the input state |1> = |0001>
qcirc_input_1 = QuantumCircuit(m)

# apply the Pauli-X gate to
# the 1st qubit of the quantum register of
# the quantum circuit defined before
qcirc_input_1.x(0)

# apply the U gate to all
# the m qubits of the quantum register of
# the quantum circuit defined before
qcirc_input_1.append( U, range(m) )

# measure all the m qubits of
# the quantum register of
# the quantum circuit defined before
qcirc_input_1.measure_all()


#########################################


# create the a quantum circuit with m qubits,
# for input state |2> = |0010>
qcirc_input_2 = QuantumCircuit(m)

# apply the Pauli-X gate to
# the 2nd qubit of the quantum register of
# the quantum circuit defined before
qcirc_input_2.x(1)

# apply the U gate to all
# the m qubits of the quantum register of
# the quantum circuit defined before
qcirc_input_2.append( U, range(m) )

# measure all the m qubits of
# the quantum register of
# the quantum circuit defined before
qcirc_input_2.measure_all()


#########################################


# create the a quantum circuit with m qubits,
# for input state |5> = |0101>
qcirc_input_5 = QuantumCircuit(m)

# apply the Pauli-X gate to
# the 1st qubit of the quantum register of
# the quantum circuit defined before
qcirc_input_5.x(0)

# apply the Pauli-X gate to
# the 3rd qubit of the quantum register of
# the quantum circuit defined before
qcirc_input_5.x(2)

# apply the U gate to all
# the m qubits of the quantum register of
# the quantum circuit defined before
qcirc_input_5.append( U, range(m) )

# measure all the m qubits of
# the quantum register of
# the quantum circuit defined before
qcirc_input_5.measure_all()


#########################################

# run this cell to simulate 'qcirc' and to plot the histogram of the result

# create the Aer Simulator object
sim = Aer.get_backend("aer_simulator")

# define the number of shots
shots = 20000

# save the count data for the input state |1> = |0001>
input_1 = execute(qcirc_input_1, sim, shots=shots).result().get_counts()

# save the count data for the input state |2> = |0010>
input_2 = execute(qcirc_input_2, sim, shots=shots).result().get_counts()

# save the count data for the input state |5> = |0101>
input_5 = execute(qcirc_input_5, sim, shots=shots).result().get_counts()

# submit your answer

# import the grader for the exercise 5 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex5

# grade the exercise 5 of the lab 3
grade_lab3_ex5( [ input_1, input_2, input_5 ] )

# create an unitary quantum circuit
# with a quantum register of m qubits
unitary_circ = QuantumCircuit(m)


#### your code goes here ####

# for each iteration in a range of 2^2 = 4
for _ in range( 2**2 ):
    
    # apply the U gate on all
    # the m qubits on the quantum register
    unitary_circ.append( U, range(m) )

# create a Unitary Simulator object
sim = Aer.get_backend("unitary_simulator")

# execute the quantum simulation of
# an unitary quantum circuit with
# a quantum register of m qubits,
# defined before, retrieving its unitary operator
unitary = execute( unitary_circ, sim ).result().get_unitary()

# submit your answer

# import the grader for the exercise 6 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex6

# grade the exercise 6 of the lab 3
grade_lab3_ex6( unitary, unitary_circ )

# define the function to built a 2^k-Controlled-U gate object,
# which repeats the action of the operator U, 2^k times
def cU_multi(k):
    
    # define the size n of the system's quantum register
    sys_register_size = 4
    
    # create the quantum circuit with n qubits on
    # the system's quantum register, to build
    # a 2^k-Controlled-U gate object
    circ = QuantumCircuit( sys_register_size )
    
    
    # for each iteration ranging until 2^k
    for _ in range(2**k):
        
        # apply the U gate to all the n qubits on
        # the system's quantum register of
        # the quantum circuit to represent
        # the 2^k-Controlled-U gate
        circ.append(U, range(sys_register_size))
    
    
    # convert the operator resulting from the construction of
    # the quantum circuit defined before, to a quantum gate
    U_multi = circ.to_gate()
    
    
    # define the name of the 2^k-Controlled-U gate,
    # as being a "7 Mod 15 gate"
    U_multi.name = "7Mod15_[2^{}]".format(k)
    
    # set this 2^k-Controlled-U gate as multi-qubit gate,
    # depending on a given control qubit
    cU_multi = U_multi.control()
    
    
    # return the 2^k-Controlled-U gate object,
    # which repeats the action of the operator U, 2^k times
    return cU_multi

# define the size m of the quantum register
# for the phase counting of the qubits
phase_register_size = 8

# define the size n of the quantum register
# for the successive applications of
# the 2^k-Controlled-U gate defined before
cu_register_size = 4


# create the Quantum Circuit needed to run
# with m = 8 qubits for the phase counting
# and with n = 4 qubits for the successive
# applications of the 2^k-Controlled-U gate
# defined before, to implement the Shor's Algorithm
# for Factoring, based on Quantum Phase Estimation (QPE)
shor_qpe = QuantumCircuit( ( phase_register_size + cu_register_size ),
                             phase_register_size )


# perform the Quantum Hadamard Transform on
# the m qubits for the phase counting of
# the quantum register of the quantum circuit
# implementing the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
apply_quantum_hadamard_transform( shor_qpe, phase_register_size )

# apply the Pauli-X gate to the last qubit on
# the quantum register of the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.x( phase_register_size )

# apply a barrier to the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.barrier()


# for each kth qubit on the quantum register 
# for the phase counting of the qubits
for k in range( phase_register_size ):
    
    # retrieve the 2^k-Controlled-U gate object,
    # which repeats the action of the operator U,
    # 2^k times, defined before
    cU = cU_multi(k)
    
    # apply the 2^k-Controlled-U gate object,
    # which repeats the action of the operator U,
    # 2^k times, defined before, for the kth iteration,
    # to the quantum circuit to implement
    # the Shor's Algorithm for Factoring,
    # based on Quantum Phase Estimation (QPE)
    shor_qpe.append( cU, [k] + list( range( phase_register_size,
                                            ( phase_register_size + cu_register_size ) ) ) )


# apply a barrier to the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)   
shor_qpe.barrier()

# perform the Swap gates on the n qubits of
# the quantum register of the quantum circuit
# implementing the Quantum Phase Estimation (QPE),
# as part of the Quantum Fourier Transform (QFT),
# required to build the quantum circuit to implement
# the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE) 
apply_swaps(shor_qpe, phase_register_size)

# apply a barrier to the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.barrier()


# perform the Inverse Quantum Fourier Transform (IQFT) on
# the m qubits for the phase counting of
# the quantum register of the quantum circuit
# implementing the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
apply_quantum_fourier_transform_inverse( shor_qpe, phase_register_size )


# apply a barrier to the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.barrier()


# perform a measurement of all
# the m qubits for the phase counting of
# the quantum register of the quantum circuit
# implementing the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.measure( range( phase_register_size ),
                  range( phase_register_size ) )


# draw the quantum circuit implementing
# the quantum circuit to
# implement the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE)
shor_qpe.draw("mpl")

# run this cell to simulate 'shor_qpe' and
# to plot the histogram of the results


# create an Aer Simulator object
sim = Aer.get_backend("aer_simulator")

# define the number of shots
shots = 20000


# execute the quantum simulation for
# the quantum circuit for the Shor's Algorithm,
# based on Quantum Phase Estimation (QPE),
# with n phase counting qubits, and retrieve
# the result counts of this quantum simulation
shor_qpe_counts = execute(shor_qpe, sim, shots=shots).result().get_counts()

# plot the histogram of the result counts of the quantum simulation
# for the quantum circuit for the Shor's Algorithm, based on
# Quantum Phase Estimation (QPE), with n phase counting qubits
plot_histogram( shor_qpe_counts, figsize=(9,5) )

# submit your answer

# import the grader for the exercise 7 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex7

# grade the exercise 7 of the lab 3
grade_lab3_ex7( shor_qpe_counts )

# import the Fraction object
# from the built-in fractions module
from fractions import Fraction


# print the number '0.666',
# as an unlimited Fraction object
print( "Unlimited Fraction(0.666):",
       Fraction(0.666), '\n')

# print the number '0.666',
# as a limited Fraction object
# with the denominator of 15
print( "Limited Fraction(0.666), with a max. denominator of 15:",
       Fraction(0.666).limit_denominator(15) )

# create a list with the estimated phases of the result counts
# obtained from the execution of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n counting qubits
estimated_phases = [ bin_to_decimal(binary_val) / 2**phase_register_size
                     for binary_val in shor_qpe_counts ]

# print the list with the estimated phases of the result counts
# obtained from the execution of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n counting qubits
print( "Estimated Phases:", estimated_phases )


# create a list of with the estimated phases of the result counts
# obtained from the execution of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n counting qubits,
# represented as Fraction objects with the format s/r
shor_qpe_fractions = [ Fraction(estimated_phase).limit_denominator(15)
                       for estimated_phase in estimated_phases ]

# print the list of with the estimated phases of the result counts
# obtained from the execution of the quantum simulation
# for the Quantum Phase Estimation (QPE), with n counting qubits,
# represented as Fraction objects with the format s/r
print( "Estimated Fractions:", shor_qpe_fractions )

# submit your answer

# import the grader for the exercise 8 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex8

# grade the exercise 8 of the lab 3
grade_lab3_ex8( shor_qpe_fractions )

# define the function to create and execute
# the Shor's Algorithm for Factoring,
# based on Quantum Phase Estimation (QPE),
# with k phase counting qubits
def shor_qpe(k):

    # define the co-prime a
    a = 7
    
    # define the number N to factor
    N = 15
    
    # compute the number m of
    # additional qubits required
    m = int( np.ceil( np.log2(N) ) )
        
        
    #################################################
    
    # step 1. Begin a while loop until a nontrivial guess is found
    #### your code goes here ####
    
    # define the boolean flag to determine
    # if a non trivial guess was found, initially as False
    non_trivial_guess_found = False
    
    
    # while no trivial factor guess was found,
    # execute the while loop
    while( not non_trivial_guess_found ):
        
        
        #################################################

        # step 2a. construct a QPE quantum circuit
        #          with m phase counting qubits to guess
        #          the phase phi = s/r, using the function
        #          cU_multi() defined before
        
        
        #### your code goes here ####
        
        # create a quantum circuit for
        # the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # with k phase counting qubits,
        # and additional m qubits for
        # the successive applications of
        # the 2^k-Controlled-U gate defined before
        qc = QuantumCircuit( ( k + m ), k)
        
        
        # perform the Quantum Hadamard Transform on
        # the k phase counting qubits of the respective
        # quantum register of the quantum circuit
        # for the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE)
        apply_quantum_hadamard_transform( qc, k )
        
        # apply a Pauli-X gate to the last
        # phase counting qubit of the respective
        # quantum register of the quantum circuit
        # for the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE)
        qc.x(k)

        # apply a barrier to the quantum circuit for
        # the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # with k phase counting qubits,
        # and additional m qubits for
        # the successive applications of
        # the 2^k-Controlled-U gate defined before
        qc.barrier()
        
        
        # for each kth qubit on the quantum register 
        # for the phase counting of the qubits
        for k_i in range(k):

            # retrieve the 2^k-Controlled-U gate object,
            # which repeats the action of the operator U,
            # 2^k times, defined before
            cU = cU_multi(k_i)
            
            # apply the 2^k-Controlled-U gate object,
            # which repeats the action of the operator U,
            # 2^k times, defined before, for the kth iteration,
            # to the quantum circuit for the Shor's Algorithm
            # for Factoring, based on Quantum Phase Estimation (QPE),
            # with k phase counting qubits, and additional m qubits
            # for the successive applications of
            # the 2^k-Controlled-U gate defined before
            qc.append( cU, [k_i] + list( range( k, ( k + m ) ) ) )

        
        # apply a barrier to the quantum circuit for
        # the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # with k phase counting qubits,
        # and additional m qubits for
        # the successive applications of
        # the 2^k-Controlled-U gate defined before
        qc.barrier()
        
        # perform the Swap gates on the k
        # phase counting qubits of the respective
        # quantum register of the quantum circuit
        # for the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # as part of the Quantum Fourier Transform (QFT)
        apply_swaps( qc, k )

        # apply a barrier to the quantum circuit for
        # the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # with k phase counting qubits,
        # and additional m qubits for
        # the successive applications of
        # the 2^k-Controlled-U gate defined before
        qc.barrier()
        
        
        # perform the Inverse Quantum Fourier Transform (IQFT) on
        # the k phase counting qubits of the respective
        # quantum register of the quantum circuit
        # for the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE)
        apply_quantum_fourier_transform_inverse( qc, k )

        # apply a barrier to the quantum circuit for
        # the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE),
        # with k phase counting qubits,
        # and additional m qubits for
        # the successive applications of
        # the 2^k-Controlled-U gate defined before
        qc.barrier()
        
        
        # perform a measurement of all
        # the k phase counting qubits of the respective
        # quantum register of the quantum circuit
        # for the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE)
        qc.measure( range(k), range(k) )
        
        
        #################################################
        
        
        # step 2b. run the QPE quantum circuit with a single shot,
        #          record the results and convert the estimated phase
        #          bitstring to a decimal format
        
        
        #### your code goes here ####
        
        # create an Aer Simulator object
        sim = Aer.get_backend("aer_simulator")
        
        
        # define the number of shots
        shots = 1
        
        
        # execute the simulation for the Quantum Phase Estimation (QPE),
        # with n counting qubits, and retrieve the result counts
        # obtained from this quantum simulation
        shor_qpe_counts = execute( qc, sim, shots=shots ).result().get_counts()
        
        
        # plot the histogram of the result counts of the quantum simulation
        # for the Quantum Phase Estimation (QPE), with n counting qubits
        plot_histogram( shor_qpe_counts, figsize=(9,5) )
        
        
        # compute the estimated phases from the result counts
        # obtained from the quantum simulation of the quantum circuit
        # implementing the Shor's Algorithm for Factoring,
        # based on Quantum Phase Estimation (QPE)
        estimated_phases = [ bin_to_decimal( binary_val ) / 2**k
                             for binary_val in shor_qpe_counts ]
        
        
        #################################################

        
        # step 3. use the Fraction object to find the guess for r
       
        #### your code goes here ####

        # convert the estimated phase to a fraction s/r format
        fraction_s_r = [ Fraction(estimated_phase).limit_denominator(N)
                         for estimated_phase in estimated_phases ][0]
        
        # retrieve the numerator s and the denominator r
        # from the estimated phase represented as a fraction
        s, r = fraction_s_r.numerator, fraction_s_r.denominator
        
        
        #################################################
        
        
        # step 4. now that r has been found, use the built-in
        #         greatest common divisor function to determine
        #         the guesses for a factor of N
        
        # build the list of guesses for possible non-trivial factors of N
        guesses = [ gcd( a**( r // 2 ) - 1, N ),
                    gcd( a**( r // 2 ) + 1, N ) ]
        
        
        #################################################
        
        
        # step 5. for each guess in guesses, check if
        #         at least one is a non-trivial factor,
        #         i.e., ( ( guess != 1 ) or ( guess != N ) )
        #               and ( N % guess == 0 )
        
        #### your code goes here ####
        
        # for each of the guesses computed before
        for guess in guesses:
            
            # if the current guess is not a trivial factor
            if ( ( ( guess != 1 ) or ( guess != N ) )
                  and ( N % guess == 0 ) ):
                
                # update the boolean flag to determine
                # if a non trivial guess was found, as True
                non_trivial_guess_found = True
                
                # break the current for loop
                break
    
        
    #################################################
    
    # step 6. if a non-trivial factor is found return
    #         the list 'guesses', otherwise
    #         continue the while loop
    
    # return the list of the guesses,
    # containing a non-trivial factor of N
    return guesses
    
    #################################################

# submit your circuit

# import the grader for the exercise 9 of the lab 3
from qc_grader.challenges.qgss_2023 import grade_lab3_ex9

# grade the exercise 9 of the lab 3
grade_lab3_ex9( shor_qpe )

# import the IBM's Qiskit Jupyter Tools
import qiskit.tools.jupyter

# show the table of the IBM's Qiskit version
%qiskit_version_table