<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <img src="../../../images/qiskit-heading.png" alt="Note
Step1:  We then use QISKit to program the algorithm.
Step2:  The qfa_algorithm function returns the Quantum Circuit qfaCircuit.
Experiment with Simulators
We can run the above circuit on the simulator.
Step3:  Insert your own parameters and try even larger prime numbers.
Step4:  Drawing the circuit of the QFA
Below is the snapshop of the QFA for reading the bitstring of length $3$. It can be seen that there are independent QFAs each of which performs $Y$ rotation for $3$ times.
Step5:  The Algorithm for Log(Log(p)) Qubits
The algorithm is quite simple as follows.
1. Prepare a quantum register for $ log(log(p)) + 1 $ qubits initialized to zero. The $ log(log(p))$ qubits will act as your control bits and the 1 extra will act as your target bit. Also prepare a classical register for 1 bit to measure the target. 
$$ |0\ldots 0\rangle |0\rangle  $$ 
2. Hadamard the control bits to put them in a superposition so that we can perform multiple QFA's at the same time.
3. For each of $s $ states in the superposition, we can perform an individual QFA with the control qubits acting as the random integer $ k $ from the previous algorithm. Thus, we need $ n $ values from $ 1... log(p)$ for $ k $. For each letter $ i $ in the string, we perform a controlled y-rotation on the target qubit, where $ \theta $ is initially zero and $ \Phi $ is the angle of rotation for each unitary. $$ \Phi = \frac{2 \pi k_{s}}{p} $$
4. The target qubit in the final state
Step6:  The qfa_algorithm function returns the Quantum Circuit control_qfaCircuit.
Experiment with Simulators
We can run the above circuit on the simulator.
Step7:  Drawing the circuit of the QFA
Below is the snapshot of the QFA for reading the bitstring of length $3$. It can be seen that there is a superposition of QFAs instead of independent QFAs.
Step8:  Experimenting with Real Devices
Real-device backends have errors and if the above QFAs are executed on the noisy backends, errors in rejecting strings that should have been accepted can happen. Let us see how well the real-device backends can realize the QFAs. 
Let us look an example when the QFA should reject the bitstring because the length of the bitstring is not divisible by the prime number.
Step9:  In the above, we can see that the probability of observing "1" is quite significant. Let us see how the circuit looks like.
Step10:  Now, let us see what happens when the QFAs should accept the input string.
Step11:  The error of rejecting the bitstring is equal to the probability of observing "1" which can be checked from the above histogram. We can see that the noise of real-device backends prevents us to have a correct answer. It is left as future work on how to mitigate errors of the backends in the QFA models.
<ASSISTANT_TASK:>
Python Code:
# useful additional packages 
import random
import math
from sympy.ntheory import isprime
# importing QISKit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import Aer, IBMQ, execute
from qiskit.wrapper.jupyter import *
from qiskit.backends.ibmq import least_busy
from qiskit.tools.visualization import matplotlib_circuit_drawer as circuit_drawer
from qiskit.tools.visualization import plot_histogram, qx_color_scheme
IBMQ.load_accounts()
sim_backend = Aer.get_backend('qasm_simulator')
device_backend = least_busy(IBMQ.backends(operational=True, simulator=False))
device_coupling = device_backend.configuration()['coupling_map']
Explanation: <img src="../../../images/qiskit-heading.png" alt="Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook" width="500 px" align="left">
Comparing Classical and Quantum Finite Automata (QFA)
Finite Automaton has been a mathematical model for computation since its invention in the 1940s. The purpose of a Finite State Machine is to recognize patterns within an input taken from some character set and accept or reject the input based on whether the pattern defined by the machine occurs in the input. The machine requires a list of states, the initial state, and the conditions for each transition from state to state. Such classical examples are vending machines, coin-operated turnstiles, elevators, traffic lights, etc. 
In the classical algorithm, the sequence begins in the start state, and will only make a transition if the next character in the input string matches the label on the transition from the current to the next state. The machine will continue making transitions on each input character until no move is possible. The string will be accepted if its final state is in the accept state and will be rejected if its final state is anywhere else. 
As for Quantum Finite Automata (QFA), the machine works by accepting a finite-length string of letters from a finite alphabet and utilizing quantum properties such as superposition to assign the string a probability of being in either the accept or reject state. 
Contributors
Kaitlin Gili, Rudy Raymond
Prime Divisibility Algorithm
Let's say that we have a string with $ a^i $ letters and we want to know whether the string is in the language $ L $ where $ L $ = {$ a^i $ | $ i $ is divisble by $ p $} and $ p $ is a prime number. If $ i $ is divisible by $ p $, we want to accept the string into the language, and if not, we want to reject it. 
$|0\rangle $ and $ |1\rangle $ serve as our accept and reject states. 
Classically, this algorithm requires a minimum of $ log(p) $ bits to store the information, whereas the quantum algorithm only requires $ log(log(p)) $ qubits. For example, using the highest known prime integer, the classical algorithm requires a minimum of 77,232,917 bits, whereas the quantum algorithm only requires 27 qubits. 
Introduction <a id='introduction'></a>
The algorithm in this notebook follows that in Ambainis et al. 1998. We assume that we are given a string and a prime integer. If the user does not input a prime number, the output will be a ValueError. First, we demonstrate a simpler version of the quantum algorithm that uses $ log(p) $ qubits to store the information. Then, we can use this to more easily understand the quantum algorithm that requires only $ log(log(p)) $ qubits.
The Algorithm for Log(p) Qubits
The algorithm is quite simple as follows.
1. Prepare quantum and classical registers for $ log(p) $ qubits initialized to zero. 
$$ |0\ldots 0\rangle $$ 
2. Prepare $ log(p) $ random numbers k in the range {$ 1 $... $ p-1 $}. These numbers will be used to decrease the probability of a string getting accepted when $ i $ does not divide $ p $. 
3. Perform a number of $ i $ Y-Rotations on each qubit, where $ \theta $ is initially zero and $ \Phi $ is the angle of rotation for each unitary. $$ \Phi = \frac{2 \pi k}{p} $$
4. In the final state: 
$$ \cos \theta |0\rangle + \sin \theta |1\rangle $$
$$ \theta = \frac{2 \pi k} p {i} $$
5. Measure each of the qubits in the classical register. If $ i $ divides $ p $, $ \cos \theta $ will be one for every qubit and the state will collapse to $ |0\rangle $ to demonstrate an accept state with a probability of one. Otherwise, the output will consist of a small probability of accepting the string into the language and a higher probability of rejecting the string.
The Circuit <a id="circuit"></a>
We now implement the QFA Prime Divisibility algorithm with QISKit by first preparing the environment.
End of explanation
#Function that takes in a prime number and a string of letters and returns a quantum circuit
def qfa_algorithm(string, prime):
    if isprime(prime) == False:
        raise ValueError("This number is not a prime") #Raises a ValueError if the input prime number is not prime
    else:
        n = math.ceil((math.log(prime))) #Rounds up to the next integer of the log(prime)
        qr = QuantumRegister(n) #Creates a quantum register of length log(prime) for log(prime) qubits
        cr = ClassicalRegister(n) #Creates a classical register for measurement 
        qfaCircuit = QuantumCircuit(qr, cr) #Defining the circuit to take in the values of qr and cr
        for x in range(n): #For each qubit, we want to apply a series of unitary operations with a random int
            random_value = random.randint(1,prime - 1) #Generates the random int for each qubit from {1, prime -1}
            for letter in string: #For each letter in the string, we want to apply the same unitary operation to each qubit
                qfaCircuit.ry((2*math.pi*random_value) / prime, qr[x]) #Applies the Y-Rotation to each qubit 
            qfaCircuit.measure(qr[x], cr[x]) #Measures each qubit 
        return qfaCircuit #Returns the created quantum circuit
