Logic Synthesis for Fault-Tolerant Quantum Computers

Efficient constructions for quantum logic are essential since quantum computation is experimentally challenging. This thesis develops quantum logic synthesis as a paradigm for reducing the resource overhead in fault-tolerant quantum computing. The model for error correction considered here is the surface code. After developing the theory behind general logic synthesis, the resource costs of magic-state distillation for the T = exp(i π(I-Z)/8) gate are quantitatively analyzed. The resource costs for a relatively new protocol distilling multi-qubit Fourier states are calculated for the first time. Four different constructions of the fault-tolerant Toffoli gate, including two which incorporate error detection, are analyzed and compared. The techniques of logic synthesis reduce the cost of fault-tolerant quantum computation by one to two orders of magnitude, depending on which benchmark is used. Using resource analysis for T gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+T" sequences, V-basis sequences, phase kickback, and programmable ancilla rotations. The application of arbitrary gates to quantum algorithms for simulating chemistry is discussed as well. Finally, the thesis examines the techniques which lead to efficient constructions of quantum logic, and these observations point to even broader applications of logic synthesis.