Quantum Finite Model Theory

本项目属于EPSRC信息和通信技术研究领域。本提案是在EPSRC资助的项目“资源和共同资源：语义和描述复杂性之间的交汇点”(EP/T00696X/1)的更广泛背景下提出的。该项目旨在通过探索新的研究途径来推动理论计算机科学的发展，这些研究途径源于将范式论技术引入有限模型理论的研究，这两个主题到目前为止几乎完全分开研究。我参加这项工作的动机来自于它结合了我的几个研究兴趣：复杂性理论、数理逻辑和量子计算。复杂性理论是致力于根据计算问题的困难程度将计算问题分成不同类别的领域。通过以这种方式将问题组织在一起，我们可以识别计算机可以在短时间内执行的任务，并将它们与计算机无法有效解决的任务分开。由于许多定义明确的任务，如蛋白质折叠、寻找纳什均衡，甚至玩电子游戏，都可以被形式化为计算问题，因此研究复杂性理论对其他许多领域都有影响，使其成为一个重要的研究主题。尽管这很重要，但我们距离解决该领域最大的开放问题还有很长的路要走。有限模型理论是数理逻辑的一个子领域，研究逻辑对有限模型的表达能力。有限模型理论和复杂性理论之间有一种令人着迷的联系，致力于探索这种联系的研究领域称为描述复杂性，它基于表达复杂性所需的逻辑来表征复杂性类。这一领域的研究始于一个开创性的结果，即存在二阶逻辑中所有可表达的问题集恰好对应于复杂性类NP。这一结果引入了使用描述性复杂性作为一种新的工具来证明复杂性类之间的分离的可能性。例如，找到与P对应的逻辑可以帮助解决著名的P与NP问题。量子计算指的是使用叠加和纠缠等量子现象进行计算。在普遍认为的数学假设下，众所周知，量子计算机可以比经典计算机更有效地解决一些问题。从复杂性理论的角度来看，准确地找出哪些问题容易受到量子加速的影响是一个重要的开放问题，在机器学习、量子模拟、密码学等许多领域都有潜在的应用。最近的工作表明，范畴论的联合概念可以用来封装描述复杂性的主要研究对象之一的扰乱-复制游戏。此外，另一种称为量子单子的新的分类结构在许多情况下捕捉到了量子加速的概念。作为我的DPhil研究的起点，我将考虑将这两条线结合起来，目标是推导出一种新的描述复杂性的量子理论。这样的理论可能导致量子复杂类的逻辑特征，这反过来可能有助于解决复杂性理论中的重大开放问题。描述性复杂性和参数复杂性之间也有一种经过充分研究的关系。在参数复杂性中，目标是确定通常难以解决但如果我们固定问题的一些输入参数就可以容易解决的计算问题。我们称这些问题为固定参数可处理问题。据我所知，之前还没有关于研究量子环境中的参数复杂性的工作，这是我在DPhil期间想要探索的另一个途径。

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.