Classical and Quantum Algorithms for Deterministic and Stochastic L-System Inference Problems
Date
2025-01-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
0000-0003-1478-542X
Type
Thesis
Degree Level
Masters
Abstract
L-systems can model and simulate many biological processes, such as plant development. Experts typically construct an L-system for a given process by hand, which is hugely time-consuming.
It would be significant if this could be done automatically from data, such as from sequences of images.
We will focus on two kinds of L-systems in this thesis: deterministic and stochastic L-systems.
As the names suggest, deterministic L-systems generate a unique sequence, while stochastic systems generate a variety of sequences with certain probabilities.
The method of constructing an L-system from a given process could look different for deterministic and stochastic L-systems.
In the case of stochastic L-systems, interesting problems could include how to construct a stochastic L-system with the highest probability of producing such a process.
Approximate solutions and solutions which
utilize the power of quantum computing are also of interest.
In one chapter of this thesis, we will present novel theorems that address open problems
in stochastic Lindenmayer-system (L-system) inference. Specifically, we will discuss the construction of an optimal stochastic L-system capable of generating
a given sequence of strings. The first theorem proposes a method for constructing a stochastic L-system that has a derivation with the highest probability of producing a given
sequence of words. The second
theorem addresses the more difficult problem in this area; it offers the stochastic L-systems with the highest probability of
producing a given sequence of words through multiple possible derivations. Once we have set the foundation to analyze these problems, we will introduce an algorithm that constructs an optimal stochastic L-system from a given sequence. This algorithm utilizes sophisticated optimization techniques, ensuring the production of a stochastically
optimal stochastic L-system suitable for generating the given sequence. This allows for using stochastic L-systems as a model for machine learning, using only positive data for training.
In the second part of this thesis, we are interested in inferring a deterministic context-free L-system from a sequence of strings. We will first introduce the characteristic graph of a sequence of strings. This graph captures the restrictions that inference applies in a problem, which we then utilize to translate our problem (inferring D0L-systems) in polynomial time into the maximum independent set problem (MIS). This translation also offers a free translation of our problem into the SAT problem. After that, we provide a classical exact and approximate quantum algorithm for the problem. The quantum algorithm we will be presenting belongs to the family of QAOA (Quantum Approximate Optimization Algorithms), and its time complexity has a polynomial time complexity. This algorithm is the first quantum algorithm and is another witness to how vast quantum computing could be towards machine learning. Our result also offers nontrivial upper bounds on the number of distinct deterministic L-systems that may generate a sequence of strings.
Description
Keywords
formal language theory, stochastic grammar, Lindenmayer systems, inference, machine learning, quantum machine learning
Citation
Degree
Master of Science (M.Sc.)
Department
Computer Science
Program
Computer Science