Comparing Classical And Quantum Finite Automata*

Quantum computers offer advantages that motivate the exploration of quantum algorithms and models with the expectation that they can solve many more complex problems than classical computers. Here, we are exploring one of the simplest models of computation by comparing Deterministic Finite Automata and Quantum Finite Automata (Ambainis and Freivalds, 1998). This research focuses on applying quantum principles to the following problem: Consider a string aⁱ with i letters. We want to determine whether the string is in the language L where L = {aⁱ | i divides p} and p is a given prime number. If i divides p, we accept the string into the language with a 0 qubit state, and if not, we reject it with a qubit state of 1. Classically, using the highest known prime integer, this algorithm requires a minimum of 77,232,917 bits, whereas the quantum finite automata only requires 27 qubits. Using Python’s Quantum Information Software Kit (Qiskit), I have implemented a program [1] that can determine if the length of a string is divisible by a large prime number with exponentially fewer qubits.

[1] https://github.com/kaitlinmgili/sharing- github/blob/master/Comparing%20Classical%20and%20Quantum%20Finite%20Automata%20.ipyn b