BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//TYPO3/NONSGML Calendarize//EN


BEGIN:VEVENT
UID:calendarize-defense-of-the-doctoral-dissertation
DTSTAMP:20251222T142658Z

DTSTART:20260116T130000Z
DTEND:20260115T220000Z
    
SUMMARY:Defense of the doctoral dissertation: Aliia Khadieva
DESCRIPTION:Topic: "Analysis and implementation of quantum automata and their generalizations".\nScientific supervisor: Dr. sc. comp. Abuzer Yakaryilmaz.\nAbstract:\nIn 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 MODp = {ai·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 MODp 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.\nReviewers:\n1) Dr. sc. comp. Kārlis Čerāns\, University of Latvia\;\n2) Dr. Ahmet Celal Cem Say\, Bogazici University\, Turkey\;\n3) Dr. Beatrice Palano\, University of Milan\, Italy.\nThe doctoral thesis is available at the LU Library\, Raiņa bulvāris 19.\nParticipation in the session is by prior application\, writing to sintija.silina@lu.lv by 13th of January.
X-ALT-DESC;FMTTYPE=text/html:<p class="text-justify">Topic:<strong> "Analysis and implementation of quantum automata and their generalizations</strong>".</p>\n<p class="text-justify">Scientific supervisor: <i>Dr. sc. comp.</i> <strong>Abuzer Yakaryilmaz</strong>.</p>\n<p class="text-justify"><strong>Abstract:</strong></p>\n<p class="text-justify">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<sub>p </sub>= {a<sup>i·p</sup>&nbsp\;| i ≥ 0}&nbsp\;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<sub>p</sub>&nbsp\;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.</p>\n<p class="text-justify"><strong>Reviewers:</strong></p>\n<p class="text-justify"><strong>1)</strong> <i>Dr. sc. comp. </i><strong>Kārlis Čerāns</strong>\, University of Latvia\;</p>\n<p class="text-justify"><strong>2)</strong> <i>Dr.</i> <strong>Ahmet Celal Cem Say</strong>\, Bogazici University\, Turkey\;</p>\n<p class="text-justify"><strong>3)</strong> <i>Dr.</i> <strong>Beatrice Palano</strong>\, University of Milan\, Italy.</p>\n<p class="text-justify">The doctoral thesis is available at the LU Library\, Raiņa bulvāris 19.</p>\n<p class="text-justify">Participation in the session is by prior application\, writing to <a href="mailto:sintija.silina@lu.lv">sintija.silina@lu.lv</a> <strong>by 13th of January.</strong></p>
LOCATION:
END:VEVENT

END:VCALENDAR