Logic Synthesis for Fault-Tolerant Quantum Computers
arXiv:1310.7290
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 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 gates and Toffoli gates, several proposals for constructing arbitrary quantum gates are compared, including "Clifford+" sequences, -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.
arXiv commentPhD 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 (80)
- Elementary gates for quantum computation
- Long-distance quantum communication with atomic ensembles and linear optics
- Quantum algorithm for solving linear systems of equations
- Surface codes: Towards practical large-scale quantum computation
- Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
- Good Quantum Error-Correcting Codes Exist
- The Physical Implementation of Quantum Computation
- Quantum state transfer and entanglement distribution among distant nodes in a quantum network
- Quantum Teleportation is a Universal Computational Primitive
- Dynamical Decoupling of Open Quantum Systems
- Simulated Quantum Computation of Molecular Energies
- Quantum Algorithms Revisited
- Quantum Computing with Very Noisy Devices
- An Open-System Quantum Simulator with Trapped Ions
- Reliable Quantum Computers
- Quantum Simulation of Antiferromagnetic Spin Chains in an Optical Lattice
- Fault-tolerant quantum computation with high threshold in two dimensions
- Quantum Networks for Elementary Arithmetic Operations
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Towards Quantum Chemistry on a Quantum Computer
- Quantum Error Correction for Beginners
- Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
- Topological fault-tolerance in cluster state quantum computation
- Fault-Tolerant Quantum Dynamical Decoupling
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- High threshold universal quantum computation on the surface code
- Restrictions on Transversal Encoded Quantum Gate Sets
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Efficient Simulation of Quantum Systems by Quantum Computers
- Quantum computing with nearest neighbor interactions and error rates over 1%
- Methodology for quantum logic gate constructions
- Implementing the Quantum von Neumann Architecture with Superconducting Circuits
- A new quantum ripple-carry addition circuit
- Preconditioned quantum linear system algorithm
- Robust dynamical decoupling with bounded controls
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Creating superpositions that correspond to efficiently integrable probability distributions
- Universal fault-tolerant quantum computation with only transversal gates and error correction
- Quantum circuits of T-depth one
- Simulating lattice gauge theories on a quantum computer
- Subsystem fault tolerance with the Bacon-Shor code
- Towards practical classical processing for the surface code
- Addition on a Quantum Computer
- Fast Quantum Modular Exponentiation
- Quantum simulation of the wavefunction to probe frustrated Heisenberg spin systems
- Fast simulation of stabilizer circuits using a graph state representation
- Direct Characterization of Quantum Dynamics
- Experimental Uhrig Dynamical Decoupling using Trapped Ions
- Improved magic states distillation for quantum universality
- Efficient factorization with a single pure qubit and mixed qubits
- Multilevel distillation of magic states for quantum computing
- Combining dynamical decoupling with fault-tolerant quantum computation
- Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics
- Quantum Communication with Phantom Photons
- Quantum Information Processing with Ferroelectrically Coupled Quantum Dots
- Surface code implementation of block code state distillation
- Conditional phase shift from a quantum dot in a pillar microcavity
- Fault-Tolerant Postselected Quantum Computation: Schemes
- Fast parallel circuits for the quantum Fourier transform
- Fault-tolerant quantum computing with color codes
- Bound States for Magic State Distillation in Fault-Tolerant Quantum Computation
- Efficient Decomposition of Single-Qubit Gates into Basis Circuits
- Scalability of Shor's algorithm with a limited set of rotation gates
- A scalable, high-speed measurement-based quantum computer using trapped ions
- Quantum Dot Cluster State Computing with Encoded Qubits
- A bridge to lower overhead quantum computation
- Communication Links for Distributed Quantum Computation
- A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
- Towards practical classical processing for the surface code: timing analysis
- Long-range coupling and scalable architecture for superconducting flux qubits
- Quantum Computing of Quantum Chaos in the Kicked Rotator Model
- Level Reduction and the Quantum Threshold Theorem
- Complex instruction set computing architecture for performing accurate quantum rotations with less magic
- Composite Toffoli gate with two-round error detection
- Quantum circuit optimization by topological compaction in the surface code
- Shor's algorithm with fewer (pure) qubits
- Automated Generation of Layout and Control for Quantum Circuits
- Accurate simulations of planar topological codes cannot use cyclic boundaries
- Interconnection Networks for Scalable Quantum Computers
- The impact of classical electronics constraints on a solid-state logical qubit memory
Cited by in corpus (7)
- Quantum Error Correction for Quantum Memories
- 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