ON SOME OPTIMISATION PROBLEMS ARISING FROM QUANTUM COMPUTING

Abstract

The thesis studies some problems arising from quantum computing using tools from optimisation theory. The first part of the thesis focuses on duelling algorithms in game theory. In a competitive scenario, quite often the best strategy to beat an opponent is not the same as one's own optimal strategy (when there is no competition). We observe that in the quantum setting, duelling algorithms for even simple tasks like searching can give rise to very interesting game theoretic dynamics. For example, we answer questions like "what is the Nash equilibrium strategy when say, two (or more) players perform Grover's search and the first one to find the solution wins?" In the second part of the thesis we study quantum Self-testing, schemes that certify quantum state and measurements using only measurement statistics. We leverage the graph-theoretic framework for contextuality, combined with tools from semi-definite programming, to establish new robust self-testing results.