À¶Ý®ÊÓƵ

°Õ¾±³Ù±ô±ð:ÌýAlice, Bob, and colours: An algebraic approach to quantum advantage

Abstract:ÌýTwo-player one-round games exhibit quantum advantage if the availability of quantum resources results in non-classical correlations between the players' answers, which allow outperforming any classical strategy. The first part of the talk illustrates a link between (i) the occurrence of quantum advantage in a game, and (ii) the complexity of the corresponding classical computational problem. In particular, I will show that both (i) and (ii) are determined by the same algebraic invariants of the game, known as polymorphisms. This allows transferring methods from the universal-algebraic theory of constraint satisfaction to the setting of quantum advantage. In particular, this approach yields a complete characterisation of the occurrence of quantum advantage for games played on graphs. ÌýÌý

The second part of the talk outlines recent work on the quantum chromatic number introduced in [Cameron--Montanaro--Newman--Severini--Winter'07]. The gap between this parameter and its classical counterpart is a measure of quantum advantage for the graph colouring game. Using the polymorphic approach, I will show that the maximum gap is linear when the quantum chromatic number makes use of entangled strategies on a constant number of qubits. In contrast, in the case of unlimited entanglement resources, I will prove the existence of graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large, conditional to the quantum variants of Khot's d-to-1 Conjecture [Khot'02] and HÃ¥stad's inapproximability of linear equations [HÃ¥stad'01].