PrimerHow Far Are Quantum Computers from Breaking RSA-2048?Part 1 of 3

Why Can Quantum Computers Accelerate Computation?

Summary

Superposition gives an exponentially parallel representation, and entanglement and interference let algorithms amplify the probability of the right answer. Problems with periodic structure, such as integer factorization, get an exponential speedup; unstructured search gets a square-root one. Once hardware scale and fault tolerance break through, Shor’s algorithm directly threatens classical public-key cryptography such as RSA-2048.

On this page
  1. Superposition and Collapse
  2. Quantum Entanglement
  3. Using Superposition and Entanglement to Accelerate Computation
  4. Quantum Computing’s Acceleration Effects on Different Problems
  5. Appendix 1: Mathematical Expression of Superposition States and Entanglement
  6. Appendix 2: How Quantum Algorithms Threaten Classical Cryptography
  7. References

In today’s digital world, classical public-key cryptography such as RSA-2048 and ECC are the most widely used encryption standards, supporting the underlying trust of network security, financial transactions, and privacy protection. However, this cornerstone is facing the potential threat of quantum computing. In theory, quantum computers can factorize large integers and solve discrete logarithms at speeds far exceeding classical computers, thereby breaking RSA and ECC encryption in a short time. This prospect is both exciting and worrying.

The question is: what stage has the development of quantum computers reached? Some optimistically believe that the “countdown” to classical public-key cryptography has already begun; others doubt that truly usable quantum computers are still far away due to manufacturing difficulties. There are various opinions in the market, often optimistic or pessimistic, but the core question always lingers: how far are quantum computers from breaking classical public-key cryptography? We will attempt to answer this question by dismantling and analyzing the manufacturing bottlenecks and breakthrough hopes of quantum computers.

First, to help readers understand the principles of quantum computing, we will introduce necessary quantum mechanics concepts, such as quantum states and entanglement, and explain why quantum computers can achieve acceleration for specific problems; second, to give everyone an intuitive understanding of the form and implementation path of quantum computers, we will analyze their basic construction and focus on dismantling the internal structure of currently fastest-developing and most engineering-feasible superconducting quantum computers; finally, using superconducting quantum computers as an example, we will deeply analyze the bottlenecks they still face in moving toward breaking classical public-key cryptography (RSA-2048), and the potential solutions behind these problems.

Our conclusion is: at the scientific level, there are no “dead ends,” and the real challenges are concentrated in engineering implementation. Cooling, control, wiring, energy consumption, and real-time implementation of quantum error correction remain huge challenges, but with the advancement of scale expansion and modular design, these problems are expected to be gradually alleviated. Considering current trends, we agree with the industry’s general prediction: million‑qubit quantum computers are very likely to appear in the 2030s, at which time the defense line of classical public-key cryptography will most likely be breached. This also means that post-quantum migration work must start as early as possible. On the one hand, the “Store Now, Decrypt Later” attack mode already exists in reality—sensitive data, even if stolen today, may be decrypted by quantum computing in the future; on the other hand, the migration of cryptographic systems itself is a huge project involving algorithm replacement, system transformation, standard compliance, and ecosystem adaptation, usually requiring many years to complete. If we wait until quantum computers are truly about to emerge before taking action, it is often too late.

The core advantage of quantum computers lies in their utilization of quantum superposition and quantum entanglement. To understand why they can accelerate computation, we first need the basic features of quantum physics—superposition, collapse, and entanglement.

Note: To make it understandable for readers unfamiliar with mathematics or physics, this section will try to avoid using mathematical formulas, which may result in some inaccuracies in details, but will not affect overall understanding. For readers with a certain mathematical foundation, you can read alongside Appendix 1, which provides a more intuitive explanation of phenomena such as superposition states, collapse, and entanglement in mathematical form.

Superposition and Collapse

In classical physics, the state of a system (such as position or velocity) is definite at any moment. In quantum mechanics, the situation is different. Before measurement, a particle’s physical quantity (such as position, momentum, spin, or energy level) is not at a specific value, but in a superposition that simultaneously contains all possible outcomes. Only upon measurement does this superposition collapse to a definite value according to a probability distribution.

