Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?

Question

A paper titled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits has just come out which proposes a technique to factor RSA keys with moduli up to 2048 bits with a design whose assumptions they stress are realistic. What are the implications of this new research?

The abstract of the paper, which lists some of the assumptions:

We significantly reduce the cost of factoring integers and computing discrete logarithms over finite fields on a quantum computer by combining techniques from Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Eker-Hstad 2017, Eker 2017, Eker 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of $10^{−3}$, a surface code cycle time of 1 microsecond, and a reaction time of 10 micro-seconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses $3n+0.002n\lg n$ logical qubits, $0.3n^3+0.0005n^3\lg n$ Toffolis, and $500n^2+n^2\lg n$ measurement depth to factor $n$-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

How feasible would it be to design a quantum computer with these properties? 20 million qubits is obviously significantly more than any general purpose quantum computer has right now, but the paper also points out that the qubits only need nearest neighbor connectivity, which is much simpler.

Answer 1

I'm one of the authors of the paper.

In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others.

1. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various places in our registers so that we can perform addition operations in piecewise fashion and also avoid normalizing modular integers into the [0, N) range until the end of the computation. There are information leakage issues that we had to solve in order to apply these operations in a quantum context, and these cause the representation with padding to be approximate, but otherwise it's a known standard classical technique (e.g. it's called "nails" in GMP).

   Modular addition using these approximate representations are significantly more efficient than modular adders using the normal representation. For example, here is a comparison of the time*space of each addition when targeting a 0.1% total approximation error rate over the entire algorithm. The "runway" entries are the ones using the approximate representations. The runway entries are significantly better across the entire span of register sizes:

   

   These representations build on previous work by Zalka from 2006.

2. "Windowed quantum arithmetic". Classically, if you know what constant you are going to multiply by when producing a physical multiplication circuit, you can specialize the circuit to that factor. This allows you to make the circuit smaller and more efficient. There is a quantum equivalent to this optimization, where the quantum program can be optimized using knowledge of the classical constant you are going to multiply by. We use this to make n-bit quantum-classical multiplication programs log(n) times shorter.

   

   We then generalize the technique, apply it simultaneously to the exponentiation part of the circuit, and save another factor of log(n).

   This paper builds on previous work by R. Van Meter from 2005 (although we didn't actually know this when writing the paper, so it is not cited in the current version).

3. "Flexible layout of surface code computations using AutoCCZ states". This one is by far the most quantum-mechanics-y, so I won't try to explain the details. You can think of it as finding a better way to pack the computation, reducing the amount of space overhead used when routing data around and also allowing it to progress at a rate limited by the classical control system's reaction time instead of by the error correction code distance.

   The main contribution here may actually be saying what the layout is in the first place, as opposed to just talking about it in the abstract. We have an operating area where the ripple-carry addition zig-zags back and forth horizontally, while input data streams through vertically, and the operating area is gradually moved as the data is processed.

   Location of data (rows from top to bottom) over time (left to right):

   

   A mocked up snapshot of the 2d data layout during a small amount of time:

   

   The ideas in this paper build on previous work by Fowler from 2012.

In summary, there are a lot of ideas in the paper but they are not radically new (they build on previous work) and they are not strongly coupled (if one is wrong, the others will still stand). So I see the savings as being on pretty strong footing. I'm more worried about whether or not people will be able to build quantum computers with 20M qubits than I am about the estimate being off by a factor of 2.