Efficient quantum communication protocols and asynchronism in the toric code
João Fernando Doriguello Diniz
Abstract
T his 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 ℓ 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.i Dedication and acknowledgements M y deepest thanks goes to my supervisor, Ashley Montanaro, who supported and motivated me during these last three years.Coming from a physics background, I am grateful to Ashley for introducing me to the field of Quantum Computation, and also for helping me to mature both academically and intellectually since my Masters.I also thank Ashley for incentivising my taste for literature by lending me his copy of John Milton's Paradise Lost.I thank my co-authors, Naomi Nickerson and Hugo Cable, for all the help and discussions behind Chapter 6 about quantum error correction and the toric code, and for their kind welcome at the time of my visit at PsiQuantum.I also thank Ryan Mann for many useful discussions, most of them about concepts from Chapter 6 and self-avoiding walks; Ronald de Wolf for having reliably improved all my papers so far with valuable suggestions and comments, for suggesting the block-encoding scheme in Chapter 4, originally with the 2, 3 → 1 QRACs, for pointing out Refs. [119,121,177] and for the precise reviewing of the thesis; Noah Linden for the precise reviewing of the thesis and for testing me throughout my PhD with interesting questions; Raphaël Clifford for helpful discussions related to Chapter 2; Makrand Sinha for useful discussions about the hypercontractive inequality; Máté Farkas and Mark Howard for pointing out Refs. [4,72,73, 190] and [69], respectively.These last four years would not be the same without all the support from QE-CDT (Center for Doctoral Training in Quantum Engineering) and QET Labs (Quantum Engineering Technology Labs) and all the people behind them, both the management and the academic teams.And not less important, my time in Bristol would definitely not be the same without my cohort: