A Caltech Library Service

Level-Reduction and the Quantum Threshold Theorem


Aliferis, Panagiotis (Panos) (2007) Level-Reduction and the Quantum Threshold Theorem. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3ZM6-HE29.


Computers have led society to the information age revolutionizing central aspects of our lives from production and communication to education and entertainment. There exist, however, important problems which are intractable with the computers available today and, experience teaches us, will remain so even with the more advanced computers we can envision for tomorrow.

Quantum computers promise speedups to some of these important but classically intractable problems. Simulating physical systems, a problem of interest in a diverse range of areas from testing physical theories to understanding chemical reactions, and solving number factoring, a problem at the basis of cryptographic protocols that are used widely today on the internet, are examples of applications for which quantum computers, when built, will offer a great advantage over what is possible with classical computer technology.

The construction of a quantum computer of sufficient scale to solve interesting problems is, however, especially challenging. The reason for this is that, by its very nature, operating a quantum computer will require the coherent control of the quantum state of a very large number of particles. Fortunately, the theory of quantum error correction and fault-tolerant quantum computation gives us confidence that such quantum states can be created, can be stored in memory and can also be manipulated provided the quantum computer can be isolated to a sufficient degree from sources of noise.

One of the central results in the theory of fault-tolerant quantum computation, 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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:accuracy threshold; error correction; fault tolerance; quantum computation
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Physics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Preskill, John P.
Thesis Committee:
  • Preskill, John P. (chair)
  • Kitaev, Alexei
  • Leung, Debbie W.
  • McEliece, Robert J.
Defense Date:11 December 2006
Record Number:CaltechETD:etd-03252007-155200
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1116
Deposited By: Imported from ETD-db
Deposited On:28 Mar 2007
Last Modified:26 Feb 2020 00:12

Thesis Files

PDF (thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page