Quantum Computing
What a quantum computer actually is — qubits, superposition, entanglement, and interference — and which problems it will and will not revolutionize.
A quantum computer processes information in quantum systems — superconducting circuits, trapped ions, photons — whose states can be superposed and entangled. It is not a fast classical computer; it is a different machine with a different repertoire of operations, spectacularly better on a few problems and no better (sometimes worse) on most.
The mechanism
A classical bit is 0 or 1; a qubit can exist in a superposition of both, described by complex amplitudes whose squared magnitudes give measurement probabilities. An n-qubit register occupies a state space of 2^n complex amplitudes, and a quantum gate operates on all amplitudes at once. Entanglement lets qubits share correlations with no classical counterpart. The art of quantum algorithms is choreographing interference so that wrong answers cancel and right ones reinforce — the wave mechanics underneath is the same as wave-particle duality.
What is actually proven
Three results define the field. Shor's algorithm (1994): factoring integers in polynomial time, which breaks RSA and much of current public-key cryptography if large fault-tolerant machines are ever built — the reason "post-quantum cryptography" standards now exist. Grover's algorithm (1996): quadratic speedup for unstructured search. Quantum simulation: Feynman's original motivation — simulating molecules and materials is exponentially costly classically and natural on quantum hardware, and is arguably the nearest-term real application in chemistry and materials.
Where it stands
Present devices are noisy intermediate-scale machines with tens to hundreds of physical qubits; error rates mean thousands of physical qubits per useful logical qubit, so useful fault-tolerant machines remain future work. Claims that quantum computers will "replace" classical computers misunderstand the field: only problems with exploitable quantum structure (factoring, unstructured search, quantum chemistry, certain optimization) benefit. Related reading: public key cryptography for what is at stake, and large language models for the classical computation that still dominates AI.
Tags
algorithms computation physics quantum computing