A simple example: imagine two small boxes, and a particle can only appear in one of them. Classically, it is either in the left box or the right box—never both. Quantum experiments show that before measurement, the particle is in a state that “contains both left and right possibilities.” Only when we actually measure it does the particle appear in one of the boxes. This process is called collapse. During collapse, each possible outcome has a probability (these probabilities sum to 1, and the distribution is an intrinsic property of the superposition). For example, a particle might be in a superposition with:

  • Probability of appearing on the left is 70%
  • Probability of appearing on the right is 30%

This may sound incredible, but the existence of superposition states has long been verified through experiments. A classic example is the double-slit interference experiment with electrons. Interested readers can further look up related experiments.

Classical state vs. quantum superposition. Color indicates measurement probability. Figure: Classical state vs. quantum superposition. Color indicates measurement probability.

Based on this principle, quantum computers select two clearly distinguishable results from a physical system as the basic unit of information. For example, we can specify “particle in the left box” as 0 and “particle in the right box” as 1. In this way, before being measured, a qubit is not simply 0 or 1, but simultaneously contains both possibilities. When measurement occurs, it will be determined as one of them. This means that qubits can simultaneously carry information of both 0 and 1 in superposition form before measurement, which is the fundamental characteristic that distinguishes them from classical bits.

Quantum Entanglement

After seeing that a single quantity can exist in multiple possibilities via superposition, we can discuss quantum entanglement. Entanglement is a nonclassical correlation: when certain properties (such as position) of two or more particles are entangled, those properties are no longer independent but behave as a single, inseparable whole.

Example: imagine two identical boxes, one on the left and one on the right. Place two particles, labeled 1 and 2. Classically, there are four possibilities, each with some probability:

  • Both particles in the left box (denoted LL)
  • Both in the right box (denoted RR)
  • 1 in the left box and 2 in the right (denoted LR)
  • 1 in the right box and 2 in the left (denoted RL)

Classically, the particles are in one definite combination; we just don’t yet know which.

However, in quantum physics, if the two particles are prepared in an entangled state where they must occupy different boxes (an odd‑parity Bell state), then the picture changes. Before measurement, they are not fixed in any specific combination but in a joint superposition. In this state, only two possibilities exist:

  • 1 on the left, 2 on the right (LR)
  • 1 on the right, 2 on the left (RL)

Upon measurement, the system instantly collapses to one of them—either LR or RL. Each outcome has a probability (the probabilities need not be equal; the distribution is an inherent property of the entangled state), while LL and RR occur with zero probability. Thus, quantum entanglement extends the idea of superposition to multi‑qubit bases. Its existence has been confirmed in many experiments (see, e.g., EPR paradox, Bell inequality).

Classical combinations vs. outcomes from an entangled pair. Figure: Classical combinations vs. outcomes from an entangled pair.

Applying this to qubits (e.g., map L→0 and R→1), we can prepare an entangled state where the two qubits always differ. Before measurement, the pair is not definitely “01” or “10,” but a superposition of both. Measurement collapses the state to either “01” or “10,” while “00” and “11” never occur.

Using Superposition and Entanglement to Accelerate Computation

Superposition gives qubits the ability to simultaneously exist in multiple states before measurement, and entanglement allows qubits to form non-classical strong correlations, which are indispensable core resources in many quantum algorithms and quantum error correction.

Here’s an intuitive example. Suppose we have a system of nn qubits representing an input variable xx. By superposition, the state of xx can simultaneously cover all values from 00 to 2n−12^n-1, not just a single number. Feeding such a state into a function f(x)f(x) produces an output that is a superposition of all corresponding results.

If we want to find the value of xx that satisfies f(x)=cf(x)=c, we can use carefully designed quantum algorithms (involving the use of mechanisms such as quantum entanglement and quantum interference) to enhance the probability amplitude corresponding to the correct result while weakening the probability amplitude of incorrect results. In this way, during final measurement, we can obtain the correct answer with a higher probability. It should be emphasized that this process of “amplifying the probability of correct solutions” is one of the core ideas of quantum algorithms.

