Efficient quantum communication protocols and asynchronism in the toric code

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


This thesis studies quantum communication complexity and quantum error correction, two fundamental areas in the theory of quantum computation, and is divided into two parts. The first part focuses on generalising three central problems in quantum communication complexity, often by the introduction of more general Boolean functions. The first studied problem is the one of approximating the Hamming distance in the simultaneous message passing model in communication complexity --- a natural generalisation of the Equality problem. An efficient quantum communication protocol is established and later used as the basis for approximating other useful distance measures, e.g. graph distance and $\ell_1$-distance.

The second generalised problem is the Boolean Hidden Matching problem, the first proposed one to exhibit an exponential quantum-classical communication separation in the one-way model. Originally defined as a task of matching bits using the Parity function, the problem is generalised by replacing the Parity function with any Boolean function. The hardness of the resulting problem, both classical and quantumly, is characterised in terms of two properties of the Boolean function used, its sign degree and pure high degree.

The first part of the thesis is completed by studying the generalisation of random access codes where the parties are no longer interested in recovering any initial bit, but the value of a fixed Boolean function on any subset of the initial bits with constant size. Different random access codes are defined by means of different accessible classical and quantum resources and their efficiency analysed and compared.

The second part of the thesis is devoted to the study of quantum error correction and the toric code. Even though unrealistic for some physical platforms, most decoders proposed for the toric code assume that stabilizer measurements can always be performed deterministically. This second part aims to study the effect of probabilistic stabilizer measurements, i.e., asynchronism, on the toric code. A few different decoders, based on gradually more refined approximations, are proposed in order to handle the asynchronism and it is numerically shown that they are able to maintain a high threshold even in the limit where stabilizer measurements are performed continuously.
Date of Award28 Sep 2021
Original languageEnglish
Awarding Institution
  • The University of Bristol
SupervisorAshley M R Montanaro (Supervisor) & Mark G Thompson (Supervisor)


  • communication complexity
  • Error Correction
  • random access code
  • quantum complexity

Cite this