Quantum Finite Model Theory

量子有限模型理论

• 批准号: 2426740
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2426740
• 关键词: 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.

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