Quantum Finite Model Theory

该项目属于EPSRC ICT研究领域。该提案位于EPSRC资助的项目“资源和共同资源：语义和描述性复杂性之间的连接”（EP/T00696X/1）的更广泛背景下。该项目旨在通过探索将范畴论技术引入有限模型理论研究的新研究途径来推进理论计算机科学的最新发展，这两个主题到目前为止几乎完全是分开研究的。我参与这项工作的动机源于这样一个事实：它结合了我的几个研究兴趣：复杂性理论、数学逻辑和量子计算。复杂性理论是一个致力于将计算问题根据其解决难度分成不同类别的领域。通过以这种方式将问题组织在一起，我们可以确定计算机可以在短时间内完成的任务，并将它们与计算机无法有效解决的任务区分开来。因为许多定义明确的任务，如蛋白质折叠，寻找纳什均衡，甚至玩电子游戏，都可以形式化为计算问题，研究复杂性理论对其他各种领域都有影响，使其成为一个重要的研究课题。尽管如此，我们离解决这一领域最大的开放性问题还很遥远。有限模型理论是数理逻辑的一个分支，研究逻辑在有限模型上的表达能力。有限模型理论和复杂性理论之间存在着令人着迷的联系，而致力于探索这种联系的研究领域被称为描述性复杂性，它基于表达它们所需的逻辑来表征复杂性类。这一领域的研究始于一个开创性的结果，该结果表明存在二阶逻辑中可表达的所有问题的集合精确地对应于复杂度类NP。这个结果引入了使用描述性复杂性作为证明复杂性类之间分离的新工具的可能性。例如，找到一个与P对应的逻辑可以帮助解决著名的P与NP问题。量子计算是指利用叠加、纠缠等量子现象进行计算。在人们普遍相信的数学假设下，量子计算机可以比经典计算机更有效地解决一些问题。从复杂性理论的角度来看，弄清楚哪些问题容易受到这种量子加速的影响是一个重要的开放问题，在机器学习、量子模拟、密码学和许多其他领域都有潜在的应用。最近的研究表明，公共的范畴理论概念可以用来概括破坏者-复制者博弈，这是描述复杂性研究的主要对象之一。此外，另一种称为量子单子的新型分类结构在许多情况下捕获了量子加速的概念。作为我博士研究的起点，我将着眼于将这两方面的工作结合起来，以获得一种描述复杂性的新型量子理论。这样的理论可以导致量子复杂性类的逻辑特征，从而有助于解决复杂性理论中的主要开放性问题。描述性复杂性和参数化复杂性之间的关系也得到了很好的研究。在参数化复杂性中，目标是识别通常难以解决但如果我们修复问题的一些输入参数就会变得容易解决的计算问题。我们称这些问题为固定参数可处理问题。据我所知，之前还没有研究量子环境中参数化复杂性的工作，这是我想在博士期间探索的另一个途径。

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.