Quantum Computing

← Encyclopedia

Classical computation works by processing bits — physical switches held in one of two states, zero or one — through sequences of logic gates. The assumption underlying every classical machine is that the state of a bit is always definite, always one thing or the other. Quantum mechanics refuses that assumption at the level of physics. A two-level quantum system — an atom’s energy levels, the spin of an electron, the polarization of a photon — need not be in either state. It can be in both at once, in a superposition whose coefficients carry the full weight of the computation until measurement forces a result. Quantum computing is the project of turning that refusal into an engineering advantage.

Origins: the simulation argument and the universal machine

The theoretical foundations were laid in a cluster of papers from 1980 through 1985. Paul Benioff, at Argonne National Laboratory, published in 1980 the first quantum-mechanical model of a Turing machine — a proof that computation could, in principle, be described by quantum theory without thermodynamic cost. The decisive intuition came from Richard Feynman, at a 1981 conference at MIT and then in print the following year. Feynman’s argument was asymmetric: simulating a quantum system on a classical computer requires an exponentially growing overhead, because the classical machine must track the full space of superposed configurations. The natural solution is a computer that is itself quantum — one whose states grow in the same way the physics does. The paper, published in the International Journal of Theoretical Physics in 1982, produced, as the Stanford Encyclopedia records, “an abstract model…show[ing] how a quantum system could be used to do computations.” The agenda this set — use quantum hardware to simulate quantum nature — is still one of the field’s clearest near-term promises, in chemistry and materials science alike.

David Deutsch at Oxford supplied the formal architecture in 1985. His paper in the Proceedings of the Royal Society introduced the first universal quantum Turing machine and, building from it, the quantum circuit model that the field still uses. The paper’s motivation was explicit and unusual: Deutsch drew on Hugh Everett’s many-worlds interpretation of quantum mechanics, arguing that the only consistent account of what a quantum computer does is that it performs its computation across many branches of the universal wave function simultaneously. That interpretive commitment is not required to use or build quantum computers, but it shaped the conceptual framing of quantum parallelism — the intuition that a quantum computation somehow explores an exponential space of possibilities at once. The many-worlds entry carries the interpretation in full; what matters here is that the Deutsch connection is foundational, not incidental, and that the field’s original theorist was explicit about it.

The qubit: superposition, the Bloch sphere, entanglement as resource

The qubit is the quantum analogue of the classical bit. Where a bit is zero or one, a qubit’s physical state is the superposition

|ψ⟩ = α|0⟩ + β|1⟩

where α and β are complex numbers whose squared moduli give the probabilities of the two measurement outcomes: |α|² for zero, |β|² for one, with |α|² + |β|² = 1. Before measurement, neither outcome is definite. The full state of a single qubit is a point on the Bloch sphere — a unit sphere in three dimensions whose north and south poles are |0⟩ and |1⟩, and whose surface encodes every possible superposition. Gates are rotations of that sphere; a sequence of gates is a sequence of rotations; the computation runs in the continuous geometry of the sphere before the measurement collapses it to a pole.

The power scales dramatically with the number of qubits. Two qubits span a superposition of four states; three span eight; n qubits span 2ⁿ states simultaneously. The computational space doubles with each added qubit, a growth no classical register can match: a classical n-bit register holds exactly one of its 2ⁿ states at a time. The catch, and it is central, is that measurement retrieves only one outcome, drawn probabilistically. Raw parallelism is not free access to exponentially many answers — the art of quantum algorithm design is engineering the interference between amplitudes so that the correct answer accumulates probability and wrong answers cancel.

Entanglement enters as a resource rather than merely a curiosity. When two qubits are entangled, their joint state cannot be written as a product of two independent single-qubit states; the pair is a single quantum object. Gate operations on entangled qubits can create correlations that have no classical analogue and that quantum algorithms exploit for speedup. The quantum entanglement entry traces the physical story and the Bell-inequality experiments that certified entanglement as a real feature of nature; for computing purposes, the key point is that entanglement lets operations on a small number of qubits encode and manipulate information distributed across the whole register in ways no classical circuit can replicate.

The algorithms that made the field

The theoretical promise of quantum computing remained modest through the early 1990s — Deutsch’s algorithm and the Deutsch-Josza extension gave provable speedups over classical methods, but for artificial oracle problems without obvious applications. The field changed in 1994 when Peter Shor, then at AT&T Research, announced a quantum algorithm for integer factoring that runs in polynomial time.

The significance is cryptographic. RSA encryption, which secures most internet traffic, relies on the computational hardness of factoring the product of two large primes: the best classical algorithms require sub-exponential but practically intractable time. Shor’s algorithm uses the quantum Fourier transform to find the period of a modular exponential function, reducing factoring to period-finding and period-finding to a quantum operation that takes polynomial steps. As the Stanford Encyclopedia states, “the implementation of Shor’s algorithm on a large scale quantum computer would render ineffective currently widely used cryptosystems that rely on the premise that no efficient algorithm for factoring exists.” The same algorithm breaks the discrete logarithm problem, undermining Diffie-Hellman and elliptic-curve cryptography. A quantum computer large enough to run Shor’s algorithm at scale would obsolete the public-key infrastructure of the internet. It does not yet exist; the cryptographic community has been migrating toward post-quantum standards for a decade regardless.

