Fault tolerance that will realize the transformative promise of quantum computing

Fault tolerance means that we can design reliable quantum circuits, despite the inevitable flaws in quantum bits (qubits) and gates.

In a fault-tolerant quantum computer, the reliable "logical" quantum bits and gates that run the user's algorithms are in turn made up of a large number of noisy "physical" quantum bits and gates. Only by connecting and controlling a large number of physical quantum bits and gates in the right way can a noisy quantum device be transformed into a reliable computing machine.

Scientific breakthroughs and "transformative applications" such as faster drug development cycles, new materials for batteries, fertilizer manufacturing and carbon capture will revolutionize society and the economy, but why do these transformative applications need to be fault tolerant? Because even the most demanding applications require millions of gates of quantum circuitry; only a fault-tolerant quantum computer can run that many gates without turning the output into an unstructured stream of random numbers.

The gate and quantum bit requirements of these transformative applications have been an active area of research over the past five years, with contributions from key teams in academia and industry. Academic teams at Caltech, ETH, Macquarie University, University of Maryland, University of Sherbrooke, University of Toronto, University of Vienna, and University of Washington, quantum hardware manufacturing teams such as Google, Microsoft, PsiQuantum, and Xanadu, as well as teams exploring quantum applications at BASF, Boehringer Ingelheim, Mercedes-Benz, and Volkswagen have all have made significant contributions.

These so-called resource estimates provide a concrete target for future fault-tolerant quantum computers in terms of the number of logic quantum bits and the number of logic gates. Below is a simplified table summarizing the number of logic gates required for the transformative applications mentioned above:

Unfortunately, today's NISQ devices cannot run circuits with so many gates because they are too noisy to run more than a few hundred gates before their output is no longer reliable and useful: then their output becomes garbled. This occurs because each gate run on a computer adds a bit of noise to the quantum state; with each additional gate, the noise grows exponentially until the result is dominated by noise. Even when noise mitigation techniques are employed, they require a large number of repetitive operations and are therefore not feasible, and often require an unimaginably large number of experimental runs with a method similar to lever extrapolation, whose outputs are not credible due to the large and often uncontrolled errors in the outputs.

A good example is the Sycamore chip that Google used in its 2019 Quantum Hegemony demonstration. The experiment involved 53 quantum bits and 20 noisy double quantum bit gates, which dominated the errors on the device. The largest supercomputers had difficulty simulating the output of "Suzuki" after these 20 gates. However, the fidelity of its output to the target state is only 0.002 - essentially, after 20 gates, the device functions as a uniform random number generator. It's true that two-thousandths of a percent output is enough to beat a supercomputer, but it will be a while before the output of these devices is reliable and useful.

This observation is not meant to criticize Google's experiment, as it is indeed a laudable achievement. Rather, we want to emphasize that the NISQ era is a dangerous place for quantum information: even with dozens of gates acting on dozens of quantum bits with more than 99% fidelity, quantum information deteriorates rapidly. As the circuit goes deeper, the problem gets worse: the overall fidelity drops further, and the output gets closer and closer to a stream of nearly unstructured random numbers.

The challenge now is to move from the less than 100 gates that can be applied on today's NISQ devices to the tens of millions of gates needed for transformative scientific applications, and the billions of gates needed for transformative commercial applications. Fault-tolerance will allow us to bridge this 10,000-fold gap, which is why many of the most powerful teams in quantum computing are working to build fault-tolerant quantum computers.

How can the true promise of quantum computing be realized through fault tolerance?

So how does the possibility of reliable computing fulfill the true promise of quantum computing through fault tolerance?

Bridging the 10,000-fold gap will require progress on three fronts:

1) First, already very complex algorithms need to become smarter in order to perform the same computation with fewer gates;
2) Second, hardware needs to get better so that it can be fault tolerant;
3) Finally, we need better fault-tolerant architectures to address the shortcomings in the actual hardware and to maximize the logical performance of the hardware.