Core idea—superposition enables “parallelism”; making use of entanglement/interference to amplify the probability of correct solutions. Figure: Core idea—superposition enables “parallelism”; making use of entanglement/interference to amplify the probability of correct solutions.

Note: Discussing quantum interference implicitly treats quantum states in wave form. If you’re curious why microscopic quantities admit wave descriptions, see Appendix 1.

Wave interference. Constructive interference boosts amplitude; destructive reduces it. Figure: Wave interference. Constructive interference boosts amplitude; destructive reduces it.

Of course, real quantum algorithms are far more complex than this intuitive description. Here we only provide a simplified explanation and do not involve specific algorithm details for now. If readers want to further understand why quantum algorithms pose a potential threat to classical cryptographic systems, please refer to Appendix 2.

Quantum Computing’s Acceleration Effects on Different Problems

The main sources of acceleration brought by quantum computers are:

  • Superposition states, meaning nn qubits can simultaneously represent 2n2^n states, equivalent to processing all possibilities in parallel at once.
  • Entanglement, through strong correlation between qubits, allows interference between different states, thereby effectively extracting useful information and amplifying correct answers.

This acceleration manifests differently for different types of problems. When suitable quantum algorithms are available:

  • Structured problems (such as integer factorization): Quantum algorithms can utilize their structure (such as periodic structure) to quickly extract answers through certain algorithms (such as quantum Fourier transform), thereby achieving exponential acceleration.
  • Unstructured problems (such as finding xx that satisfies f(x)=cf(x)=c): Due to the lack of patterns to exploit, we can only rely on continuous N\sqrt{N} times of interference to amplify the probability amplitude of the correct answer, so the number of computations can only be reduced from the classical NN times to N\sqrt{N} times, corresponding to square root level acceleration.

Appendix 1: Mathematical Expression of Superposition States and Entanglement

Vector Expression of Superposition States and Collapse

In quantum mechanics, for a single quantum state, we can express it in vector form:

∣ψ⟩=α∣S0⟩+β∣S1⟩\begin{equation*} |\psi\rangle = \alpha |S_0\rangle + \beta |S_1\rangle \end{equation*}

Where:

  • ∣S0⟩|S_0\rangle and ∣S1⟩|S_1\rangle are two possible states of the quantum system;
  • α\alpha and β\beta are called complex probability amplitudes, whose modulus squared gives the probability of obtaining the corresponding state during measurement, and they satisfy ∣α∣2+∣β∣2=1|\alpha|^2+|\beta|^2=1.

Quantum computers select two distinguishable physical quantum states from a physical system as information carriers, denoted as ∣0⟩|0\rangle and ∣1⟩|1\rangle, respectively. Therefore, the state of a quantum bit (qubit) can be written as:

∣ψ⟩=α∣0⟩+β∣1⟩\begin{equation*} |\psi\rangle = \alpha |0\rangle + \beta |1\rangle \end{equation*}

Vector Expression of Quantum Entanglement

If two qubits are prepared in an entangled state where they must have different values (an odd‑parity Bell state), then the system’s state is:

∣ψ⟩=α∣01⟩+β∣10⟩\begin{equation*} |\psi\rangle = \alpha |01\rangle + \beta |10\rangle \end{equation*}

Where α\alpha and β\beta are complex probability amplitudes satisfying the normalization condition ∣α∣2+∣β∣2=1|\alpha|^2+|\beta|^2=1.

This means: the probability of measurement result “01” is ∣α∣2|\alpha|^2, the probability of measurement result “10” is ∣β∣2|\beta|^2, while the probabilities of “00” and “11” are strictly zero. It can be seen that quantum entanglement is actually an extension of superposition states in multi-dimensional bases.

Wave Function Expression of Quantum States

Quantum states can also be described in wave form, with the modulus square of the wave function giving the probability of collapsing to a specific state. Taking a particle confined in a one-dimensional box (with impassable walls at both ends) as an example, the particle’s waves reflect at both ends and superpose on each other (similar to sound echoing between two walls), and the wave function manifests as a standing wave.

