Level Reduction and the Quantum Threshold Theorem

Abstract

The quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.

125 pages, Ph.D. thesis, Caltech, 2007; pdf file fixed

References in corpus (20)

• Simulated Quantum Computation of Molecular Energies
• Quantum Computing with Very Noisy Devices
• Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories
• Instantaneous non-local computation of low T-depth quantum circuits
• Stabilizer Formalism for Operator Quantum Error Correction
• Valence Bond Solids for Quantum Computation
• Fault-tolerant quantum computation with long-range correlated noise
• Simulating lattice gauge theories on a quantum computer
• Subsystem fault tolerance with the Bacon-Shor code
• Fault-Tolerant Quantum Computation For Local Non-Markovian Noise
• Fault-tolerant quantum computation with cluster states
• Effective fault-tolerant quantum computation with slow measurements
• Noise thresholds for optical quantum computers
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Fault-Tolerant Postselected Quantum Computation: Schemes
• Computation by measurements: a unifying picture
• Universal Leakage Elimination
• Simple proof of fault tolerance in the graph-state model
• Error-detection-based quantum fault tolerance against discrete Pauli noise
• Secure Multi-party Quantum Computing

Cited by in corpus (16)

• Quantum Error Correction for Quantum Memories
• Quantum Error Correction for Beginners
• Fault-Tolerant Measurement-Based Quantum Computing with Continuous-Variable Cluster States
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Fault-tolerant quantum computation versus Gaussian noise
• Distilling one-qubit magic states into Toffoli states
• Overhead analysis of universal concatenated quantum codes
• Composite Toffoli gate with two-round error detection
• Scheme for fault-tolerant holonomic computation on stabilizer codes
• Logic Synthesis for Fault-Tolerant Quantum Computers
• An introduction to reliable quantum computation
• Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code
• Topics in quantum information and the theory of open quantum systems
• Prospects for Quantum Computing
• Approximate quantum error correction for correlated noise
• Circuit-level fault tolerance of cat codes