Now, let's look more closely at what is required for useful quantum computing: what are the algorithms that enable these breakthroughs, and how many quantum bits and gates do these algorithms require to provide useful results? Finally, why is fault tolerance necessary to realize this promise?

1) Quantum simulations will power the first applications that will transform society and the economy

Quantum computers are expected to outperform classical computers in numerous tasks. One of the most important commercial applications is quantum simulation, a kind of "virtual chemistry lab". In this virtual laboratory, we can simulate and study the behavior of quantum systems such as molecules or materials.

Quantum simulation is likely to be the first task to bring practical economic and social benefits. This is because quantum simulation involves modeling other quantum systems, which is what quantum computers are good at. More specifically, other quantum computing applications with specific commercial impacts are more computationally expensive, such as the cost of factorization studied by researchers at Google and PsiQuantum through Shore's algorithm.

Users of the Quantum Simulation Virtual Laboratory provide descriptions of quantum systems, such as how the electrons and nuclei of molecules interact with each other. The lab then discovers important properties of the quantum system, including the energy values of common configurations of that quantum system that can be realized through virtual experiments. These configurations include several of the most stable conditions in the system, and energetic configurations of molecules and materials are key to advances in several fields. For example, in chemistry, they reveal how reactions occur, helping to generate ideas for designing efficient catalysts; in pharmaceuticals, they predict how drug molecules will interact with their targets, helping to design more effective drugs; and in materials science and nanotechnology, these energy states determine the properties of materials, from electrical conductivity to chemical reactivity.

The lab focuses on two main areas: molecules (e.g., those in drugs) and materials (e.g., those used in electric car batteries). Modeling molecules involves dealing with the regions of space where electrons are most likely to be found, called "electron-molecule orbitals". While modeling more orbitals improves accuracy, it also increases computational cost. For materials, the challenge is even greater because they contain far more electrons than can be directly modeled. However, by focusing on the lattice of repeating patterns of atoms in a material, we can effectively characterize the entire material.

In order to obtain energy levels with the desired accuracy, the simulation should capture the appropriate number of energy levels and be performed with the appropriate precision. Obtaining more accurate results from the laboratory requires more quantum bits and more gates. Therefore, we need to strike a balance in finding the most efficient quantum circuits to provide the accuracy of energy values required by the user.

This presents us with a major challenge: all these requirements imply huge computational costs: we are talking about tens of millions of gate circuits acting on hundreds of quantum bits. This is clearly not achievable with NISQ devices, and this is where fault tolerance comes in.

In order to achieve fault tolerance, we need to build fault-tolerant "logical bits" from thousands of "physical bits". By applying a large number of gates to these physical bits, efficient "logic gates" can be executed on these logical bits. These logical quantum bits utilize this redundancy to hide relevant information in intricate superpositions that are spread over thousands of physical quantum bits and are unaffected by noise at the physical level. Designing these intricate combinations is the science and art of fault tolerance.

Thinking about these requirements again, billions of physical gates applied to hundreds of thousands of physical quantum bits is the equivalent of tens of millions of logic gates applied to thousands of logic quantum bits, which is what is needed to realize the true promise of quantum computing.

2) New methods for manufacturing fertilizers and carbon capture

One of the most promising applications of quantum simulation is to help develop new and more efficient methods for manufacturing fertilizers. This area is very interesting because the current industrial processes for producing fertilizers require high pressure, high temperature, and significant energy consumption. In contrast, plants perform a similar nitrogen-fixing task at room temperature and pressure with much less energy consumption. The ferric ink cobalt molecule is a key component of this natural process, and it can provide us with a deeper understanding of how plants achieve this feat, and how we can learn from it to design better fertilizer manufacturing processes. We have studied the molecule extensively and it is now considered a benchmark task for quantum simulations.

A 2016 work by Microsoft and the Federal Institute of Technology comprehensively discusses how quantum simulations can be used to understand reactions such as nitrogen fixation. This work showed that base state calculations using quantum simulations can help determine the structure of intermediate molecules and all the steps involved in a reaction, leading to a comprehensive understanding of the chemical mechanism.

