Quantum Computing

Abstract

In May 1981, Richard Feynman asked an uncomfortable question: can a classical computer fully simulate nature? His answer was no, and that conclusion implicitly contained a research program for the following decades. What Feynman proposed was a computer that itself works quantum mechanically. Thirty years later, Google and IBM built such machines. They work, and at the same time they remain far from fulfilling what their most enthusiastic advocates promised.

IBM Quantum System One. Image: OJB Quantum, CC BY 4.0, via Wikimedia Commons.

Feynman’s Provocation

On May 7, 1981, Richard Feynman gave a talk at the MIT conference Physics of Computation that counts as the founding document of quantum computing: “Simulating Physics with Computers”, published in 1982 in the International Journal of Theoretical Physics.

Feynman’s argument was precise: a classical computer that wants to simulate a quantum system with N particles must describe a state space that grows exponentially with N. Ten entangled quantum particles have $2^{10}$ = 1,024 possible states; a hundred particles have $2^{100}$, a number for which no classical computer would have enough memory even if every state were encoded with a single bit. Every atom in the universe would not suffice.

The conclusion was provocative: “Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical.” A simulator that is supposed to describe quantum physics correctly must itself be quantum mechanical.

Feynman did not design a complete machine; he posed a research question. David Deutsch at the University of Oxford formalized the first complete model of a universal quantum computer in 1985: a quantum extension of the Turing machine, proving that such a device can in theory perform any physically realizable computation.

The Qubit: Superposition, Entanglement, Interference

The classical computer works with bits; each bit is either 0 or 1. The qubit follows different rules.

Superposition: a qubit can be in a state that represents both 0 and 1 at the same time, a linear combination of both. Only upon measurement does it collapse to a definite value. A register of N qubits simultaneously represents $2^N$ states: 10 qubits represent 1,024 states in parallel, 300 qubits represent more states than there are atoms in the observable universe.

Entanglement: two or more qubits can be correlated such that the state of one qubit cannot be described independently of the other, even across arbitrary distances. Einstein called this “spooky action at a distance” and considered it a flaw in the theory. It is not.

Interference: quantum computers manipulate probability amplitudes so that paths to correct answers interfere constructively (are amplified) and paths to wrong answers interfere destructively (are canceled). This mechanism is the true heart of quantum algorithms.

Together, these three properties permit computations that cannot be reproduced efficiently classically, but only for certain problems, and only with precisely constructed algorithms.

Shor’s Algorithm: RSA in the Crosshairs

In 1994, Peter Shor of AT&T Bell Labs presented an algorithm at the Foundations of Computer Science conference that alarmed the cryptography community: a quantum procedure for integer factorization in polynomial time.

The significance was immediately clear. RSA encryption (the standard for secure communication on the internet, for HTTPS, for encrypted email) rests on the assumption that factoring large numbers is classically intractable. Factoring $15 = 3 \times 5$ is trivial; factoring a 2048-bit number would take longer on the fastest classical supercomputer than the age of the universe.

Shor’s algorithm does this on an ideal quantum computer in a number of steps that grows polynomially with the bit length, an exponential speedup over the best known classical method.

The catch: ideal quantum computer. Shor showed what is possible, not what could be built in 1994. A quantum computer that could actually break RSA-2048 would, by current estimates, require several million physical qubits with extremely low error rates. Today’s largest machines have a few thousand qubits, with error rates still far from that.

A second fundamental algorithm came in 1996 from Lov Grover (also Bell Labs): a quadratic speedup for unstructured search. Classically, searching through N elements takes N/2 steps on average; Grover does it in $\sqrt{N}$ steps. Less dramatic than Shor, but provable and universal.

Decoherence: The Fundamental Barrier

Warning

The decoherence problem: A qubit in superposition is extraordinarily fragile. Any uncontrolled interaction with the environment (a photon, a temperature fluctuation, a vibration) dissolves the superposition and destroys the stored quantum information. This process is called decoherence, and it happens within microseconds to milliseconds, even under laboratory conditions. Superconducting quantum processors (IBM, Google) must be operated at about 15 millikelvin, colder than the cosmic background (~3 K), colder than the deepest point of space. This operation requires enormous cooling systems and makes scaling extremely costly. All “quantum supremacy” claims must be judged against the fact that today’s qubits are error-prone: physical two-qubit gate operations have typical error rates of 0.1–1%. Shor’s algorithm requires error rates of billionths of a percent; that demands error correction, which in turn needs many physical qubits per logical qubit.

