The Genesis of Quantum Computing: From Classical Limitations to a New Computational Paradigm

The persistent physical bottlenecks of classical computing have long constrained humanity’s ability to model and solve problems rooted in quantum mechanical systems, a limitation that became increasingly apparent as computational demands grew in fields ranging from materials science to cryptography. In 1981, at the inaugural “Physics and Computation” conference hosted by the Massachusetts Institute of Technology (MIT), theoretical physicist Richard Feynman delivered a landmark lecture titled *Simulating Physics with Computers*, formally proposing the core concept of quantum computing. Feynman’s argument cut directly to the fundamental physical limits of classical computation: all microscopic systems in nature evolve according to quantum mechanical laws, but simulating such systems with classical computers requires computational resources that grow exponentially with system size. Taking the simulation of a quantum many-body system as an example, he noted that to accurately describe the state of n interacting quantum particles, a classical computer must store $2^n$ complex probability amplitudes, each corresponding to an orthogonal basis state in the Hilbert space of the quantum system. This exponential growth means that even simulating a simple quantum system of just 50 spin particles requires approximately 1 petabyte (1 PB, or $10^{15}$ bytes) of storage space, approaching the storage capacity limit of the world’s top supercomputers; scaling the system to 100 particles pushes required storage to roughly $1.27 \times 10^{30}$ bytes, equivalent to 10 million times the total global storage capacity of all electronic devices combined, making it physically impossible to implement. Feynman closed his lecture with the famous assertion: “Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical.” This statement directly defined the core value of quantum computing: using quantum systems themselves to simulate other quantum systems avoids the exponential complexity bottleneck of classical simulation, enabling efficient computational modeling of natural laws.

Feynman’s lecture outlined the vision of quantum computing, but it was not until 1985 that Oxford University theoretical physicist David Deutsch completed the formal theoretical framework for the field. In his paper *Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer*, Deutsch proposed the mathematical model of the Universal Quantum Turing Machine (UQTM), proving that quantum computing is computationally equivalent to (and more powerful than) the classical Turing machine, while satisfying an extended form of the Church-Turing Principle: any physically realizable computational process can be efficiently simulated by a universal quantum Turing machine. Deutsch’s work clarified the computational paradigm of quantum computing: unlike the deterministic state of a classical Turing machine (which occupies only a definite 0 or 1 state at any given time), the state of a quantum Turing machine is a unit vector in Hilbert space, with its evolution following the unitary transformation rules of the Schrödinger equation. This characteristic directly endows quantum computing with quantum properties such as superposition and entanglement that are absent in classical computing.

Building on Deutsch’s work, IBM researcher Charles Bennett and others constructed a complete theoretical framework for Quantum Information Theory in the early 1990s, with two core theorems that define the feasibility boundaries of quantum computing. The first is the No-Cloning Theorem, which states that an arbitrary unknown quantum state cannot be perfectly copied. Due to the collapse property of quantum measurement, any attempt to copy an unknown quantum state introduces disturbance, leading to deviations between the copied state and the original state. This property is the foundation of the security of quantum cryptography, and also means quantum computing cannot implement redundant backups by simple copying as classical computing does, requiring special quantum error correction codes for error mitigation. The second is the mathematical description of quantum entanglement: for a system of n qubits, its state space is a $2^n$-dimensional Hilbert space, where any two qubits can exhibit non-local correlation, i.e., an entangled state. Taking the most typical two-qubit Bell state as an example, its mathematical expression is: $$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$ In this state, the measurement results of the two qubits are always fully correlated: if measuring the first qubit yields 0, the second qubit will inevitably collapse to 0; if the result is 1, the second will collapse to 1, regardless of the distance between the two qubits. Einstein referred to this correlation as “spooky action at

Einstein’s 1947 description of quantum entanglement as “spooky action at a distance” crystallized the deepest conceptual divide in 20th-century physics, a divide that would later become the foundational resource for quantum computing. At the time, Einstein viewed entanglement as evidence that quantum mechanics was an incomplete theory, arguing in the 1935 Einstein-Podolsky-Rosen (EPR) paradox that the non-local correlation between entangled particles implied the existence of “hidden variables” that determined measurement outcomes in advance. For decades, this debate remained a philosophical dispute with no clear experimental resolution, until 1964, when physicist John Bell proposed a testable mathematical inequality: if hidden variables existed, the correlation between measurements of entangled particles would fall below a fixed threshold; if quantum mechanics was correct, the correlation would exceed that threshold. The 1982 experiment by Alain Aspect and colleagues at the University of Paris-Sud finally confirmed that quantum entanglement violates Bell’s inequality, proving that Einstein’s “spooky action” is a real, measurable physical phenomenon, not a flaw in quantum theory. This experimental validation removed the last major conceptual barrier to the practical development of quantum computing: if entanglement is a real, controllable physical resource, it can be harnessed for computational tasks.

While the theoretical framework of quantum computing was formalized in the 1980s, the field remained a niche academic curiosity until the early 1990s, when two landmark algorithms demonstrated that quantum computers could solve classically intractable problems with exponential or polynomial speedups. The first breakthrough came in 1994, when mathematician Peter Shor of Bell Labs proposed Shor’s algorithm, a quantum algorithm for factoring large composite integers into their prime factors. Factoring is the core mathematical problem underlying the security of almost all modern public-key cryptography systems, including RSA and ECC (Elliptic Curve Cryptography), which protect everything from online banking transactions to national security communications. Classical algorithms for factoring large integers scale exponentially with the size of the input: the most efficient classical factoring algorithm, the general number field sieve, requires approximately $O(e^{n^{1/3}})$ operations to factor an n-bit integer. For a 2048-bit RSA key (the current standard for secure communications), this translates to roughly $10^{23}$ elementary operations; even using the world’s fastest classical supercomputer, Frontier, which can perform $1.1 \times 10^{18}$ operations per second, factoring a 2048-bit RSA key would take approximately 300 billion years, longer than the current age of the universe. Shor’s algorithm, by contrast, runs in polynomial time: it requires only $O(n^3)$ operations to factor an n-bit integer, meaning a 2048-bit RSA key could be factored in approximately 8 hours using a fault-tolerant quantum computer with roughly 1,000 logical qubits<sup>[1