Lov Grover’s 1996 algorithm addressed a different class of problem: searching an unstructured database of n items for a marked one. Classically this requires on average n/2 queries. Grover’s algorithm uses quantum amplitude amplification to find the answer in order √n queries — a quadratic speedup that, while less dramatic than Shor’s exponential gain, applies to an enormous range of search and optimization tasks. Grover’s algorithm is provably optimal among quantum search strategies and has become one of the field’s canonical illustrations of quantum advantage.

Decoherence: the central obstacle

Quantum states are fragile. The superposition that gives a qubit its computational richness is destroyed by any unwanted coupling to the environment — a stray photon, a fluctuating magnetic field, a vibration in the substrate. When a qubit entangles with environmental degrees of freedom it did not intend to interact with, the interference between its components is suppressed and the state effectively collapses to a mixture. This process is decoherence, and it is not merely an engineering inconvenience: it is the fundamental reason large-scale quantum computation is difficult. The quantum-measurement-problem entry carries decoherence’s full physical story; what matters here is its engineering consequence. Decoherence times in current hardware range from microseconds in superconducting qubits to minutes in isolated ion traps, but every operation takes time, and a useful computation requires many operations. Keeping a large register coherent long enough to complete Shor’s algorithm at cryptographically relevant key sizes remains beyond current capability.

The theoretical answer to decoherence is quantum error correction. Classical error correction works by redundancy: encode one bit in three, compare, and correct the minority. The same strategy fails for qubits because measuring to check for errors destroys the superposition. Quantum error correction works differently, using entanglement to encode logical qubits in the correlations among many physical qubits, and syndrome measurements that detect errors without revealing the logical state. The threshold theorem — one of the major results of the late 1990s — establishes that if the physical error rate per gate is below a certain threshold (roughly one part in a thousand for the best current codes), then adding more physical qubits per logical qubit exponentially suppresses the logical error rate. Below the threshold, arbitrarily long computations are in principle achievable. Above it, errors accumulate faster than correction can keep pace. Current hardware sits at or near the threshold, which is why the phrase “fault-tolerant quantum computing” describes a goal not yet reached at scale.

Hardware eras

The history of quantum computing hardware is a sequence of platforms with different decoherence timescales and gate-fidelity profiles. Ion traps, pioneered by Cirac and Zoller in 1995, confine individual ions in electromagnetic fields and achieve among the highest gate fidelities of any platform, but scaling to hundreds of qubits poses engineering challenges in the laser and ion-control infrastructure. Superconducting qubits, pursued by IBM, Google, and others from the 2000s onward, use circuits of superconducting metal cooled to millikelvin temperatures; their decoherence times are shorter but their fabrication is closer to chip-manufacturing methods and they scale in qubit count more readily. Photonic approaches use photon polarization or path as the qubit, with room-temperature operation as the attraction, at the cost of probabilistic two-qubit gates. Neutral atoms, topological qubits, and spin qubits in silicon extend the range further. No single platform has yet established decisive dominance.

The NISQ era and the supremacy dispute

John Preskill coined the term “Noisy Intermediate-Scale Quantum” — NISQ — in a 2017 keynote and a 2018 paper in the journal Quantum. NISQ names devices with 50–100 qubits, noisy gates, and no full error correction. Preskill’s abstract is direct: “Quantum computers with 50-100 qubits may be able to perform tasks which surpass the capabilities of today’s classical digital computers, but noise in quantum gates will limit the size of quantum circuits that can be executed reliably… the 100-qubit quantum computer will not change the world right away — we should regard it as a significant step toward the more powerful quantum technologies of the future.”

The first hardware claim to exceed classical capabilities came in 2019, when Google announced that its 53-qubit Sycamore processor had completed a specific task — random circuit sampling — in 200 seconds, a computation the company estimated would require approximately 10,000 years on the Summit supercomputer. The result was published in Nature and widely reported as achieving “quantum supremacy.” IBM responded within days, arguing that a classical simulation using different storage and algorithm choices could complete the same task in roughly 2.5 days rather than 10,000 years — a rebuttal that shrank the claimed advantage without eliminating it. Subsequent work in 2022 showed that improved classical simulation algorithms could match or beat the Sycamore result, prompting a broad reassessment of what “supremacy” means in this context. The honest rendering is that Sycamore demonstrated a genuine, if narrow, advantage on a task designed to be hard for classical machines, and that the margin of that advantage has been progressively contested by improvements in classical simulation. The field now tends to use the more careful phrase “quantum advantage” rather than “supremacy,” reserving the stronger term for tasks where no classical simulation can plausibly close the gap.