The key concept is quantum error correction (QEC): analogous to classical error correction in hard drives and network transmission, quantum information can be encoded redundantly to detect and correct errors. The difference: quantum mechanics forbids simply copying a qubit state (the no-cloning theorem). Error correction must be constructed cleverly, without measuring the state.

A logical qubit (a fault-tolerant qubit with low effective error rates) requires between ten and a thousand physical qubits, depending on the error correction code. IBM’s qLDPC code, published in Nature in 2024, encodes 12 logical qubits in 288 physical qubits, an advance that reduces the overhead by about 90% compared with earlier approaches. IBM plans to deliver a machine with 200 logical qubits and 100 million error-corrected gate operations by 2029, the Quantum Starling system.

The Sycamore Moment and Its Limits

On October 23, 2019, Google published an article in Nature titled “Quantum supremacy using a programmable superconducting processor”. The Sycamore processor with 53 qubits had completed a specific computation (sampling the outputs of a random quantum circuit) in 200 seconds. Google estimated that Summit, then the fastest supercomputer in the world, would need 10,000 years for it.

IBM’s response came the same day. IBM researchers had analyzed the computation classically and argued: with clever use of disk storage and optimized algorithms, the same task could be solved on Summit in about 2.5 days. The term quantum supremacy, coined by physicist John Preskill in 2012 for the moment when quantum computers do something that is outright impossible classically, was not satisfied.

Later developments proved IBM right: by 2022, researchers had developed classical algorithms that solved Google’s benchmark task in under 200 seconds. The benchmark problem was not general; it was constructed to look hard for classical algorithms, a property that turned out to be temporary.

Post-Quantum Cryptography as Countermeasure

The mere theoretical existence of Shor’s algorithm triggered real consequences long before any quantum computer came close to threatening RSA. The concept of “harvest now, decrypt later” (HNDL): state actors could collect encrypted communication today and wait until a sufficiently large quantum computer exists to decrypt it, especially relevant for secrets with long sensitivity (state secrets, medical data, corporate IP).

As a countermeasure, the US NIST standardized the first post-quantum cryptography algorithms in 2024: CRYSTALS-Kyber (key exchange) and CRYSTALS-Dilithium (digital signatures), both based on lattice problems (lattice-based cryptography) that, as far as current knowledge goes, resist quantum computers too, plus the hash-based signature scheme SPHINCS+.

Dead End: Quantum Hype vs. NISQ Reality

The physicist John Preskill (the same one who coined quantum supremacy) introduced a more sober term in 2018: NISQ (Noisy Intermediate-Scale Quantum). NISQ devices are the machines we have today: 50–1000 noisy qubits, without sufficient error correction for fault-tolerant computation, too small for Shor’s algorithm on practically relevant numbers.

The hype cycle of the 2010s projected onto quantum computing the same expectations AI researchers once projected onto symbolic systems and neural networks: transformative disruption, imminent superiority over classical systems across broad applications. The reality is more complicated:

No quantum computer has yet solved a practical problem faster than the best classical algorithm
The benchmark tasks on which quantum supremacy was demonstrated have no economic relevance
Quantum error correction requires overhead factors that drastically reduce effective processor power
The cooling infrastructure limits how many qubits can physically coexist in one system

That does not mean quantum computing will fail. Feynman’s original motivation (simulating quantum systems, particularly for chemistry, materials science, and pharmacology) remains promising: here classical computers are fundamentally limited, and even a NISQ device with a few hundred logical qubits could enable breakthroughs in catalysis, battery technology, or drug development.

The dead end is not quantum computing itself, but the expectation that it would become the general alternative to classical computing. Quantum computers will not replace laptops, run databases, or serve web pages. They will (if error correction delivers the promised progress) be used for specific, quantum-natively hard problems. That is less romantic than the promises of the hype cycle. It is still scientifically extraordinary work.