Explanation: We then use QISKit to program the algorithm.
End of explanation
#A function that returns a string saying if the string is accepted into the language or rejected
def accept(parameter):
    states = list(result.get_counts(parameter))
    for s in states:
        for integer in s:
            if integer == "1":
                return "Reject: the string is not accepted into the language"
    return "Accept: the string is accepted into the language"
Explanation: The qfa_algorithm function returns the Quantum Circuit qfaCircuit.
Experiment with Simulators
We can run the above circuit on the simulator.
End of explanation
range_lower = 0
range_higher = 36
prime_number = 11
for length in range(range_lower,range_higher):
    params = qfa_algorithm("a"* length, prime_number)
    job = execute(params, sim_backend, shots=1000)
    result = job.result()
    print(accept(params), "\n", "Length:",length," " ,result.get_counts(params))
Explanation: Insert your own parameters and try even larger prime numbers.
End of explanation
circuit_drawer(qfa_algorithm("a"* 3, prime_number), style=qx_color_scheme())
Explanation: Drawing the circuit of the QFA
Below is the snapshop of the QFA for reading the bitstring of length $3$. It can be seen that there are independent QFAs each of which performs $Y$ rotation for $3$ times.
End of explanation
#Function that takes in a prime number and a string of letters and returns a quantum circuit
def qfa_controlled_algorithm(string, prime):
    if isprime(prime) == False:
        raise ValueError("This number is not a prime") #Raises a ValueError if the input prime number is not prime
    else:
        n = math.ceil((math.log(math.log(prime,2),2))) #Represents log(log(p)) control qubits 
        states = 2 ** (n) #Number of states that the qubits can represent/Number of QFA's to be performed 
        qr = QuantumRegister(n+1) #Creates a quantum register of log(log(prime)) control qubits + 1 target qubit
        cr = ClassicalRegister(1) #Creates a classical register of log(log(prime)) control qubits + 1 target qubit
        control_qfaCircuit = QuantumCircuit(qr, cr) #Defining the circuit to take in the values of qr and cr
        for q in range(n): #We want to take each control qubit and put them in a superposition by applying a Hadamard Gate
            control_qfaCircuit.h(qr[q])
        for letter in string: #For each letter in the string, we want to apply a series of Controlled Y-rotations
            for q in range(n):  
                control_qfaCircuit.cu3(2*math.pi*(2**q)/prime, 0, 0, qr[q], qr[n]) #Controlled Y on Target qubit 
        control_qfaCircuit.measure(qr[n], cr[0]) #Measure the target qubit  
        return control_qfaCircuit #Returns the created quantum circuit  
