Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.15844

Opportunities and Challenges in Fault-Tolerant Quantum Computation

Daniel Gottesman

Published Oct 28, 2022• 15 citations
arXivHTMLPDF

Abstract

I will give an overview of what I see as some of the most important future directions in the theory of fault-tolerant quantum computation. In particular, I will give a brief summary of the major problems that need to be solved in fault tolerance based on low-density parity check codes and in hardware-specific fault tolerance. I will then conclude with a discussion of a possible new paradigm for designing fault-tolerant protocols based on a space-time picture of quantum circuits.

DOI
10.48550/arxiv.2210.15844

Related papers

The Complexity of Quantum Fault Tolerance

Quynh The Nguyen

The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.

•Jan 1, 2026•0 citations

Fault-Tolerant Quantum Computation with Constant Overhead

Daniel Gottesman

What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.

arXiv:1310.2984•Oct 10, 2013•35 citations

Quantum computing in practice: fault-tolerant protocols and circuit-mapping techniques

Lingling Lao

Quantum computing promises to solve some problems that are intractable by classical computers. Several quantum processors based on different technologies and consisting of a few tens of noisy qubits have already been developed. However, qubits are fragile as they tend to decohere extremely quickly and quantum operations are faulty, making reliable computation very difficult. Moreover, quantum processors have hardware constraints such as limited qubit connectivity and shared classical control, making quantum algorithms not directly executable. This thesis focuses on some of the challenges of the implementation of quantum algorithms on near-termintermediate-scale and future large-scale quantum processors. More precisely, it investigates how to perform reliable quantum computation using fault-tolerant protocols and how to execute quantum algorithms on hardware-constrained processors using circuit-mapping techniques.

•Nov 25, 2019•0 citations

Fault-Tolerant quantum computation with constant overhead

Daniel Gottesman

What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.

Quantum Information and Computation•Nov 1, 2014•164 citations

Fault-tolerant quantum computation

Christophe Vuillot

Quantumcomputation is the modern version of Schrödinger’s cat experiment. It is backed up in principle by the theory and thinking about it can make people equally uncomfortable and excited. Besides, its practical realization seems so extremely challenging that some people even doubt it is possible. On the other hand, we are nowadays much closer to realizing quantum computation and in addition, it has much more implications than Schrödinger’s original cat experiment. One of the major difficulties in realizing quantum computation is the inevitable presence of noise in realistic quantum devices which makes the direct realization of quantum computers impossible. In order to protect quantum information and quantum processes against noise, quantum error correction and fault-tolerance have been devised. Although the gap between experiments and the requirements of fault-tolerance is still daunting, the field of quantum error correction and fault-tolerance extends and influences architectural decisions from the hardware to the ideal quantum programs that we want to run. That is why it has the potential to make or break the practicality of quantum computation and a lot of research effort goes into this field. In this thesis we investigate and improve several aspects of fault-tolerant schemes and quantum error correction. We implement an experiment which validates on a small device the usefulness of fault-tolerance for quantum computation. We investigate the advantages of harnessing quantum continuous degrees of freedom present in the lab to protect discrete quantum information in a scalable way. We establish a framework to analyze the fault-tolerant properties of code deformation techniques which are versatile techniques to process quantum information protected by an error correcting code. We also present some novel code deformation techniques with the potential to increase reliability. Finally we define a new class of quantum error correcting codes, quantum pin codes, with built in capabilities for fault-tolerant quantum gates. We give some practical constructions and show some protocols with interesting parameters. The roads towards universal and fault-tolerant quantum computation are still steep but research efforts are pushing in the right directions.

•Dec 16, 2019•2 citations

Quantum fault tolerance in small experiments

Daniel Gottesman

I discuss a variety of issues relating to near-future experiments demonstrating fault-tolerant quantum computation. I describe a family of fault-tolerant quantum circuits that can be performed with 5 qubits arranged on a ring with nearest-neighbor interactions. I also present a criterion whereby we can say that an experiment has succeeded in demonstrating fault tolerance. Finally, I discuss the possibility of using future fault-tolerant experiments to answer important questions about the interaction of fault-tolerant protocols with real experimental errors.

arXiv:1610.03507•Oct 11, 2016•34 citations
I will give an overview of what I see as some of the most important future directions in the theory of fault-tolerant quantum computation. In particular, I will give a brief summary of the major problems that need to be solved in fault tolerance based on low-density parity check codes and in hardware-specific fault tolerance. I will then conclude with a discussion of a possible new paradigm for designing fault-tolerant protocols based on a space-time picture of quantum circuits.
The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.
Quantum computing promises to solve some problems that are intractable by classical computers. Several quantum processors based on different technologies and consisting of a few tens of noisy qubits have already been developed. However, qubits are fragile as they tend to decohere extremely quickly and quantum operations are faulty, making reliable computation very difficult. Moreover, quantum processors have hardware constraints such as limited qubit connectivity and shared classical control, making quantum algorithms not directly executable. This thesis focuses on some of the challenges of the implementation of quantum algorithms on near-termintermediate-scale and future large-scale quantum processors. More precisely, it investigates how to perform reliable quantum computation using fault-tolerant protocols and how to execute quantum algorithms on hardware-constrained processors using circuit-mapping techniques.
Quantumcomputation is the modern version of Schrödinger’s cat experiment. It is backed up in principle by the theory and thinking about it can make people equally uncomfortable and excited. Besides, its practical realization seems so extremely challenging that some people even doubt it is possible. On the other hand, we are nowadays much closer to realizing quantum computation and in addition, it has much more implications than Schrödinger’s original cat experiment. One of the major difficulties in realizing quantum computation is the inevitable presence of noise in realistic quantum devices which makes the direct realization of quantum computers impossible. In order to protect quantum information and quantum processes against noise, quantum error correction and fault-tolerance have been devised. Although the gap between experiments and the requirements of fault-tolerance is still daunting, the field of quantum error correction and fault-tolerance extends and influences architectural decisions from the hardware to the ideal quantum programs that we want to run. That is why it has the potential to make or break the practicality of quantum computation and a lot of research effort goes into this field. In this thesis we investigate and improve several aspects of fault-tolerant schemes and quantum error correction. We implement an experiment which validates on a small device the usefulness of fault-tolerance for quantum computation. We investigate the advantages of harnessing quantum continuous degrees of freedom present in the lab to protect discrete quantum information in a scalable way. We establish a framework to analyze the fault-tolerant properties of code deformation techniques which are versatile techniques to process quantum information protected by an error correcting code. We also present some novel code deformation techniques with the potential to increase reliability. Finally we define a new class of quantum error correcting codes, quantum pin codes, with built in capabilities for fault-tolerant quantum gates. We give some practical constructions and show some protocols with interesting parameters. The roads towards universal and fault-tolerant quantum computation are still steep but research efforts are pushing in the right directions.
I discuss a variety of issues relating to near-future experiments demonstrating fault-tolerant quantum computation. I describe a family of fault-tolerant quantum circuits that can be performed with 5 qubits arranged on a ring with nearest-neighbor interactions. I also present a criterion whereby we can say that an experiment has succeeded in demonstrating fault tolerance. Finally, I discuss the possibility of using future fault-tolerant experiments to answer important questions about the interaction of fault-tolerant protocols with real experimental errors.