  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 \pi (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.

Quantum Physics