Fast-forward to 2019, and researchers at Google, Macquarie University, and Caltech introduced an efficient algorithm for simulating molecules like FeMoCo in a study. Their estimates suggest that simulating the active space of the FeMoCo molecule might require about 1011 Toffoli gates acting on millions of physical bits.

The following year, 2020, another study from Google, Pacific Northwest National Laboratory, Columbia University, Macquarie University and the University of Washington proposed an algorithm to efficiently simulate arbitrary molecules. The authors analyzed the performance of the algorithm and showed that a useful simulation required more than 2,000 logic quantum bits and more than 109 gates.

In addition to nitrogen fixation, some work has been done on carbon capture to combat climate change.2020 Microsoft and the Federal Polytechnic Institute (ETH) conducted a study that estimated the computational cost of determining the ground-state energy involved in catalyzing atmospheric carbon into methanol for several different structures. These calculations require about 1010-1011 Toffoli gates and about 4,000 logic quantum bits.

3) Designing new batteries

Improvements in rechargeable batteries, which are used in everything from electric cars to smartphones, could have significant economic and environmental benefits. As a result, new battery designs that offer higher energy density, longer life and faster charging times are highly sought after.

Quantum simulation algorithms can help investigate these properties in novel battery designs, including new materials for cathode and anode components, and innovative molecules for electrolytes. Several teams have already delved into how quantum simulation can drive novel battery designs.

In 2022, PsiQuantum partnered with Mercedes-Benz to explore the use of quantum simulations to study electrochemical reactions in battery electrolytes. While most of the resource estimates focused on photonic architectures, it did show that T-gate depths in excess of 109 are necessary.

In a 2022 study, Xanadu, Volkswagen, and other research groups provided a detailed step-by-step procedure for estimating the ground-state energy of an important battery cathode material: lithium iron silicate. They estimate that these simulations require more than 2,000 logic quantum bits and more than 1013 Toffoli gates.

In a recent follow-up work in 2023, Xanadu and Volkswagen improved the algorithm for simulating lithium-excess cathode materials, which are expected to be used in new high-energy-density batteries. Using this improved algorithm, the authors report that even simulating more demanding materials requires a similar number of more than 2,000 logic quantum bits and 1,013 Toffoli gates.

Another recent advance was made this year by a team from Google, QSimulate, BASF and Macquarie University, who presented an improved method for simulating materials. They applied this method to calculate the cathode structure of lithium nickel oxide (LNO) batteries, which are considered a potential replacement for current car batteries. They found that these simulations required more than 1012 gates acting on more than 107 physical bits.

While these developments are certainly promising, the challenge of actually applying these new materials to a state suitable for mass production is likely to be enormous; this could reduce the premium on "quantum advantage" to a very low level. However, given that batteries are expected to have a major impact on the future of energy and transportation, any small premium may be worth it.

4) Accelerating drug development

As mentioned earlier, quantum simulations help to understand the kinetics of chemical reactions. They do this by determining the ground state energies of the various reactants and intermediates involved in the reaction. It is therefore not surprising that quantum simulations help predict the intended and unintended effects of drugs. This is the reason why powerful simulations are utilized to speed up the drug discovery process, as quantum simulations can accurately render chemical properties in the laboratory.

Several recent studies have estimated the cost of quantum computing for molecular simulations related to drug development:

In 2022, Google, Boehringer Ingelheim, and QSimulate collaborated on a simulation of cytochrome P450. This work showed that over 109 gates of computation on more than 103 logic quantum bits were required to perform a ground state energy calculation.

Later that year, researchers at Riverlane and Astex Pharmaceuticals studied Ibrutinib, a drug used to treat non-Hodgkin's lymphoma. They calculated the resources needed to study the drug using different methods, determining that non-trivial computations would require more than 1011 T-gate counts acting on more than 106 physical quantum bits.

