Quantum advantage in categories of relational structures

本项目属于EPSRC理论计算机科学研究领域。给定两个模型论关系结构(都使用相同的底层语言)，考虑两个参与者之间的博弈：从第一个结构中随机选择两个元素a和b，然后，在不共享信息的情况下，博弈者1和博弈者2从第二个结构中选择元素A和B。如果对于语言中的每个关系R，R(a，b)在第一个结构中成立当且仅当R(A，B)在第二个结构中成立，则玩家获胜。在这个博弈中，可以看到两个参与者的完美策略的存在等价于两个结构之间存在同态，因此可以看到考虑这样的博弈是如何成为接近有限关系结构的有用的方法。有限关系结构的研究在数据库理论、约束满足和图论等领域有着广泛的应用。在类似工作的基础上，例如在[1]和[2]中，这个项目的目标是探索如何使用量子信息来帮助找到有限关系结构之间的博弈的完美策略，例如上述结构之间的量子同态的概念。如果考虑一种特定语言中的结构范畴，称为克莱斯利范畴，那么在这类游戏中使用量子信息的策略也可以被识别为单子，这使得人们也可以运用范畴理论中的许多概念。因此，该项目将有助于理解如何在一系列信息处理任务中比传统资源更有效地利用量子资源。这种方法将包括量子信息、有限模型理论和范式论方法的新组合。[1]有限模型理论中的鹅卵石Comonad，S.Abramsky，A.Dawar和P.Wang[2]The Quantum Monad on Relative Structures，S.Abramsky，R.S.Barbosa，N.Silva和O.Zapata

This project falls within EPSRC theoretical computer science research area.Given two model-theoretic relational structures (both using the same underlying language), consider the following game played between two players: two elements, a and b, are chosen at random from the first structure, then, without sharing information, Player 1 and Player 2 select elements A and B from the second structure. The players win if for every relation R in the language, R(a,b) holds in the first structure if and only if R(A,B) holds in the second. In this game, one can see that the existence of a perfect strategy for the two players is equivalent to the existence of a homomorphism between the two structures, hence one can see how considering games such as these can be a useful way of approaching finite relational structures. The study of finite relational structures has many applications, for example to database theory, constraint satisfaction and graph theory. Building on similar work such as in [1] and [2], this project will aim to explore how the use of quantum information can be used to help find perfect strategies for games between finite relational structures such as the one described above, making use of the notion of a quantum homomorphism between structures. If one considers the category of structures in a certain language, known as a Kleisli category, strategies using quantum information in such games can also be recognised as monads, allowing one to bring to bear many notions from category theory also. Hence, the project will contribute to understanding how quantum resources can be used more effectively than classical resources in a range of information processing tasks. This approach will include a novel combination of methods from quantum information, finite model theory, and category theory.[1] The Pebbling Comonad in Finite Model Theory, S. Abramsky, A. Dawar and P. Wang[2] The Quantum Monad on Relational Structures, S. Abramsky, R.S. Barbosa, N. Silva, and O. Zapata