**This is an old revision of the document!**
Table of Contents
Quantum computing
Quantum computing is a model of computation that uses quantum-mechanical systems to store and process information. The fundamental unit is the Qubit, the quantum analog of a classical bit. A classical bit is either 0 or 1 at any given moment. A qubit can be in a superposition of both — and multiple qubits can be entangled, meaning their states are correlated in ways that have no classical analog. Those two properties, superposition and entanglement, are the source of quantum computing's potential.
What does “potential” actually mean here? For most problems, nothing special — a classical CPU will beat a quantum computer comfortably, and it is a lot cheaper to run. Quantum speedups are real but narrow: searching unstructured data (Grover's algorithm, $O(\sqrt{N})$ vs $O(N)$), factoring large integers (Shor's algorithm, polynomial vs sub-exponential), and simulating other quantum systems. Outside those niches, quantum computing does not help much.
The field is also much younger and messier than the hype suggests. Today's hardware is noisy, error-prone, and limited to hundreds or a few thousand qubits. Running any of the famous algorithms at a useful scale requires fault tolerance, which in turn requires encoding each logical qubit into hundreds of physical ones. That gap between what quantum computers can do in theory and what they can do right now is the central engineering problem of the field.