More recently, in 2023, building on previous work by Google, Boehringer Ingelheim, and others, PsiQuantum, QC Ware, and Boehringer Ingelheim introduced a method that allows for the direct computation of molecular observables, rather than just calculating the ground state. These advances are crucial for drug design, as calculating molecular forces helps to model molecular dynamics. The researchers estimate that this algorithm would require more than 1014 gates running on thousands of logic quantum bits to produce meaningful results.

While this work provides strong evidence that future fault-tolerant quantum computers will be able to simulate these specific systems, recent work has also examined whether all quantum systems can accommodate exponential dominance. The answer is no, though the authors note that in general quantum systems, quantum computers can still prove useful for ground-state quantum chemistry through polynomial acceleration.

5) Scientific breakthroughs

Much of the work considers simulating quantum mechanical models relevant to open scientific questions, including those that help understand and design high-Tc superconductors.

For example, in 2018, a team from Maryland demonstrated that simulating the time evolution of a spin-½ Heisenberg chain requires about 107 single- and double-quantum-bit gates for the parameter n=t=100 and an approximation error of 0.001.

Subsequently, Microsoft and USherbrooke undertook a collaboration in 2020 focusing on quantum simulations of the Hubbard (Hubbard) model, which is crucial in the study of high telluric superconductivity. They found that it takes about 107 gates to prepare the ground state of the 100-qubit Hubbard model.

Since 2011, quantum field theory simulations have emerged as an area where quantum simulations can aid scientific discovery. Developing and improving algorithms for fault-tolerant quantum computers has become a focus of the field.

A 2019 paper by Google, Harvard University, Macquarie University, and the University of Toronto shows that careful study of errors that occur in different subroutines of a quantum simulation can greatly improve the efficiency of the simulation. This work examines simulations of simple solid-state materials such as lithium hydride, graphite, and diamond, as well as two typical models of solid-state physics: the uniform electron gas model and the Hubbard model. Simulations of these systems can be accomplished with 107-109 gates acting on 105-106 physical bits. These numbers are well beyond the current state of the art, but appear to be easier to achieve than quantum chemical simulations, so these may be the first breakthrough applications of quantum simulations.

The circuits and algorithms behind -

Next, we will explain the implementation of fault-tolerant quantum computing using more rigorous technical language.

Quantum fault-tolerance and quantum error-correction theory provide a range of techniques for dealing with imperfect operations and unavoidable noise in physical hardware, but at the cost of a modest increase in resource overhead. In the basic model of fault tolerance, we assume that each fundamental component of a quantum circuit (including verification gates) may fail with a small but non-zero probability, independent of the other components, and that classical information processing is noise-free. For concreteness and simplicity, we may choose to model any noisy component as an ideal component followed (or in the case of measurements, preceded) by some bubbly channel acting on a subset of the same quantum bits.Let be a quantum circuit (possibly with classical inputs and outputs) describing the desired quantum algorithm.Since each component of may fail, we should not implement directly;Instead, we need to implement a different quantum circuit , which is a fault-tolerant (FT) version of . This in turn can be achieved by replacing each quantum bit in with a logical quantum bit encoded in some kind of quantum error correction (QEC) code (as shown in the figure), so that the required quantum computation can be realized at the logical level of without having to leaving the protective coding guaranteed by the QEC code.

The basic idea of the proof of the threshold theorem in this is as follows. Assuming the above basic model of fault tolerance, for a sufficiently small physical error rate p, the logical error rate of should be less than p, since is the FT realization of . By repeating this process, one can eventually obtain a quantum circuit . The logical error rate of is less than ϵ. The resulting FT protocol is based on a tandem QEC code.

We can extend the threshold theorem in a number of ways. Even using the basic model of fault tolerance, we can choose different failure probabilities for each of the basic components of a quantum circuit, e.g., the failure probability of a measurement is ten times higher than the failure probability of a gate. We can consider more generalized noise (including systematic errors such as overrotation) due to weak interactions between the system and the non-Markovian environment. In general, although experimental implementations of quantum computing may not fully satisfy the assumptions of the threshold theorem, we expect the main conclusions to hold as long as they are not excessively violated.

