Quantum advantage in categories of relational structures
Lead Research Organisation:
University of Oxford
Department Name: Computer Science
Abstract
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
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
Organisations
People |
ORCID iD |
| Samson Abramsky (Primary Supervisor) | |
| Thomas Paine (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509711/1 | 01/10/2016 | 30/09/2021 | |||
| 1893567 | Studentship | EP/N509711/1 | 01/10/2017 | 31/03/2021 | Thomas Paine |