ψn(x,t)=2Lsin⁡(nπxL)e−iωnt\begin{equation*} \psi_n(x,t) = \sqrt{\frac{2}{L}} \sin\left(\frac{n\pi x}{L}\right) e^{-i\omega_n t} \end{equation*}

Where tt is time, xx is the particle’s position, LL is the box length (range of particle motion), nn is the quantum number (1,2,3…, determining how many peaks and troughs the wave function has), k=nπLk = \frac{n\pi}{L} is the wave number (i.e., spatial frequency), λ=2πk=2Ln\lambda = \frac{2\pi}{k} = \frac{2L}{n} is the wavelength (i.e., spatial period), ω\omega is the angular frequency, and the wave’s temporal frequency f=ω2πf = \frac{\omega}{2\pi}. The probability of the particle appearing at position xx at time tt is ∣ψ(x,t)∣2|\psi(x,t)|^2. The passage of time only adds a string of rotating phase factors to the entire wave function, not affecting the probability distribution.

Wave function (real part) at t=0. Figure: Wave function (real part) at t=0.

Relationship Between Wave Function Expression and Vector Expression of Quantum States

Some readers might wonder: the state‑vector form ∣ψ⟩=α∣S0⟩+β∣S1⟩|\psi\rangle = \alpha |S_0\rangle + \beta |S_1\rangle and the wave‑function form ψn(x,t)\psi_n(x,t) seem unrelated. In fact, they are two representations of the same quantum state in different “coordinate systems.”

To describe a quantum state at a certain moment (assume t=0t=0), we must first choose a set of bases.

  • The first method uses continuous position basis {∣x⟩}0<x<L\{|x\rangle\}_{0<x<L}. In this case, the abstract quantum state can be described as ψ(x)=⟨x∣ψ⟩\psi(x)=\langle x | \psi \rangle, called the wave function, which assigns a complex amplitude to each point xx.
  • The second method uses discrete energy basis {∣n⟩}\{|n\rangle\}. In this case, the abstract quantum state can be described as ∣ψ⟩=∑ncn∣n⟩|\psi\rangle = \sum_n c_n|n\rangle, where cn=⟨n∣ψ⟩c_n=\langle n|\psi\rangle, which assigns a complex amplitude to each energy eigenstate.

These two representations are related by:

ψ(x)=∑ncn2Lsin⁡(nπxL)\begin{equation*} \psi(x)=\sum_n c_n\sqrt{\frac{2}{L}}\sin(\frac{n\pi x}{L}) \end{equation*}

These two notations are just different perspectives; they essentially describe the same physical quantity.

Appendix 2: How Quantum Algorithms Threaten Classical Cryptography

To make it understandable for readers unfamiliar with mathematics or physics, this section will minimize the use of complex mathematical formulas. This may result in some inaccuracies in details but will not affect overall understanding.

Grover’s Algorithm: Accelerating Search Problems

Suppose you have a black-box function f(x)f(x) that can determine whether a certain input xx is the correct answer:

  • f(x)=1f(x) = 1: indicates xx is the target
  • f(x)=0f(x) = 0: indicates xx is not the target

If xx is a 32-bit integer, there are 2322^{32} possible values. On a classical computer, we can only try f(x)f(x) one by one, requiring 2322^{32} tries in the worst case.

Quantum computers reduce search complexity from O(N)O(N) to O(N)O(\sqrt{N}) through superposition states and interference. The core logic of Grover’s algorithm is as follows:

  1. Construct superposition state. Quantum computers can make variable x simultaneously represent a superposition state of all possible values, that is, x=0,1,2,⋯ ,232−1x = 0, 1, 2, \cdots, 2^{32} - 1. If these values are substituted into f(x)f(x), then f(x)f(x)’s result will also be a superposition state of all possible outputs. For some xx, f(x)f(x)’s value is 0; for other xx, f(x)f(x)’s value is 1.

  2. Mark the correct answer (Oracle operation). The key to Grover’s algorithm is “marking the correct answer.” In quantum computing, this marking does not directly tell you the answer but makes the correct answer special at the quantum mechanical level through operations. For example, we do special processing on those xx where f(x)=1f(x) = 1 (i.e., correct answers): change their “phase.” Phase is a property of quantum states that, while invisible itself, can affect the probability distribution when quantum states collapse through subsequent operations. This step is equivalent to putting an “invisible mark” on the correct answer.

  3. Amplify the probability of the correct answer through interference. Next, through constructive interference, the amplitude of the correct answer is gradually amplified, and through destructive interference, the amplitude of wrong answers is gradually reduced. This can be imagined as an “amplifier”—each operation makes the presence of the correct answer stronger. Each interference operation further increases the probability of the correct answer. After approximately N\sqrt{N} Oracle operations, the probability of the correct answer approaches 1.

  4. Measure the correct answer. Finally, by measuring the quantum state, the quantum computer can almost always return the correct answer.