To simplify the analysis of FT schemes, we usually assume that the classical computational power is infinite, e.g., we need to process error syndromes in QEC gadgets and infer appropriate recovery operators; we have developed many such decoding algorithms for QEC with surface codes.However, in some cases we need to take into account the finite speed of classical information processing. If the classical units that process error syndromes cannot keep up with the rate at which they are generated, the error syndromes will begin to accumulate and one will encounter the so-called backlog problem; subsequently, the speed of quantum computation will decrease exponentially and the computational advantages of quantum computation will be lost. This problem is particularly acute in polynomially accelerated quantum algorithms.

The ability to realize arbitrary unitary operations exactly or approximately is a prerequisite for performing quantum computation. This can be achieved by constituting a universal gate set of unitary gates.The set of gates commonly considered contains two Clifford gates: the Hadamard gate H and the controlled-X gate CX (also known as the controlled NOT gate), and one non-Clifford gate: gate.We can also consider other non-Clifford gates, such as the Toffoli (Toffoli) gate CCX. to protect quantum information from the deleterious effects of noise, we can encode it into the code space of some kind of quantum error correcting (QEC) code.

(a) Planar layout of data and auxiliary quantum bits (white and yellow dots, respectively) with entanglement gates (green edges) located only between neighboring quantum bits. This layout produces an L × L square lattice with open boundary conditions, here L = 5.(b) The surface code can be realized by measuring the bubblegum Z- and X-type parity (bright and dark surfaces, respectively). The error syndromes (red and blue stars) can be interpreted as string endpoints similar to the bubbleley X and Z errors (red and blue dashed lines, respectively).

(a) The planar arrangement of quantum bits consists of surface coding patches (shaded), each of which uses the layout depicted in Fig. (a) and encodes the logical quantum bits, as well as the routing space in between. (b) Logical soakaway measurement is achieved by preparing the routing space quantum bits (turquoise dots) in the |0⟩ state and repeating the parity measurement in the routing space between the two surface code patches (light shading). Other logical bubbleley measurements, such as and , are required to connect different boundaries of the two patches.

Considering the promise of the applications, and the enormous costs involved in realizing them, it is not surprising that a number of research teams have invested a great deal of effort in developing improved algorithms to simulate molecules and materials with greater accuracy. In the process, every element of these algorithms has been improved. The interactions between different elements have also been carefully optimized. In particular, we identified errors arising from the approximations in these algorithms and systematically optimized the costs associated with reducing these errors.

The result of this ongoing process has been a series of increasingly sophisticated algorithms that have led to decreasing costs. To get a sense of the innovations in the field, the table below highlights the gradual reduction in the number of quantum bits and gates required, as well as the innovations behind these cost reductions.

Where is the future headed?

Trying to predict the future of quantum computing today is akin to predicting flying cars and ending up with cameras in our cell phones. However, many researchers agree that several milestones are possible in the next decade.

We have already seen how numerous research teams are scrutinizing the cost of performing useful simulations on different molecules and materials. Evaluations of meaningful quantum simulations consistently show huge computational costs: astronomical gates acting on the same number of quantum bits. Ideally, these algorithms would be cheaper, but unfortunately this is not the case. We've seen the cost of running these algorithms decrease rapidly, but it's still a factor of 10,000 away from the number of gates needed for useful quantum computing. The only viable way to realize these transformative applications of quantum computing is to use fault-tolerant technology.

That's why several hardware teams are working to build fault-tolerant quantum computers one step at a time.

Demonstrating true "quantum superiority" will also be a possible development. This means a compelling application where quantum devices are indisputably superior to digital devices. A stretch goal for the next decade is to create a large-scale quantum computer that is error-free (active error correction).

When this is achieved, we can be sure that the 21st century will be the "quantum age".