How Many Qubits are Necessary?

A common question arises: how many qubits are required to breach RSA encryption? Initial searches might suggest a figure as low as 4,000, but this can be misleading. A more reliable answer can be drawn from a comprehensive 2019 study by Gidney and Ekera.

Though a few thousand qubits might theoretically suffice to factor a 2048-bit number in an ideal scenario, these qubits must be practically noiseless. How noiseless? The best-known method involves executing several billion gates and measurements in succession. Thus, for Shor’s algorithm, a qubit is deemed "noiseless" if its operation error falls well below 1e-9, or 0.0000001%.

This requirement is a far cry from what current technologies can offer. The solution lies in employing quantum error correction. With innovative fault-tolerant approaches, we can utilize a substantial number of "noisy qubits" to effectively encode fewer "noiseless qubits."

So, how many noisy qubits do we need? According to the leading algorithm available today, with an operation error rate of 0.1%, approximately 1,500 "noisy qubits" are needed to encode a single "noiseless qubit." In total, to factor a 2048-bit number within about eight hours, we would require around 14,000 "noiseless qubits," which translates to 20 million noisy qubits.

Current State of Quantum Computing

How do these theoretical requirements stack up against experimental realities? Let’s examine Google's Sycamore processor, renowned for its demonstration of quantum computational advantage, to identify what enhancements would be necessary to breach RSA encryption.

The specifications reveal:

• Gate error: 0.6% – This is close, needing just a tenfold reduction.
• Read-out error: 3.8% – Read-out is vital for quantum error correction and requires a two-order-of-magnitude improvement to dip below the 0.1% threshold.
• Qubit count: 53 – An increase by six orders of magnitude to reach 20 million is necessary.

It’s clear where the challenges lie. Although some advanced experiments have shown the potential of utilizing multiple noisy qubits to create a single noiseless qubit, a truly noiseless qubit has yet to be realized. While qubit counts are increasing, current quantum computing technologies typically feature around 10 to 100 qubits. IBM is forecasting the use of 1,000-qubit chips in 2023. However, no one has yet discovered how to manage millions of qubits simultaneously, leaving us in uncharted territory filled with potential surprises and challenges.

Assessing Your Risk

So how concerned should you be about the implications of quantum computing? The answer largely hinges on the sensitivity of the information you need to protect.

First, the good news: quantum computers are not poised to dismantle all public-key cryptography. A variety of quantum-safe protocols have been identified, and researchers are diligently developing new standards and implementations. It is likely that by the time a quantum computer capable of breaking RSA-2048 is constructed, we will have transitioned to a quantum-safe protocol.

On the downside, any messages transmitted and intercepted prior to this shift could potentially be decrypted later. For most individuals, this isn’t a significant concern. The critical question to ponder is:

"Is any message I send today valuable enough that someone would invest eight hours of processing time on a multi-billion-dollar machine to decrypt it in ten or twenty years?"

For those few who might answer yes (and if so, please reach out!), it might be wise to reconsider your encryption methods. For the majority of us, however, there are far less costly methods for adversaries to gain access to our secrets today. The best course of action remains to use randomly generated passwords and enable two-step authentication. The likelihood of falling prey to a phishing scam far exceeds the risk from Google's quantum computer.