Grover’s algorithm (schematic). Figure: Grover’s algorithm (schematic).

Cryptographic Application Example: Breaking Hash Functions

Suppose you have a hash function f(x)f(x), know a hash value HH, and want to find some input xx satisfying f(x)=Hf(x) = H. If xx is a 4-byte integer (range 2322^{32}), classical computation requires at most 2322^{32} tries, while Grover’s algorithm only needs approximately 2162^{16} tries. This acceleration is very useful for password cracking and unordered search.

Similarly, we can also use Grover’s algorithm to accelerate breaking symmetric cryptography like AES.

Shor’s Algorithm: Accelerating Integer Factorization

Difficulty of Classical Integer Factorization

Integer factorization is a classic problem: given a large composite number NN, find two integers pp and qq greater than 1 such that N=p×qN = p \times q. When NN is the product of two sufficiently large prime numbers, classical computers need to try a large number of possible values, with time complexity growing exponentially. This is the security foundation of RSA encryption: factoring a 2048-bit integer is an almost impossible task.

How Does Quantum Computing Accelerate Integer Factorization?

First, we can transform the integer factorization problem into a “period problem” through number theory knowledge. Shor’s algorithm uses quantum Fourier transform to efficiently extract the period, thereby calculating factors. The core logic is as follows:

  1. Transform into period problem

Choose a random number aa, calculate f(x)≡ax(modN)f(x) \equiv a^x \pmod N. This calculation generates a periodic sequence, such as:

f(0)=1,f(1)=3,f(2)=9,f(3)=27,f(4)=9,f(5)=27,⋯\begin{equation*} f(0) = 1, f(1) = 3, f(2) = 9, f(3) = 27, f(4) = 9, f(5) = 27, \cdots \end{equation*}

The sequence repeats every certain length, and this repetition length is the period rr. After finding this period, we can quickly obtain a factor of NN, then recursively factorize other factors of NN.

  1. Quantum Fourier transform extracts period

In classical computation, finding the period requires trying one by one, which is very time-consuming. Quantum computing “simultaneously computes” all possible xx through superposition states. By having quantum bits accumulate phases proportional to the period in a series of controlled modular multiplication operations, then using quantum Fourier transform to convert this phase into measurable results, the function’s period rr can be extracted in polynomial time.

  1. Calculate factors

Once the period rr is known, factors of NN can be quickly factorized through simple mathematical formulas. Specifically, factors of NN can be obtained by calculating gcd(ar/2±1,N)\text{gcd}(a^{r/2}\pm 1, N).

Shor’s algorithm for factoring RSA (schematic). Figure: Shor’s algorithm for factoring RSA (schematic).

Cryptographic Application: RSA Breaking

The security of RSA encryption relies on the difficulty of integer factorization of large numbers. If a classical computer factors a 2048-bit integer, it might take billions of years. Shor’s algorithm can complete the factorization in a few hours, posing a direct threat to modern encryption systems.

References

  1. Beckman, David, et al. “Efficient networks for quantum factoring.” Physical Review A 54.2 (1996): 1034.
  2. Grover, Lov K. “A fast quantum mechanical algorithm for database search.” Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.
  3. Shor, Peter W. “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.
  4. Nielsen, Michael A., and Isaac L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
  5. Gidney, Craig. “How to factor 2048 bit RSA integers with less than a million noisy qubits.” arXiv preprint arXiv:2505.15917 (2025).
  6. Gidney, Craig, and Martin Ekerå. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5 (2021): 433.