Defense of the doctoral dissertation: Aliia Khadieva

On 16th of January, 2026, remotely at 15.00 the UL Promotional Council of Computer Science and Informatics, and Electrical Engineering, Electronics and Communication Technology will hold an open meeting, during which Aliia Khadieva will defend her doctoral thesis (Ph.D) in natural sciences.

Topic: "Analysis and implementation of quantum automata and their generalizations".

Scientific supervisor: Dr. sc. comp. Abuzer Yakaryilmaz.

Abstract:

In this work, we study different models of finite automata and their modifications, analyse their computational power and limitations. Specifically, we investigate quantum finite automata as well as their implementation on real machines. We also explore some non-uniform quantum automata and quantum automata-like algorithms. The first part is devoted to the study of quantum algorithms based on the fingerprinting technique. In particular, we study the quantum finite automaton (QFA) for the language MOD_p = {a^i·p | i ≥ 0} as one of the main algorithms based on this technique, and design QFAs for other languages. We also implement the QFAs efficiently on real circuit-based devices. Furthermore, we present several methods to improve an implementation of the QFA algorithm for MOD_p recognition when implemented on real quantum devices. We then analyse the implementation results in terms of correctness, noise resistance and scalability. In the second part, we study quantum ordered binary decision diagrams (QOBDDs) as non-uniform automata and investigate their computational power. We focus on a particular model of QOBDDs, which is a read-k-times quantum model of OBDD (k-QOBDD). We artificially create a Boolean function and present a k-QOBDD that computes this function to show some hierarchies of complexity classes of Boolean functions computable by k-QOBDDs of constant, polylogarithmic and sublinear width. In the third part, we consider an affine model of computation. This model is a quantum-like generalization of probabilistic systems. Specifically, we study affine automata and affine verifiers, in particular, as bounded error Arthur-Merlin systems with real-time affine finite verifiers. In this work, we provide some language verification algorithms and investigate the verification power of affine finite automata.

Reviewers:

1) Dr. sc. comp. Kārlis Čerāns, University of Latvia;

2) Dr. Ahmet Celal Cem Say, Bogazici University, Turkey;

3) Dr. Beatrice Palano, University of Milan, Italy.

The doctoral thesis is available at the LU Library, Raiņa bulvāris 19.

Participation in the session is by prior application, writing to sintija.silina@lu.lv by 13th of January.