Explanation: The Algorithm for Log(Log(p)) Qubits
The algorithm is quite simple as follows.
1. Prepare a quantum register for $ log(log(p)) + 1 $ qubits initialized to zero. The $ log(log(p))$ qubits will act as your control bits and the 1 extra will act as your target bit. Also prepare a classical register for 1 bit to measure the target. 
$$ |0\ldots 0\rangle |0\rangle  $$ 
2. Hadamard the control bits to put them in a superposition so that we can perform multiple QFA's at the same time.
3. For each of $s $ states in the superposition, we can perform an individual QFA with the control qubits acting as the random integer $ k $ from the previous algorithm. Thus, we need $ n $ values from $ 1... log(p)$ for $ k $. For each letter $ i $ in the string, we perform a controlled y-rotation on the target qubit, where $ \theta $ is initially zero and $ \Phi $ is the angle of rotation for each unitary. $$ \Phi = \frac{2 \pi k_{s}}{p} $$
4. The target qubit in the final state: 
$$ \cos \theta |0\rangle + \sin \theta |1\rangle $$
$$ \theta = \sum_{s=0}^n \frac{2 \pi k_{s}} p {i} $$
5. Measure the target qubit in the classical register. If $ i $ divides $ p $, $ \cos \theta $ will be one for every QFA and the state of the target will collapse to $ |0\rangle $ to demonstrate an accept state with a probability of one. Otherwise, the output will consist of a small probability of accepting the string into the language and a higher probability of rejecting the string.
The Circuit <a id="circuit"></a>
We then use QISKit to program the algorithm.
End of explanation
for length in range(range_lower,range_higher):
    params = qfa_controlled_algorithm("a"* length, prime_number)
    job = execute(params, sim_backend, shots=1000)
    result = job.result()
    print(accept(params), "\n", "Length:",length," " ,result.get_counts(params))
Explanation: The qfa_algorithm function returns the Quantum Circuit control_qfaCircuit.
Experiment with Simulators
We can run the above circuit on the simulator.
End of explanation
circuit_drawer(qfa_controlled_algorithm("a"* 3, prime_number), style=qx_color_scheme())
Explanation: Drawing the circuit of the QFA
Below is the snapshot of the QFA for reading the bitstring of length $3$. It can be seen that there is a superposition of QFAs instead of independent QFAs.
End of explanation
prime_number = 3
length = 2          # set the length so that it is not divisible by the prime_number
print("The length of a is", length, " while the prime number is", prime_number)
qfa1 = qfa_controlled_algorithm("a"* length, prime_number)
%%qiskit_job_status
HTMLProgressBar()
job = execute(qfa1, backend=device_backend, coupling_map=device_coupling, shots=100)
result = job.result()
plot_histogram(result.get_counts())
Explanation: Experimenting with Real Devices
Real-device backends have errors and if the above QFAs are executed on the noisy backends, errors in rejecting strings that should have been accepted can happen. Let us see how well the real-device backends can realize the QFAs. 
Let us look an example when the QFA should reject the bitstring because the length of the bitstring is not divisible by the prime number.
End of explanation
circuit_drawer(qfa1, style=qx_color_scheme())
Explanation: In the above, we can see that the probability of observing "1" is quite significant. Let us see how the circuit looks like.
End of explanation
print_number = length = 3 # set the length so that it is divisible by the prime_number
print("The length of a is", length, " while the prime number is", prime_number)
qfa2 = qfa_controlled_algorithm("a"* length, prime_number)
%%qiskit_job_status
HTMLProgressBar()
job = execute(qfa2, backend=device_backend, coupling_map=device_coupling, shots=100)
result = job.result()
plot_histogram(result.get_counts())
Explanation: Now, let us see what happens when the QFAs should accept the input string.
End of explanation
circuit_drawer(qfa2, style=qx_color_scheme())
Explanation: The error of rejecting the bitstring is equal to the probability of observing "1" which can be checked from the above histogram. We can see that the noise of real-device backends prevents us to have a correct answer. It is left as future work on how to mitigate errors of the backends in the QFA models.
End of explanation
<END_TASK>