Quantum advantage in categories of 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