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:
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:
This dissertation is motivated by the following fundamental questions: (a) are there any exponential gaps between quantum and classical communication complexities? (b) what is the role of entanglement in assisting quantum communications? (c) how to characterize the nonlocality of quantum operations? We study four specific problems below. 1. The communication complexity of the Hamming Distance problem. The Hamming Distance problem is for two parties to determine whether or not the Hamming distance between two n-bit strings is more than a given threshold. We prove tighter quantum lower bounds in the general two-party, interactive communication model. We also construct an efficient classical protocol in the more restricted Simultaneous Message Passing model, improving previous results. 2. The Log-Equivalence Conjecture. A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a total Boolean function in the two-party, interactive model. The answer is believed to be No. Razborov proved this conjecture for the most general class of functions so far. We prove this conjecture for a broader class of functions that we called block-composed functions. Our proof appears to be the first demonstration of the dual approach of the polynomial method in proving new results. 3. Classical simulations of bipartite quantum measurement. We define a new ix concept that measures the nonlocality of bipartite quantum operations. From this measure, we derive an upper bound that shows the limitation of entanglement in reducing communication costs. 4. The maximum tensor norm of bipartite superoperators. We define a maximum tensor norm to quantify the nonlocality of bipartite superoperators. We show that a bipartite physically realizable superoperator is bi-local if and only if its maximum tensor norm is 1. Furthermore, the estimation of the maximum tensor norm can also be used to prove quantum lower bounds on communication complexities.
Quantum error correction is needed for future quantum computers. Classical error correcting codes are not suitable for this due to the nature of quantum mechanics. Therefore, new codes need to be developed. A promising candidate is the toric code, a surface code, because of its locality and its high error correcting capability and thresholds (the error probability below which increasing the size of the code decreases the failure rate). This thesis provides an introduction to quantum error correction and the stabilizer formalism, which is used to introduce the toric code. Several decoders are looked at, including the Minimum Weight Perfect Matching (MWPM) decoder and a recently developed decoder, the Union-Find (UF) decoder. The UF decoder is useful because of its almost-linear time complexity, while only reducing the threshold by a marginal amount compared to the MWPM decoder. In this thesis, the time complexity of the weighted growth version of the UF decoder is analysed. The toric code and the decoders have been implemented and simulated, and the thresholds have been determined. For the MWPM decoder, the threshold was determined to be 11.5±0.2%, which is not in agreement with the threshold in literature of 10.3%, and should not be possible according to the optimal threshold of about 11%. This probably is a result of the low grid sizes (up to a gridsize of 11) of the code used due to the time needed to simulate the MWPM decoder. For the UF decoder, the threshold found was 9.7 ± 0.9%, which is in agreement with the threshold of 9.9% found by N. Delfosse and N. Nickerson. The time complexity of the UF decoder has also been determined, and is indeed almost-linear as expected by the analysis.
Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.
This thesis will be focused on the classical capacity of quantum channels, one of the first areas treated by quantum information theorists. The problem is fairly solved since some years. Nevertheless, this work will give me a reason to introduce a consistent formalism of the quantum theory, as well as to review fundamental facts about quantum non-locality and how it can be used to enhance communication. Moreover, this reflects my dwelling in the spirit of classical information theory, and it is intended to be a starting point towards a thorough study of how quantum technologies can help to shape the future of telecommunications. Whenever it was possible, heuristic reasonings were introduced instead of rigorous mathematical proofs. This finds an explanation in that I am a self-taught neophyte in the field, and just about every time I came across a new concept, physical arguments were always more compelling to me than just maths. The technical content of the thesis is twofold. On one hand, a quadratic classification based on optimization programs that I devised for distinguishing entangled states is presented in Chapter 4. In second place, a less difficult yet I hope equally interesting technical part consists of versions of some proofs throughout the text.
Quantum algorithms require quantum computers performing logical operations on a sufficiently large number of entangled qubits. Unfortunately, state-of-the-art quantum computers can only operate on tens of qubits. A solution to this scalability challenge is to employ the distributed paradigm, where a network of small-scale quantum computers are used in a distributed manner. It is the aim of my work to study the fundamental limits of distributed quantum problems and to further enhance their performance by exploiting the structure inherent to these problems employing asymptotically good Algebraic codes. This thesis consists of two parts. The first part studies the task of faithfully simulating a distributed quantum measurement, wherein we provide a protocol for the three parties, Alice, Bob and {Charlie}, to simulate a repeated action of a distributed quantum measurement using a pair of non-product approximating measurements by Alice and Bob, followed by a stochastic mapping at {Charlie}. The objective of the protocol is to utilize minimum resources, in terms of classical bits needed by Alice and Bob to communicate their measurement outcomes to {Charlie}, and the common randomness shared among the three parties, while faithfully simulating independent repeated instances of the original measurement. We characterize a set of sufficient communication and common randomness rates required for asymptotic simulatability in terms of single-letter quantum information quantities. We further improve the results obtained in the above by exploiting the structure present in the Charlie's stochastic bivariate mapping using random structured POVMs based on asymptotically good algebraic codes. The algebraic structure of these codes is matched to that of the bivariate function that models the action of Charlie. This leads to the computation being performed on the fly, thus obviating the need to reconstruct individual measurement outcomes at Charlie. We provide examples to illustrate the information-theoretic gains attained by endowing POVMs with algebraic structure. As an application of the distributed measurement compression problem, we also demonstrate a multi-party purity distillation protocol. Concluding this part, we consider the lossy quantum source coding problem where the objective is to compress a given quantum source below its von Neumann entropy. Inspired by the duality connections between the rate-distortion and channel coding problems in the classical setting, we propose a new formulation for the lossy quantum source coding problem. We require that the reconstruction of the compressed quantum source fulfill a global error constraint and employ the notion of a ``posterior reference map'' to measure the reconstruction error. Using these, we characterize the asymptotic performance limit of this problem in terms of single-letter coherent information of the given posterior reference map. In the second part of this thesis, we study the advantage algebraic structured codes can provide, to the class of the classical-quantum network problems. In particular, we investigate two problems. Firstly, we consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. We propose and analyze a coding scheme based on algebraic structured coset codes that enables the decoder to recover the desired function without recovering the sources themselves. We derive a new set of sufficient conditions that are weaker than the current known for identified examples. In addition, we analyze the performance of these algebraic codes toward studying the capacity of a special class of 3-user classical-quantum interference channel.
This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.