| ▲ | rendaw 5 days ago | |
Is there a qubit-speed tradeoff, where you could factor 2048 bit RSA integers with fewer qubits but it would take more time? Or is it all or nothing? | ||
| ▲ | adgjlsfhk1 5 days ago | parent | next [-] | |
there is a trade-off, but it doesn't help too much because of you take more time, you need more error correction which takes more qbits. the best trade-off probably comes from dropping the error correction to the point where you go from 99% reliability to 1% reliability. doing so will increase your rsa factor time from ~1 week to ~1 year and probably saves you ~an order of magnitude in qbits The big thing that could change the numbers is more reliable qbits. Most of the calculations so far are done with qbits right at the edge of where error correction works (about 5x better than current qbits). if you get another 10x in qbit quality you probably drop the required qbits by ~100-1000x. | ||
| ▲ | Strilanc 3 days ago | parent | prev [-] | |
Realistic Shor circuits have depth polynomial in n, but you can easily construct ones whose depth is polylogarithmic in n. Just do the multiplications as a binary tree instead of in a linear order, using log depth multiplication circuits, and then do the frequency basis measurement using a low depth QFT [1]. The only part that isn't known to be doable in polylog depth is the classical GCD computation hiding in the classical postprocessing, to find the closest fraction to get the period. The result is that, if you keep adding qubits that can be operated on in parallel, Shor's algorithm basically just keeps getting faster and faster and faster. The energy cost doesn't go down, and the number of qubits required becomes frankly absurd, but the time can go really really low. | ||