Quantum advantage in categories of relational structures

关系结构类别中的量子优势

• 批准号: 1893567
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1893567
• 关键词: Quantum; advantage; categories; relational; structures

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

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