Later Sycamore demonstrations — topological order, time crystals, wormhole simulations — reflect the platform’s use as a physics probe rather than a general computation device, consistent with Feynman’s original framing.

Post-quantum cryptography: the practical consequence

Whatever the current state of hardware, Shor’s algorithm has already reshaped global cryptographic policy. The United States National Institute of Standards and Technology finalized its first post-quantum cryptographic standards in 2024, selecting lattice-based and other quantum-resistant algorithms as replacements for RSA and elliptic-curve systems. The migration is not waiting for a cryptographically capable quantum computer to appear: the risk of “harvest now, decrypt later” — adversaries storing encrypted traffic today to decrypt once a sufficient machine exists — makes the timeline urgent irrespective of when the hardware arrives. Post-quantum cryptography is therefore the first concrete consequence of quantum computing on everyday life, a migration driven by an algorithm that has not yet run at the scale it requires to threaten anything in practice.

Site-relevant threads

Computational universe and it-from-bit

John Archibald Wheeler, Deutsch’s intellectual predecessor and Everett’s doctoral supervisor, introduced the phrase “it from bit” in a 1990 essay, proposing that every particle, every field, even spacetime itself derives its existence from binary yes-or-no measurement answers. Wheeler’s participatory-universe framework — that physical reality is constituted by the questions measurement poses — influenced the generation of physicists who founded quantum information science. The it-from-bit lineage runs from Wheeler through Feynman’s simulation argument and Deutsch’s circuit model to contemporary claims that the universe is, at some level, a quantum computer. These claims carry different weights: the simulation argument is precise and physical; Wheeler’s ontological inversion is philosophical; the computational-universe program of Seth Lloyd and others sits between, as a productive but contested research program. The quantum-physics entry carries the broader ontological framing.

Consciousness and quantum computation: Orch OR

The claim that quantum computation underlies consciousness has a serious, if contested, home in Penrose and Hameroff’s Orchestrated Objective Reduction (Orch OR), developed in the 1990s: quantum superposition in microtubule proteins, with wave-function collapse driven by quantum gravity, is the basis of conscious experience. Max Tegmark’s 2000 calculation argued that thermal decoherence in the warm, wet brain would destroy any microtubule superposition in femtoseconds — far faster than neural processes. A 2022 Italian experiment failed to detect the spontaneous radiation objective-reduction collapse would emit. A 2014 revision addressed some criticisms; the theory sits far outside mainstream neuroscience. The quantum-measurement-problem entry notes the gravitationally induced objective-reduction model was constrained by a 2021 experiment. What the reception history of Orch OR demonstrates is that quantum computation as an explanation for consciousness is compelling enough to attract serious researchers and that the physical evidence has not supported it.

Quantum computing in tech-mysticism

Quantum computing has attracted a distinct genre of popular discourse that treats its strangeness as license for broader metaphysical claims: that quantum processors can access parallel universes, that entanglement enables telepathy, that consciousness is fundamentally quantum and therefore computation will eventually replicate or contact it. These claims build on genuine physics — superposition, entanglement, and quantum parallelism are real — and on a conflation the physics does not support. A quantum computer uses superposition and entanglement as engineering resources, in a precisely controlled physical system, to compute specific functions faster than classical circuits; it does not open channels to other branches of the wave function, and the no-communication theorem applies as strictly to quantum processors as to any other entangled system (see quantum-entanglement). The technical literature does not support the mystical applications; the vocabulary they borrow is real and the inferences are not.

Sources and scholarship

Richard P. Feynman, “Simulating Physics with Computers,” International Journal of Theoretical Physics 21 (1982), 467–488. Publisher page: https://link.springer.com/article/10.1007/BF02650179 The founding argument for quantum simulation. Behind a paywall; the argument is widely surveyed in open secondary literature.

David Deutsch, “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer,” Proceedings of the Royal Society A 400 (1985), 97–117. Publisher page: https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070 Introduced the universal quantum Turing machine and the circuit model; the many-worlds motivation is explicit in the paper. Behind a paywall.

Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” arXiv:quant-ph/9508027 (1995); published SIAM J. Comput. 26 (1997). Open access: https://arxiv.org/abs/quant-ph/9508027 The factoring algorithm whose cryptographic implications drove a decade of policy response before hardware could run it.

John Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum 2, 79 (2018). Open access: https://quantum-journal.org/papers/q-2018-08-06-79/ Coined the NISQ acronym and set the research agenda for the current hardware generation.

Stanford Encyclopedia of Philosophy — “Quantum Computing” https://plato.stanford.edu/entries/qt-quantcomp/ The most authoritative open reference for both the physics and the philosophical foundations of computational speedup.

Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000). The standard graduate textbook; covers qubits, gates, algorithms, error correction, and decoherence in full technical detail.

→ Related: Quantum Physics · Quantum Entanglement · Quantum Measurement Problem · Many Worlds Interpretation · Teleportation · Quantum Biology