Quantum Finite Model Theory

This project falls within the EPSRC ICT research area.
This proposal sits within the wider context of the EPSRC funded project "Resources and co-Resources: A junction between semantics and descriptive complexity" (EP/T00696X/1). The project aims to advance the state-of-the-art in theoretical computer science by exploring new avenues of research which arise from bringing category-theoretic techniques into the study of finite model theory, two topics which have been studied almost entirely disjointly until now. My motivation for taking part in this effort stems from the fact that it combines several of my research interests: complexity theory, mathematical logic, and quantum computation.
Complexity theory is the field dedicated to grouping computational problems into different classes based on how difficult they are to solve. By organising problems together in this way, we can identify tasks that computers can perform in a short amount of time, and separate them from tasks which a computer will be unable to solve efficiently. Because many well-defined tasks, such as protein folding, finding Nash equilibria, or even playing video games, can be formalised as computational problems, studying complexity theory has implications for a wide variety of other fields, making it an important subject of research. Despite this importance, we are still far away from solving the biggest open questions in this field.
Finite model theory is a subfield of mathematical logic that studies the expressive power of logics over finite models. There is a fascinating link between finite model theory and complexity theory, and the area of study dedicated to exploring this link is called descriptive complexity, which characterises complexity classes based on the logics required to express them. Research in this area began after a seminal result showed that the set of all problems expressible in existential second-order logic corresponds precisely to the complexity class NP. This result introduced the possibility of using descriptive complexity as a new tool to prove separations between complexity classes. For example, finding a logic which corresponds to P could help settle the famous P vs. NP problem.
Quantum computing refers to the usage of quantum phenomena such as superposition and entanglement to perform computation. Under widely believed mathematical assumptions, it is known that quantum computers can solve some problems more efficiently than classical computers. From the point of view of complexity theory, figuring out exactly what problems are susceptible to such quantum speed-ups is an important open problem, with potential applications in machine learning, quantum simulations, cryptography, and many other fields.
Recent work has shown that the category-theoretic concept of a comonad can be used to encapsulate spoiler-duplicator games, one of the main objects of study in descriptive complexity. Moreover, another novel categorical construct called the quantum monad captures the notion of quantum speed-ups in many situations. As a starting point for my DPhil research, I will look into combining these two lines of work with the goal of deriving a novel quantum theory of descriptive complexity. Such a theory could lead to logical characterisations of quantum complexity classes which could in turn help solve major open problems in complexity theory. There is also a well-studied relationship between descriptive complexity and parameterised complexity. In parameterised complexity, the goal is to identify computational problems which are in general hard to solve but become easy to solve if we fix some of the input parameters of the problems. We call these problems fixed-parameter tractable. To the best of my knowledge, there has been no prior work on studying parameterised complexity in a quantum setting, this is another avenue which I would like to explore during my DPhil.