Logic Synthesis for Fault-Tolerant Quantum Computers

Abstract

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.

PhD Thesis. 201 pages, 10 chapters, 62 figures. Original version on Stanford archives at [http://purl.stanford.edu/mz653ng0546]. Incorporates material from arXiv:1010.5022, arXiv:1204.0567, arXiv:1205.2402, arXiv:1210.3388, arXiv:1212.5069, and arXiv:1303.3066

References in corpus (30)

• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Simulated Quantum Computation of Molecular Energies
• An Open-System Quantum Simulator with Trapped Ions
• Quantum Simulation of Antiferromagnetic Spin Chains in an Optical Lattice
• Fault-tolerant quantum computation with high threshold in two dimensions
• Topological fault-tolerance in cluster state quantum computation
• Fault-Tolerant Quantum Dynamical Decoupling
• Restrictions on Transversal Encoded Quantum Gate Sets
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Quantum computing with nearest neighbor interactions and error rates over 1%
• A new quantum ripple-carry addition circuit
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum circuits of T-depth one
• Subsystem fault tolerance with the Bacon-Shor code
• Fast Quantum Modular Exponentiation
• Fast simulation of stabilizer circuits using a graph state representation
• Improved magic states distillation for quantum universality
• Multilevel distillation of magic states for quantum computing
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Scalability of Shor's algorithm with a limited set of rotation gates
• A scalable, high-speed measurement-based quantum computer using trapped ions
• A bridge to lower overhead quantum computation
• Communication Links for Distributed Quantum Computation
• Long-range coupling and scalable architecture for superconducting flux qubits
• Quantum Computing of Quantum Chaos in the Kicked Rotator Model
• Quantum circuit optimization by topological compaction in the surface code
• Automated Generation of Layout and Control for Quantum Circuits
• Interconnection Networks for Scalable Quantum Computers
• The impact of classical electronics constraints on a solid-state logical qubit memory

Cited by in corpus (6)

• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Doubled Color Codes
• Resource optimization for fault-tolerant quantum computing
• Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts