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.
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.
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 is quite simple as follows.
In [1]:
# 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
In [2]:
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']
We then use QISKit to program the algorithm.
In [3]:
#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
The qfa_algorithm function returns the Quantum Circuit qfaCircuit.
In [4]:
#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"
Insert your own parameters and try even larger prime numbers.
In [5]:
range_lower = 0
range_higher = 36
prime_number = 11
In [6]:
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))
In [7]:
circuit_drawer(qfa_algorithm("a"* 3, prime_number), style=qx_color_scheme())
The algorithm is quite simple as follows.
We then use QISKit to program the algorithm.
In [8]:
#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
The qfa_algorithm function returns the Quantum Circuit control_qfaCircuit.
In [9]:
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))
In [10]:
circuit_drawer(qfa_controlled_algorithm("a"* 3, prime_number), style=qx_color_scheme())
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.
In [11]:
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)
In [12]:
%%qiskit_job_status
HTMLProgressBar()
job = execute(qfa1, backend=device_backend, coupling_map=device_coupling, shots=100)
In [13]:
result = job.result()
plot_histogram(result.get_counts())
In the above, we can see that the probability of observing "1" is quite significant. Let us see how the circuit looks like.
In [14]:
circuit_drawer(qfa1, style=qx_color_scheme())
Now, let us see what happens when the QFAs should accept the input string.
In [15]:
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)
In [16]:
%%qiskit_job_status
HTMLProgressBar()
job = execute(qfa2, backend=device_backend, coupling_map=device_coupling, shots=100)
In [17]:
result = job.result()
plot_histogram(result.get_counts())
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.
In [18]:
circuit_drawer(qfa2, style=qx_color_scheme())