Physical implementations of cryptographic algorithms leak information, which makes them vulnerable to so-called side-channel attacks.Cryptography is now used in an ever-increasing variety of scenarios, and the assumption that the execution of cryptosystems is physically insulated is often not realistic.The field of leakage resilience proposes to mitigate side-channel attacks by designing protocols that are secure even if information leaks during execution.In this work, we study leakage-resilient computation, which concerns the problem of performing secure universal computation in the presence of leakage.Fault-tolerant quantum computation is concerned with the problem of noise in quantum computers.Since it is very hard to insulate quantum systems from noise, fault tolerance proposes schemes for performing computations correctly even if some noise is present.It turns out that there exists a connection between leakage resilience and fault tolerance.In this work, we show that leakage in a classical circuit is a form of noise, when the circuit is interpreted as quantum.We then prove that for an arbitrary leakage model, there exists a corresponding noise model in which a circuit that is fault-tolerant against the noise model is also resilient against the given leakage model.We also show how to use constructions for fault tolerance to implement classical circuits that are secure in specific leakage models.This is done by establishing criteria in which quantum circuits can be converted into classical circuits in such a way that the leakage resilience property is preserved.Using these criteria, we convert an implementation of universal fault-tolerant quantum computation into a classical leakageresilient compiler, i.e., a scheme that compiles an arbitrary circuit into a circuit of the same functionality that is leakage-resilient.vi 4.9 (a): Circuito de codificação para |0 no código de Steane.O circuito que codifica |+ é o mesmo, com a diferença de que alvos e controles são revertidos, e estados |0 são revertidos em |+ e vice-versa.(b):
Physical implementations of cryptographic algorithms leak information, which makes them vulnerable to so-called side-channel attacks.Cryptography is now used in an ever-increasing variety of scenarios, and the assumption that the execution of cryptosystems is physically insulated is often not realistic.The field of leakage resilience proposes to mitigate side-channel attacks by designing protocols that are secure even if information leaks during execution.In this work, we study leakage-resilient computation, which concerns the problem of performing secure universal computation in the presence of leakage.Fault-tolerant quantum computation is concerned with the problem of noise in quantum computers.Since it is very hard to insulate quantum systems from noise, fault tolerance proposes schemes for performing computations correctly even if some noise is present.It turns out that there exists a connection between leakage resilience and fault tolerance.In this work, we show that leakage in a classical circuit is a form of noise, when the circuit is interpreted as quantum.We then prove that for an arbitrary leakage model, there exists a corresponding noise model in which a circuit that is fault-tolerant against the noise model is also resilient against the given leakage model.We also show how to use constructions for fault tolerance to implement classical circuits that are secure in specific leakage models.This is done by establishing criteria in which quantum circuits can be converted into classical circuits in such a way that the leakage resilience property is preserved.Using these criteria, we convert an implementation of universal fault-tolerant quantum computation into a classical leakageresilient compiler, i.e., a scheme that compiles an arbitrary circuit into a circuit of the same functionality that is leakage-resilient.vi 4.9 (a): Circuito de codificação para |0 no código de Steane.O circuito que codifica |+ é o mesmo, com a diferença de que alvos e controles são revertidos, e estados |0 são revertidos em |+ e vice-versa.(b):
This thesis is concerned with certain theoretical problems that arise naturally in the context of fault-tolerant quantum computation. Fault-tolerance can be defined as the art of building reliable devices from unreliable components, and is of particular importance for quantum computers that aim to precisely control the dynamics of extremely sensitive quantum systems. A model of quantum computation is a specification of the basic building blocks by which a quantum computation is implemented. The best known model is the quantum circuit model, where computations are implemented by means of unitary quantum gates that are applied to two-level quantum systems known as qubits. In a physical implementation of a quantum circuit, the gates and qubits will inevitably be affected by noise. Fault-tolerant quantum circuits are designed to be resilient against the effects of this noise, provided that it is not too strong. Fault-tolerance in the quantum circuit model is well developed thanks to the theory of quantum error-correcting codes. These codes allow for the correction of small numbers of errors introduced by a variety of noise processes. In a fault-tolerant quantum circuit, qubits are replaced with encoded qubits, and quantum gates with encoded gates that are immediately followed by special quantum circuits for error correction. Provided the rate at which errors occur is below a constant threshold value, the accumulation of errors can be checked so that the correct output of the computation correctly determined. The threshold acts as both a measure of how good the design of a quantum circuit is, and also as a target for experimenters aiming to implement quantum circuits. Much current research in quantum computation is aimed at designing quantum circuits that increase the noise threshold, hopefully to the point where it becomes within the reach of experimenters. A fault-tolerant encoded quantum gate must limit the propagation of errors so that the code’s corrective capabilities are not overwhelmed. It is not so easy to design encoded gates that satisfy this property, and to date only a finite handful of such gates are known. In a faulttolerant quantum circuit, all quantum gates must be decomposed or compiled in terms of those that may be implemented fault-tolerantly. In the first part of this thesis, we present two results that may be applied to this problem of gate compilation. The first is a generic method based on the Solovay-Kitaev theorem that may be applied to all quantum gates, but is most effective for those that act on single qubits. We present the Solovay-Kitaev theorem in its simples known form as an algorithm, together with novel constructions that can be used to implement it. Following this we give a two specialized methods for two-qubit gate decomposition, based on the Cartan decomposition of the Lie group SU(4). The cluster-state model of computation is an alternative to the quantum circuit model, and makes use of quantum measurements and highly entangled cluster-states to implement a quantum computation. The fault-tolerant techniques developed for quantum circuits are not immediately applicable in this model, so in order for it to be a realistic candidate for performing computations we prove that such techniques are possible. In the second part of the thesis we prove that constant fault-tolerance thresholds may be achieved in the cluster-state model, and in particular in an adaption to an optical implementation. Following this we design a complete error correction scheme for optical cluster-state computation, and numerically determine the threshold of this model in the face of the dominant noise models likely to affect such an implementation.
Quantum computers promise to solve computational problems that are inaccessible to classical machines. The reliable execution of large-scale quantum algorithms requires robust operations in the presence of noise. Quantum error correction addresses this challenge by encoding quantum information redundantly across several physical qubits, such that errors can be detected and corrected during a computation. However, no single error-correcting code intrinsically supports an inherently robust, fault-tolerant implementation of all gates needed for universal quantum computing. Moreover, most modern approaches to both quantum error correction and the implementation of universal logical operations on encoded qubits rely on mid-circuit measurements and feed-forward control. These types of operations are technologically demanding, often slow, and prone to high error rates, and they limit the overall success probability of quantum algorithms. In this thesis, we develop fault-tolerant protocols and circuits for quantum error correction and universal logical computation, with an emphasis on implementations compatible with current hardware systems. We first focus on fault-tolerant quantum error correction on small codes. By comparing different protocols, we identify trade-offs between compact circuit constructions and their robustness to noise. We then assess their practical performance by comparing numerical simulations of noisy circuits with experimental data. Beyond the preservation of encoded information, we study how universal logic can be implemented in a fault-tolerant manner on encoded qubits. A central approach considered in this thesis is code switching, in which logical information is transferred between two distinct error-correcting codes that support complementary sets of inherently fault-tolerant logical gates. In combination, these codes give access to a complete universal fault-tolerant logical gate set. In this thesis, we determine conditions that allow us to construct fault-tolerant protocols for code switching. We adapt these protocols to the capabilities of current hardware, thereby enabling the first experimental realization of universal fault-tolerant logic by means of code switching. However, the overall performance of these schemes is limited by slow and noisy mid-circuit measurements. To address this bottleneck, we construct a suite of measurement-free fault-tolerant universal operations that do not require any measurements during the execution of an algorithm. In this framework, error correction and logical operations are implemented coherently as part of the quantum circuit, without mid-circuit measurements or in-sequence classical control. We introduce measurement-free code-switching schemes that can be scaled to arbitrary code distances through concatenation, and which thereby provide, in principle, arbitrarily strong error suppression. We further tailor our approach to the capabilities of current trapped-ion quantum processors. New circuit constructions support the first experimental implementation of a logical quantum algorithm without mid-circuit measurements, demonstrated through Grover's search on three encoded qubits. Together, the results of this thesis expand the toolbox for early fault-tolerant quantum computation. They show how protocols for quantum error correction and universal logical gates can be designed without mid-circuit measurements with realistic hardware constraints in mind, opening new pathways towards universal quantum logic.
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.
Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless, and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against (a) constant-depth circuits leakage, where the leakage function is computed by an AC0 circuit (composed of NOT gates and unbounded fan-in AND and OR gates); (b) noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, but each bit is perturbed by independent binomial noise---i.e., flipped with some probability p. Namely, for some number p∈(0,1/2], each bit of the computation is flipped with probability p, and remains unchanged with probability 1−p.
Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor's algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and M{ü}ller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard, model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction random errors.
Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor’s algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and Müller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction of random errors.