Fault-tolerant quantum computers compose elements of a discrete gate set in order to approximate a target unitary. The problem of minimizing the number of gates is known as gate synthesis. The approximation error is a form of coherent noise, which can be significantly more damaging than comparable incoherent noise. We show how mixing over different gate sequences can convert this coherent noise into an incoherent form. As measured by diamond distance, the postmixing noise is quadratically smaller than before mixing, without increasing resource cost upper bounds. Equivalently, we can look for shorter gate sequences that achieve the same precision as unitary gate synthesis. For a broad class of problems this gives a factor $1/2$ reduction in worst-case resource costs.
Fault-tolerant quantum computers compose elements of a discrete gate set in order to approximate a target unitary. The problem of minimizing the number of gates is known as gate synthesis. The approximation error is a form of coherent noise, which can be significantly more damaging than comparable incoherent noise. We show how mixing over different gate sequences can convert this coherent noise into an incoherent form. As measured by diamond distance, the postmixing noise is quadratically smaller than before mixing, without increasing resource cost upper bounds. Equivalently, we can look for shorter gate sequences that achieve the same precision as unitary gate synthesis. For a broad class of problems this gives a factor 1/2 reduction in worst-case resource costs.
Using error correcting codes and fault tolerant techniques, it is possible, at least in theory, to produce logical qubits with significantly lower error rates than the underlying physical qubits. Suppose, however, that the gates that act on these logical qubits are only approximation of the desired gate. This can arise, for example, in synthesizing a single qubit unitary from a set of Clifford and T gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error ε in the unitary of each gate must scale as ε≲1/N, where N is the number of gates. If, however, one has the option of synthesizing one of several unitaries near the desired target, and if an average of these options is closer to the target, we give some elementary bounds showing cases in which the errors can be made to add incoherently by averaging over random choices, so that, roughly, one needs ε≲1/N. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.
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.
Using error correcting codes and fault tolerant techniques, it is possible, at least in theory, to produce logical qubits with significantly lower error rates than the underlying physical qubits. Suppose, however, that the gates that act on these logical qubits are only approximation of the desired gate. This can arise, for example, in synthesizing a single qubit unitary from a set of Clifford and T gates; for a generic such unitary, any finite sequence of gates only approximates the desired target. In this case, errors in the gate can add coherently so that, roughly, the error epsilon in the unitary of each gate must scale as epsilon < 1/N, where N is the number of gates. If, however, one has the option of synthesizing one of several unitaries near the desired target, and if an average of these options is closer to the target, we give some elementary bounds showing cases in which the errors can be made to add incoherently by averaging over random choices, so that, roughly, one needs epsilon < 1/ √ N. We remark on one particular application to distilling magic states where this effect happens automatically in the usual circuits.
We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.
Rigorously establishing that the error in an experimental quantum operation is beneath the threshold for fault-tolerant quantum computation currently requires considering the worst-case error, which can be orders of magnitude smaller than the average gate infidelities routinely reported in experiments. We show that an improved bound on the worst-case error can be obtained by also considering the recently-introduced unitarity of the noise where the upper and lower bounds differ by a factor of ≈2.45 for unital qubit channels. We prove that the contribution from the nonunital part of any noise map is at most on the order of the average gate infidelity and so is negligible relative to any coherent contribution. We also show that the "average" error rate when measurements are not restricted to an eigenbasis containing the state of the system exhibits the same scaling as the worst-case error, which, for coherent noise, is the square-root of the infidelity. We also obtain improved bounds for the diamond distance when the noise map is known (or approximately known).
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.