3 ms·

The amount of error correction you need is more than what the five qubit code provides. A more typical estimate is that you'd need 1000 physical qubits per logi

The amount of error correction you need is more than what the five qubit code provides. A more typical estimate is that you'd need 1000 physical qubits per logical qubit. For example, using the surface code, a back of the envelope estimate would be that you need a code distance of d = ln(number_of_operations). Each logical qubit will use 2d^2 physical qubits. So for a million operations you'd need around 400 physical qubits per logical qubit and for a trillion operations you'd need around 1500 physical qubits per logical qubit. So, way more than 5. (A major practical obstacle to using almost-anything-that-isn't-the-surface-code is that the surface code has forgiving connectivity and maximum-allowed-physical-noise requirements.)

XorNot 4y ago
The other issue when you start talking about very large numbers of qubits is that they're not independent. Building more qubits influences your noise environment substantially. Expectations of a Moore's law type improvement rate are going to be left wanting.
gronky_ 4y ago
So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?
- Strilanc 4y ago
  If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction. Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower. ...but don't forget that "if the paper is correct" bit.

XorNot 4y ago

The other issue when you start talking about very large numbers of qubits is that they're not independent. Building more qubits influences your noise environment substantially. Expectations of a Moore's law type improvement rate are going to be left wanting.

gronky_ 4y ago

So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?

Strilanc 4y ago
If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction. Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower. ...but don't forget that "if the paper is correct" bit.