How to Think in Qubits
How to Think in Qubits
A first-principles tutorial in quantum information for cryptographers and mathematicians — from the state space of a single qubit to universal gate sets, circuit construction, interference, and what a quantum attack actually costs.
This is a self-contained introduction to quantum information for readers who are comfortable with linear algebra and probability but have never worked with a qubit. We build the subject from one substitution — replace the 1-norm over the non-negative reals with the 2-norm over the complex numbers — and derive everything else from it: the Born rule, unitarity, reversibility, no-cloning, entanglement, and interference. We then construct quantum circuits explicitly, catalogue the standard gates with their matrices, prove universality of small gate sets, and explain why entanglement alone is not the source of quantum advantage. We close with what all of this actually implies for cryptography, including honest resource estimates for attacks on RSA and AES.
1. The Right Mental Model
Almost every serious misunderstanding of quantum computing comes from the same mistake: reaching for a physical picture before reaching for the linear algebra. A qubit is not a coin that has not yet landed. It is not a bit that is secretly both values at once. It is a unit vector in a two-dimensional complex vector space — and every correct intuition you will ever have about quantum information is, in the end, a statement about that vector space.
So we will not start with photons, spins, or cats. We will start with something you already know — a probabilistic computer — and change exactly one thing.
Three Computers, One Difference
Consider a machine with $N$ possible configurations, labelled $0, 1, \dots, N-1$. There are three ways to describe its state.
- Deterministic. The state is a single label $x$. Equivalently, the standard basis vector $e_x \in \mathbb{R}^N$. Evolution is a function on labels; if we insist on reversibility, a permutation matrix.
- Probabilistic. The state is a vector $p \in \mathbb{R}^N$ with $p_i \geq 0$ and $\sum_i p_i = 1$. That is: the entries are non-negative and the 1-norm is 1. Evolution is a stochastic matrix — one that maps probability vectors to probability vectors.
- Quantum. The state is a vector $\psi \in \mathbb{C}^N$ with $\sum_i |\psi_i|^2 = 1$. That is: the entries are arbitrary complex numbers and the 2-norm is 1. Evolution is a unitary matrix — one that maps unit vectors to unit vectors.
That is the whole leap. Swap the 1-norm over $\mathbb{R}_{\geq 0}$ for the 2-norm over $\mathbb{C}$. Everything that follows — interference, entanglement, the impossibility of copying, the Born rule, the entire architecture of quantum algorithms — is downstream of that one substitution.
The norm you preserve determines the matrices you are allowed to use, and the matrices you are allowed to use determine what your computer can do.
Preserve the 1-norm on non-negative vectors and you get stochastic matrices. Their entries lie in $[0,1]$. There is no way for two non-negative numbers to cancel. Probability mass can be shuffled and spread, but never destroyed by adding more of it.
Preserve the 2-norm over $\mathbb{C}$ and you get unitary matrices. Their entries may be negative, or complex. Two computational paths that arrive at the same outcome may now arrive carrying amplitudes $+\tfrac{1}{2}$ and $-\tfrac{1}{2}$ — and annihilate.
Probabilities can only accumulate. Amplitudes can cancel. That single asymmetry is the entire resource that quantum computation exploits.
The Comparison That Should Live in Your Head
| Deterministic | Probabilistic | Quantum | |
|---|---|---|---|
| State | Label $x$, i.e. basis vector $e_x$ | Probability vector $p \in \mathbb{R}^N$ | Amplitude vector $\psi \in \mathbb{C}^N$ |
| Constraint | — | $p_i \geq 0$, $\textstyle\sum_i p_i = 1$ | $\textstyle\sum_i |\psi_i|^2 = 1$ |
| Norm preserved | — | $\ell^1$ | $\ell^2$ |
| Evolution | Permutation matrix | Stochastic matrix | Unitary matrix |
| Reversible? | If we require it | Generally no | Always — until you measure |
| Cancellation | None | None — entries are $\geq 0$ | Yes — this is the resource |
| Composing systems | Cartesian product | Tensor product of $p$-vectors | Tensor product of Hilbert spaces |
| Reading the state | Free, complete | Free, complete | Destructive, partial (Born rule) |
The Fallacy You Must Kill Immediately
You will read, in a hundred popular articles, that a quantum computer "tries all $2^n$ possibilities in parallel." This is the single most damaging sentence in the field, and you should scrub it from your vocabulary before reading further.
Here is why it is wrong. Yes, an $n$-qubit register carries $2^n$ complex amplitudes. But you never get to read those $2^n$ numbers. When you measure, you receive exactly one $n$-bit string, sampled according to the Born rule. If "parallelism" were the mechanism, a quantum computer would solve NP-complete problems instantly by checking every certificate at once — and it is not believed to do so [BBBV1997].
The correct sentence is this: a quantum computer manipulates one vector of $2^n$ amplitudes, and hands you a single sample from it. The entire art of quantum algorithm design is arranging for the amplitudes on the wrong answers to cancel, so that the one sample you are allowed is overwhelmingly likely to be the right one.
Superposition is not the resource. Interference is. Superposition merely makes interference possible — and a computation that never interferes is a computation you could have run classically, at the same cost, with a coin.
— The organising principle of this tutorial2. What a Qubit Actually Is
Set $N = 2$. A single qubit is a unit vector in $\mathbb{C}^2$.
The two vectors $|0\rangle$ and $|1\rangle$ form the computational basis. Concretely:
That is the definition. There is nothing else. A qubit is a point on the unit sphere of $\mathbb{C}^2$, and the rest of this tutorial is bookkeeping.
Dirac Notation Is Just Linear Algebra with Better Bookkeeping
The angle brackets intimidate newcomers unnecessarily. They are a compact notation for objects you already know.
| Dirac | Name | What it is |
|---|---|---|
| $|\psi\rangle$ | ket | A column vector in $\mathbb{C}^2$ (or $\mathbb{C}^{2^n}$). |
| $\langle\psi|$ | bra | Its conjugate transpose — a row vector, i.e. $|\psi\rangle^{\dagger}$. |
| $\langle\phi|\psi\rangle$ | braket | The Hermitian inner product $\phi^{\dagger}\psi \in \mathbb{C}$. A number. |
| $|\psi\rangle\langle\phi|$ | ketbra | The outer product $\psi\phi^{\dagger}$ — a matrix. A rank-1 operator. |
| $\langle\phi|A|\psi\rangle$ | matrix element | $\phi^{\dagger} A \psi$. A number. |
| $|\psi\rangle \otimes |\phi\rangle$ | tensor / Kronecker | Also written $|\psi\rangle|\phi\rangle$ or $|\psi\phi\rangle$. |
The one habit worth acquiring immediately: $\langle 0|\psi\rangle = \alpha$. The bra $\langle 0|$ extracts the coefficient of $|0\rangle$. This is why the Born rule is written the way it is.
The Born Rule
Measuring $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ in the computational basis returns the outcome $0$ with probability $|\alpha|^2$ and $1$ with probability $|\beta|^2$.
The normalisation condition $|\alpha|^2 + |\beta|^2 = 1$ is now exactly the statement that probabilities sum to one. It is not an extra postulate bolted on; it is the reason the state space is the unit sphere and not all of $\mathbb{C}^2$.
Global Phase Is Nothing. Relative Phase Is Everything.
This is the distinction beginners fumble most often, and the one that most reliably separates people who understand qubits from people who are reciting them.
Multiply the whole state by a unit complex number: $|\psi'\rangle = e^{i\gamma}|\psi\rangle$. Then for any measurement, and after any subsequent sequence of gates $U$, the outcome probabilities are unchanged, because $|e^{i\gamma}|^2 = 1$ and $U(e^{i\gamma}|\psi\rangle) = e^{i\gamma}(U|\psi\rangle)$. The factor rides along, unobservably, forever. A global phase has no physical meaning whatsoever.
Now consider instead the relative phase between the two components:
Measure either one in the computational basis and you get $0$ or $1$ with probability $\tfrac{1}{2}$ each. They are statistically indistinguishable — in that basis. But they are orthogonal states, $\langle +|-\rangle = 0$, and a single application of the Hadamard gate maps $|+\rangle \mapsto |0\rangle$ and $|-\rangle \mapsto |1\rangle$, distinguishing them with certainty. The minus sign is not a decoration. It is the whole difference between two perfectly distinguishable states.
If a phase multiplies the entire state vector, ignore it — you may freely add or drop it in any calculation. If a phase multiplies one component relative to another, it is physical, it is measurable, and it is very probably the thing your algorithm is about to exploit.
The Bloch Sphere — and When to Stop Using It
Since global phase is meaningless and the norm is fixed, the four real parameters in $(\alpha,\beta)$ collapse to two. Write:
The pair $(\theta,\varphi)$ are spherical polar coordinates. Every pure qubit state is a point on a sphere: $|0\rangle$ at the north pole, $|1\rangle$ at the south pole, $|\pm\rangle$ on the equator. For a mathematician there is an elegant way to say this: the state space of a qubit is the complex projective line $\mathbb{CP}^1$, and $\mathbb{CP}^1 \cong S^2$ is the Riemann sphere.
Note carefully that orthogonal states sit at antipodal points, not at right angles. $|0\rangle$ and $|1\rangle$ are orthogonal in $\mathbb{C}^2$ but $180°$ apart on the sphere. The Bloch angle is half the Hilbert-space angle. This trips up everyone once.
The Bloch sphere is a faithful picture of one qubit and a lethal trap for two. There is no "Bloch sphere for two qubits." A two-qubit pure state lives in $\mathbb{CP}^3$ — six real dimensions — and entanglement is precisely the phenomenon that cannot be drawn as two little arrows on two little spheres.
Rule: use the Bloch sphere to reason about single-qubit gates. The moment entanglement enters, drop it and return to vectors and matrices.
Superposition Is Basis-Relative
Here is a fact that reorganises many people's thinking, so read it slowly.
"Being in superposition" is not an intrinsic property of a state. It is a statement about a state relative to a chosen basis. The state $|+\rangle$ is a superposition of $|0\rangle$ and $|1\rangle$ — but it is a basis state of the $X$ basis $\{|+\rangle, |-\rangle\}$, where it is not a superposition of anything. And conversely $|0\rangle = \tfrac{1}{\sqrt2}(|+\rangle + |-\rangle)$ is a superposition in the $X$ basis.
Every state is a superposition in some basis and a basis state in another. So "the qubit is in a superposition" carries no information until you say with respect to what. (Contrast this with entanglement, in Section 4, which is basis-independent — and that is exactly why entanglement, not superposition, is the structurally meaningful notion.)
How Much Information Is in a Qubit?
A qubit is specified by two continuous complex parameters. It is tempting — and wrong — to conclude that a qubit stores infinitely many bits.
You cannot get them out. Holevo's theorem [Holevo1973] states that no measurement strategy whatsoever can extract more than $n$ classical bits of information from $n$ qubits. The continuum of $(\alpha,\beta)$ is real, but it is inaccessible: one measurement yields one bit, and the state is destroyed in the process.
For cryptographers this is the right calibration. Quantum states are not magic compression. The exponential lives in how the state evolves, never in how much you can read.
Bit versus Qubit
| Classical bit | Qubit | |
|---|---|---|
| State space | $\{0, 1\}$ — two points | Unit sphere of $\mathbb{C}^2$ — a continuum |
| Copyable? | Yes, trivially | No — no-cloning theorem (Section 5) |
| Readable? | Yes, non-destructively, exactly | One sample, then the state collapses |
| Information carried | 1 bit | At most 1 bit extractable (Holevo) |
| $n$ of them | $n$ bits describe the state | $2^n$ complex amplitudes describe the state |
3. Measurement: The Only Irreversible Thing
Every gate in a quantum circuit is reversible. Measurement is not. It is the one place where information leaves the quantum world, and it is where all of your probability comes from.
Measuring in Another Basis
The Born rule as stated in Eq. (3) measures in the computational ($Z$) basis. But you may measure in any orthonormal basis $\{|b_0\rangle, |b_1\rangle\}$; the probability of outcome $k$ is $|\langle b_k|\psi\rangle|^2$ and the state collapses to $|b_k\rangle$.
In practice hardware only measures in the computational basis, so we perform a change of basis first. To measure in the $X$ basis $\{|+\rangle,|-\rangle\}$: apply $H$ (which maps $|+\rangle \mapsto |0\rangle$ and $|-\rangle \mapsto |1\rangle$), then measure in $Z$. Reading outcome $0$ means "the state was $|+\rangle$."
Measuring in the basis $\{U^{\dagger}|0\rangle,\, U^{\dagger}|1\rangle\}$ is the same as applying $U$ and measuring in the computational basis. Every "exotic" measurement is a unitary followed by the only measurement you actually have.
The Experiment That Kills the Coin Analogy
Prepare $|0\rangle$. Apply $H$. Measure. You get $0$ or $1$ with probability $\tfrac12$ each. So far, this is a fair coin, and you might reasonably conclude that $H$ "randomises" the qubit.
Now do it again — but apply $H$ twice before measuring.
You get $0$. Always. With certainty. Every single run.
Flip a fair coin, then flip it again: still fair. Randomise a bit, then randomise it again: still random. Classical randomisation is a one-way street — you cannot un-randomise. But $H^2 = I$, and so the qubit after the first $H$ was never random at all. It was in the perfectly definite state $|+\rangle$, which the second $H$ maps deterministically back to $|0\rangle$.
Let us watch the cancellation happen. The two applications of $H$ create two computational paths from the input $|0\rangle$ to each output, and we sum the amplitudes along them:
Written out algebraically, with $H|0\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle)$ and $H|1\rangle = \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle)$:
The $|1\rangle$ terms carry coefficients $+\tfrac12$ and $-\tfrac12$ and vanish. That is a quantum computation. Everything else — Deutsch, Simon, Grover, Shor — is this trick, scaled up and made to do useful work.
Superposition Is Not Ignorance
The $H \cdot H$ experiment refutes a specific, tempting, and wrong belief: that after the first $H$ the qubit "is really" $0$ or $1$, and we merely do not know which. If that were true, no subsequent operation could restore $|0\rangle$ with certainty. The information was never lost, because it was never randomised — only rotated.
To make this airtight, it helps to introduce the density matrix, which is the correct tool for distinguishing "in superposition" from "in an unknown one of two states."
Both matrices have the same diagonal, so both give $50/50$ statistics when measured in the computational basis. They are not the same state. The difference lives entirely in the off-diagonal entries, which are called coherences. Apply $H$ to each: the left one becomes $|0\rangle\langle 0|$ and yields the outcome $0$ with certainty. The right one is $\tfrac12 I$, which is invariant under every unitary, and stays $50/50$ forever.
Decoherence — the central enemy of every quantum engineer alive — is precisely the process that drives those off-diagonal entries toward zero. It converts the left matrix in Eq. (7) into the right one.
When that happens, your qubit has not "become noisy" in some vague sense. It has become a classical random bit. Coherences are what interference consumes; destroy them and your quantum computer is an expensive random number generator.
Projective Measurement, Stated Properly
For completeness, the general rule. A projective measurement is a family of orthogonal projectors $\{P_m\}$ with $\sum_m P_m = I$. Outcome $m$ occurs with probability $\langle\psi|P_m|\psi\rangle$, and the post-measurement state is $P_m|\psi\rangle / \sqrt{\langle\psi|P_m|\psi\rangle}$.
For a single-qubit $Z$ measurement, $P_0 = |0\rangle\langle 0|$ and $P_1 = |1\rangle\langle 1|$, and this reduces to Eq. (3). The value of the general form is that it applies unchanged when you measure one qubit out of many — which is exactly what happens in every real circuit, and what produces entanglement's strangest behaviour.
4. Many Qubits, Tensor Products, and Entanglement
One qubit is a warm-up. The exponential arrives when you put qubits together.
The Tensor Product
If system $A$ has state space $\mathcal{H}_A = \mathbb{C}^2$ and system $B$ has $\mathcal{H}_B = \mathbb{C}^2$, the joint system has state space $\mathcal{H}_A \otimes \mathcal{H}_B = \mathbb{C}^4$. Note: tensor product, not Cartesian product. Dimensions multiply; they do not add.
Concretely, the Kronecker product does what you expect:
An $n$-qubit register therefore lives in $\mathbb{C}^{2^n}$ and is described by $2^n$ complex amplitudes:
Fifty qubits carry $2^{50} \approx 10^{15}$ amplitudes; three hundred carry more amplitudes than there are atoms in the observable universe. This is the number everyone quotes. Keep Holevo in mind while you quote it: you may still only read $n$ bits out.
In this article, and in most textbooks, $|q_0 q_1 \dots q_{n-1}\rangle$ lists qubit $0$ leftmost (most significant), so the basis state $|10\rangle$ means $q_0 = 1,\ q_1 = 0$, and it is index $2$ of the vector.
Qiskit reverses this. Qiskit is little-endian: it prints $|q_{n-1} \dots q_1 q_0\rangle$, so qubit $0$ is rightmost. Apply qc.x(0) to a two-qubit register in Qiskit and the state vector prints as $|01\rangle$, not $|10\rangle$.
Neither convention is wrong; mixing them silently is. Every single person who works with quantum circuits loses an afternoon to this exactly once. Consider this your afternoon.
Product States versus Entangled States
Some two-qubit states factor:
Such a state carries no correlation at all: measuring $A$ tells you nothing new about $B$. A state that cannot be written in this form is called entangled. The canonical example is the Bell state:
That this does not factor is a two-line exercise, and worth doing once by hand.
Suppose it were. Then for some $a,b,c,d \in \mathbb{C}$,
$\bigl(a|0\rangle + b|1\rangle\bigr) \otimes \bigl(c|0\rangle + d|1\rangle\bigr) = ac|00\rangle + ad|01\rangle + bc|10\rangle + bd|11\rangle = \tfrac{1}{\sqrt2}\bigl(|00\rangle + |11\rangle\bigr).$
Comparing coefficients: $ad = 0$ and $bc = 0$, while $ac = bd = \tfrac{1}{\sqrt2} \neq 0$. From $ad = 0$, either $a = 0$ or $d = 0$. If $a = 0$ then $ac = 0$, a contradiction. If $d = 0$ then $bd = 0$, a contradiction. Hence no such factorisation exists. $\blacksquare$
Notice what this proof is not: it is not about distance, particles, or physics. It is a statement about rank. A two-qubit state, written as a $2 \times 2$ coefficient matrix, is a product state precisely when that matrix has rank $1$. Entanglement is rank $\geq 2$. That is all it ever was.
The Four Bell States
They form an orthonormal basis of $\mathbb{C}^4$ — the Bell basis — and every one of them is maximally entangled.
The state $|\Psi^{-}\rangle$ is the singlet, the star of Bell-inequality experiments [Bell1964] and of the companion article in this series.
Why You Cannot Signal With Entanglement
Alice holds qubit $A$ of $|\Phi^{+}\rangle$; Bob holds $B$, a galaxy away. If Alice measures and gets $0$, Bob's qubit "instantly becomes" $|0\rangle$. Does that transmit information?
No — and the density matrix says exactly why. Alice's local description of her own qubit is the reduced state, obtained by tracing out Bob:
The maximally mixed state. A perfect coin. And crucially, $\rho_A$ does not depend on anything Bob does — not on whether he measures, nor on which basis he chooses. Every local statistic Alice can compute is a function of $\rho_A$ alone, so nothing Bob does can change what she sees. The correlations only become visible when the two of them compare notes over a classical channel, which travels at most at the speed of light.
Every product state is a joint state. Not every joint state is a product state — the ones that are not are entangled. Entanglement is a property of the joint state, not of either part; each part, taken alone, is simply mixed. Maximal entanglement means each part alone is maximally mixed, i.e. carries no information at all.
Recall from Section 2 that "being in superposition" is basis-relative — every state is a superposition in some basis. Entanglement is different: it is basis-independent. A state is either a product state or it is not, and no change of local basis can turn one into the other.
This is why entanglement earns a place in the theory and "superposition" does not, quite. And it is why, in Section 9, the honest question turns out not to be "does this circuit entangle?" but something considerably sharper.
5. Gates Are Unitary Matrices — and Why That Forces Everything
A quantum gate on $n$ qubits is a unitary matrix $U \in \mathbb{C}^{2^n \times 2^n}$, meaning $U^{\dagger}U = U U^{\dagger} = I$. It acts on the state by ordinary matrix–vector multiplication: $|\psi\rangle \mapsto U|\psi\rangle$.
This is not an arbitrary design choice. It is forced.
The Two-Line Derivation
Suppose $U$ is linear and $\|U\psi\| = \|\psi\|$ for every $\psi \in \mathbb{C}^N$ (it must be, or probabilities would stop summing to one). Then
$\langle \psi | (U^{\dagger}U - I) | \psi\rangle = \|U\psi\|^2 - \|\psi\|^2 = 0 \quad\text{for all } \psi.$
Over $\mathbb{C}$, an operator $M$ with $\langle\psi|M|\psi\rangle = 0$ for all $\psi$ is the zero operator (apply the polarisation identity). Hence $U^{\dagger}U = I$. $\blacksquare$
Linearity is a postulate of quantum mechanics. Norm preservation is forced by the Born rule. Unitarity is the consequence — and everything below is, in turn, a consequence of unitarity.
Consequence 1: Every Gate Is Reversible
If $U$ is unitary, $U^{-1} = U^{\dagger}$ exists and is itself unitary. So every quantum gate can be undone, exactly, by another quantum gate. There is no quantum gate that "forgets" its input.
This has a sharp consequence for anyone coming from classical computing: there is no quantum AND gate in the naive sense. Classical AND maps two bits to one; it is not injective; it destroys information. A quantum circuit simply cannot do that. The only irreversible step available to you is measurement — and measurement ends the coherent computation.
Consequence 2: Classical Functions Must Be Embedded Reversibly
Suppose you want a quantum circuit to evaluate some classical function $f : \{0,1\}^n \to \{0,1\}^m$ — AES, SHA-256, a modular exponentiation, whatever. You cannot simply "run the code." You must build a reversible embedding, standardly:
This is a permutation of the computational basis (apply it twice and you are back where you started, since $y \oplus f(x) \oplus f(x) = y$), hence unitary, hence legal. It is called the oracle for $f$, and it is how every quantum algorithm in the literature accesses a classical function.
Reversibility is not free. Classical circuits discard intermediate values constantly; quantum circuits cannot. Every scratch bit becomes an ancilla qubit that must be carried along, and — critically — must be uncomputed before it can be reused or discarded, because leftover ancillas remain entangled with your register and destroy the interference you were trying to arrange.
The upshot: a quantum circuit for AES is dramatically more expensive than an AES chip. When you read that "Grover halves the security of AES-128," the honest version is "Grover requires roughly $2^{64}$ sequential evaluations of a fully reversible, error-corrected AES circuit." Those are wildly different statements, and only the second one is a cost model.
Consequence 3: The No-Cloning Theorem
This is the result on which quantum cryptography is built, and it falls straight out of linearity.
Suppose a unitary $U$ existed with $U\bigl(|\psi\rangle \otimes |0\rangle\bigr) = |\psi\rangle \otimes |\psi\rangle$ for every state $|\psi\rangle$. Take any two states $|\psi\rangle, |\phi\rangle$. Unitaries preserve inner products, so comparing the inner product of the inputs with that of the outputs:
$\langle\psi|\phi\rangle \cdot \underbrace{\langle 0|0\rangle}_{=\,1} \;=\; \langle\psi|\phi\rangle\langle\psi|\phi\rangle \;=\; \langle\psi|\phi\rangle^2.$
So $z = z^2$ where $z = \langle\psi|\phi\rangle$, forcing $z \in \{0, 1\}$: the two states are either orthogonal or identical. A cloner can therefore work on a set of mutually orthogonal states — but no unitary clones an arbitrary unknown state. $\blacksquare$ [WZ1982, Dieks1982]
Notice how little was needed: linearity, unitarity, and an inner product. No physics.
In BB84 [BB84], Alice sends qubits encoded at random in either the $Z$ basis $\{|0\rangle,|1\rangle\}$ or the $X$ basis $\{|+\rangle,|-\rangle\}$. These four states are not mutually orthogonal — $|0\rangle$ and $|+\rangle$ overlap — so by the theorem above, no device can copy them all.
An eavesdropper cannot grab a copy and decide later. She must measure, and to measure she must guess a basis. Guess wrong and she irreversibly disturbs the state, injecting detectable errors into Alice and Bob's key. Security comes from a theorem of linear algebra, not from an assumption that some problem is hard. This is what "information-theoretic security" means, and it is why QKD is qualitatively different from RSA.
6. The Gate Zoo
You will meet perhaps a dozen gates in practice. Here they are, with their matrices. Learn the matrices; the names are just labels.
6.1 The Pauli Gates
$X$ is the quantum NOT: $X|0\rangle = |1\rangle$, $X|1\rangle = |0\rangle$. It is a bit flip.
$Z$ leaves $|0\rangle$ alone and sends $|1\rangle \mapsto -|1\rangle$. It is a phase flip. It does absolutely nothing observable to $|0\rangle$ or $|1\rangle$ — and yet it swaps $|+\rangle \leftrightarrow |-\rangle$, which are perfectly distinguishable. A gate that is invisible in one basis can be maximally violent in another. Internalise that.
$Y = iXZ$ does both at once. The three Paulis together with $I$ span all $2\times 2$ Hermitian matrices over $\mathbb{R}$, they each square to $I$, and they pairwise anticommute: $XY = -YX = iZ$, and cyclic permutations thereof.
6.2 Hadamard: The Basis Changer
$H|0\rangle = |+\rangle$, $H|1\rangle = |-\rangle$, and $H^2 = I$. It maps the $Z$ basis to the $X$ basis and back. Nearly every quantum algorithm opens with a layer of Hadamards — $H^{\otimes n}|0\rangle^{\otimes n}$ produces the uniform superposition over all $2^n$ strings — and closes with another layer, which is where the interference is cashed in.
Two identities you will use constantly:
In words: Hadamard exchanges bit flips and phase flips. This is the single most useful algebraic fact in elementary quantum computing, and it is a thirty-second matrix multiplication to verify.
6.3 Phase Gates: $S$, $T$, and $P(\varphi)$
These apply a relative phase to the $|1\rangle$ component and nothing else. Note $T^2 = S$ and $S^2 = Z$, so $T$ is the "eighth root of the identity" in a precise sense: $T^8 = I$.
The $T$ gate looks like the most boring object on this page. It is, in fact, the most expensive gate in the entire subject, and Section 9 explains why.
6.4 Rotations
For any Pauli $P \in \{X,Y,Z\}$ (each satisfying $P^2 = I$), the exponential series splits cleanly:
which gives the three familiar matrices:
These are literally rotations of the Bloch sphere about the $x$, $y$, and $z$ axes, by angle $\theta$. The factor of $\tfrac12$ in the exponent is the Bloch-angle-is-half-the-Hilbert-angle business again — a $2\pi$ rotation returns $-I$, not $I$, which is the famous spinor sign and is (being a global phase) physically invisible.
Every single-qubit unitary can be written $U = e^{i\alpha}\,R_z(\beta)\,R_y(\gamma)\,R_z(\delta)$ for real $\alpha,\beta,\gamma,\delta$. Three rotations and a phase — that is the whole of $U(2)$. So a hardware vendor who gives you $R_z$ and $R_y$ (or in practice $R_z$ and $\sqrt{X}$) has given you every single-qubit gate there is.
6.5 Two-Qubit Gates
The workhorse is the controlled-NOT. In the basis $(|00\rangle, |01\rangle, |10\rangle, |11\rangle)$, with qubit $0$ as control:
It flips the target iff the control is $|1\rangle$. On basis states it is exactly the classical XOR-into-target. On superpositions it is the gate that creates entanglement.
More generally, for any single-qubit unitary $U$, the controlled-$U$ gate is the block matrix
Taking $U = Z$ gives the controlled-$Z$ gate, $\mathrm{CZ} = \operatorname{diag}(1,1,1,-1)$, which is symmetric in control and target — there is no way to tell which qubit is which. That surprises people, and it is a good sanity check on whether you are thinking in matrices or in metaphors.
And since $HZH = X$, conjugating the target of a CZ by Hadamards produces a CNOT:
This is not a curiosity. Superconducting hardware often implements CZ natively, and the compiler turns your CNOTs into Eq. (24) without telling you.
6.6 Three-Qubit Gates
The Toffoli gate (CCX) flips the target iff both controls are $|1\rangle$: $|a,b,c\rangle \mapsto |a,\,b,\,c \oplus (a \wedge b)\rangle$. It is the reversible AND, and it is universal for classical reversible computation — anything a classical circuit can do, a circuit of Toffolis can do reversibly. It is also the gate in which quantum resource estimates for cryptanalysis are usually denominated.
The Fredkin gate (CSWAP) swaps two targets iff the control is $|1\rangle$. It is also classically universal.
6.7 The Reference Table
| Gate | Matrix | Action | Notes |
|---|---|---|---|
| $X$ | $\begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}$ | Bit flip; $\pi$ rotation about $x$ | Quantum NOT. Clifford. |
| $Y$ | $\begin{pmatrix} 0 & -i \\ i & 0\end{pmatrix}$ | Bit + phase flip | $Y = iXZ$. Clifford. |
| $Z$ | $\begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}$ | Phase flip | Invisible on $|0\rangle,|1\rangle$. Clifford. |
| $H$ | $\tfrac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix}$ | $Z$ basis $\leftrightarrow$ $X$ basis | Creates superposition. $H^2 = I$. Clifford. |
| $S$ | $\begin{pmatrix} 1 & 0 \\ 0 & i\end{pmatrix}$ | Quarter phase turn | $S^2 = Z$. Clifford. |
| $T$ | $\begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4}\end{pmatrix}$ | Eighth phase turn | Non-Clifford. $T^2 = S$. The expensive one. |
| $R_z(\theta)$ | $\operatorname{diag}\bigl(e^{-i\theta/2},\, e^{i\theta/2}\bigr)$ | Rotation about $z$ | Continuous family; $S,T,Z$ are special cases. |
| CNOT | $\begin{pmatrix} I & 0 \\ 0 & X\end{pmatrix}$ | $|a,b\rangle \mapsto |a, b \oplus a\rangle$ | Entangling. Clifford. |
| CZ | $\operatorname{diag}(1,1,1,-1)$ | Phase $-1$ on $|11\rangle$ | Symmetric in control/target. Clifford. |
| SWAP | $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}$ | $|a,b\rangle \mapsto |b,a\rangle$ | Equals three CNOTs. Not entangling. |
| Toffoli | $8\times 8$ permutation | $|a,b,c\rangle \mapsto |a,b,\,c \oplus ab\rangle$ | Reversible AND. Non-Clifford. Costed in attacks. |
7. Constructing Circuits
A quantum circuit is a picture of a matrix product. That is the whole idea, and if you hold onto it you will never be confused by a circuit diagram again.
Anatomy
Circuits read left to right. Matrix products compose right to left. So the circuit "first $A$, then $B$, then $C$" corresponds to the operator
$U = C \cdot B \cdot A$ — not $A \cdot B \cdot C$.
The order is reversed, because $C(B(A|\psi\rangle))$ applies $A$ first. Write it out once, slowly, and then never think about it again.
Gates in Parallel Are Tensor Products
Two gates acting on different qubits at the same moment combine with $\otimes$. If you apply $H$ to qubit $0$ of a two-qubit register and nothing to qubit $1$, the operator on the full space is not $H$ — it is
"Doing nothing" to a qubit is an operation — the identity — and it must appear explicitly in the tensor product. Every gate in an $n$-qubit circuit is secretly a $2^n \times 2^n$ matrix, padded with identities on the wires it does not touch.
Worked Example: Building a Bell Pair
Two gates. Watch every amplitude.
| Stage | Operator applied | State |
|---|---|---|
| $|\psi_0\rangle$ | — | $|00\rangle$ |
| $|\psi_1\rangle$ | $H \otimes I$ | $\tfrac{1}{\sqrt2}\bigl(|0\rangle + |1\rangle\bigr) \otimes |0\rangle \;=\; \tfrac{1}{\sqrt2}\bigl(|00\rangle + |10\rangle\bigr)$ |
| $|\psi_2\rangle$ | $\mathrm{CNOT}$ | $\tfrac{1}{\sqrt2}\bigl(|00\rangle + |11\rangle\bigr) \;=\; |\Phi^{+}\rangle$ |
The CNOT acted linearly on the superposition: it left $|00\rangle$ alone and mapped $|10\rangle \mapsto |11\rangle$. It did not "choose" a branch. It processed both terms, because it is a matrix, and matrices do not choose.
As a whole the circuit is the single unitary $U = \mathrm{CNOT} \cdot (H \otimes I)$ — note the reversed order. And here is a fact worth knowing: fed the four computational basis states, this one circuit outputs the four Bell states.
Run it backwards — CNOT, then $H$ — and you map the Bell basis onto the computational basis. That reversed circuit is the Bell measurement, and it is the engine of quantum teleportation and superdense coding. Both protocols are, at bottom, this three-gate circuit read in the two possible directions.
# Qiskit: the Bell pair, and the endianness trap from qiskit import QuantumCircuit from qiskit.quantum_info import Statevector qc = QuantumCircuit(2) qc.h(0) # qubit 0 -> |+> qc.cx(0, 1) # CNOT: control 0, target 1 print(Statevector(qc).data) # [0.70710678+0.j, 0.+0.j, 0.+0.j, 0.70710678+0.j] -> (|00> + |11>)/sqrt(2) # Careful: Qiskit is little-endian. Try this and read the output twice: qc2 = QuantumCircuit(2) qc2.x(0) print(Statevector(qc2).draw('latex_source')) # |01>, not |10>
Circuit Identities Are Just Matrix Algebra
Because circuits are products of matrices, you can prove circuit equivalences rather than guess at them. Three you will use forever:
- $H X H = Z$. A bit flip sandwiched between Hadamards is a phase flip. Compilers use this constantly to move gates past each other.
- $(H \otimes H)\,\mathrm{CNOT}_{0 \to 1}\,(H \otimes H) = \mathrm{CNOT}_{1 \to 0}$. Conjugating a CNOT by Hadamards on both qubits reverses control and target. If your hardware only offers CNOT in one direction, this is how you get the other.
- $\mathrm{SWAP} = \mathrm{CNOT}_{0\to1}\,\mathrm{CNOT}_{1\to0}\,\mathrm{CNOT}_{0\to1}$. The classic three-XOR swap, now in superposition. On hardware with limited connectivity, chains of SWAPs are how distant qubits are brought together — and they are a major hidden cost.
Depth, Width, and the Real Cost Model
Two numbers describe a circuit's size. Width is the number of qubits. Depth is the number of time steps — layers of gates that must happen in sequence. Depth, not gate count, is what races against your qubits' coherence time.
But for cryptographic resource estimation, neither is the headline figure. The number that matters is the T-count (or equivalently the Toffoli count), and Section 9 explains why a gate that looks like a diagonal $2\times2$ matrix ends up dominating the cost of breaking RSA.
You will sometimes see circuits that measure a qubit mid-way and then apply a gate conditioned on the classical outcome. This is always avoidable: any such circuit can be rewritten with all measurements pushed to the very end, replacing each classically-controlled gate with a quantum-controlled one.
Consequence: you may always analyse a circuit as "one big unitary, then measure everything." Real hardware often prefers mid-circuit measurement for practical reasons, but the mathematics never requires it.
8. Interference at Work: Deutsch's Algorithm
Time to see the whole machine run. Deutsch's algorithm [Deutsch1985] is the smallest problem on which a quantum computer provably beats a classical one, and it exhibits every idea in this tutorial in about six gates.
The Problem
You are given an oracle for an unknown function $f : \{0,1\} \to \{0,1\}$. There are four such functions: two are constant ($f \equiv 0$ or $f \equiv 1$) and two are balanced ($f(x) = x$ or $f(x) = \bar{x}$). Determine which class $f$ belongs to.
Classically you must query the oracle twice: knowing $f(0)$ alone tells you nothing about the class. Quantum mechanically, one query suffices.
The Trick: Phase Kickback
Recall the standard oracle from Eq. (15): $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. Now feed the target register the state $|-\rangle$ instead of a basis state, and compute:
Check both cases. If $f(x) = 0$ the target is unchanged and the factor is $+1$. If $f(x) = 1$ the two terms swap, giving $\tfrac{1}{\sqrt2}(|1\rangle - |0\rangle) = -|-\rangle$, and the factor is $-1$.
Read Eq. (27) again, because it is the most important line in this article. The oracle was supposed to write $f(x)$ into the target register. Instead, the target came out completely unchanged — and the value of $f(x)$ appeared as a phase on the control register. The function's output has been converted from a bit into a sign.
And signs, unlike bits, can cancel.
Phase kickback is the hinge on which quantum algorithms turn. It takes a value you cannot use — a bit sitting in a register you are not going to read — and converts it into a phase you can interfere with. Every quantum speedup in the literature does some version of this.
— Why Eq. (27) is worth memorisingThe Circuit
The Walkthrough
Prepare
$|\psi_0\rangle = |0\rangle \otimes |1\rangle$. The ancilla starts in $|1\rangle$, not $|0\rangle$ — that is deliberate.
Hadamard Both
$|\psi_1\rangle = |+\rangle \otimes |-\rangle = \tfrac{1}{\sqrt2}\bigl(|0\rangle + |1\rangle\bigr) \otimes |-\rangle$. The control is now a uniform superposition over both inputs to $f$; the ancilla is primed for kickback.
Query the Oracle — Once
By Eq. (27), applied linearly to both terms: $|\psi_2\rangle = \tfrac{1}{\sqrt2}\bigl((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigr) \otimes |-\rangle$. Factoring out the (unobservable) global phase $(-1)^{f(0)}$, the control register is $\tfrac{1}{\sqrt2}\bigl(|0\rangle + (-1)^{f(0) \oplus f(1)}|1\rangle\bigr)$.
Interfere
The control is $|+\rangle$ if $f(0) \oplus f(1) = 0$ and $|-\rangle$ if $f(0) \oplus f(1) = 1$. The final Hadamard maps $|+\rangle \mapsto |0\rangle$ and $|-\rangle \mapsto |1\rangle$, so $|\psi_3\rangle$ is a computational basis state — with certainty.
Measure
Outcome $0$ $\Rightarrow$ $f(0) = f(1)$, i.e. constant. Outcome $1$ $\Rightarrow$ $f(0) \neq f(1)$, i.e. balanced. No randomness, no repetition, one oracle call.
# Qiskit: Deutsch's algorithm end to end from qiskit import QuantumCircuit def deutsch(oracle): qc = QuantumCircuit(2, 1) qc.x(1) # ancilla -> |1> qc.h([0, 1]) # -> |+> (x) |-> qc.compose(oracle, inplace=True) # the single query qc.h(0) # interfere the two paths qc.measure(0, 0) # 0 = constant, 1 = balanced return qc constant = QuantumCircuit(2) # f(x) = 0 -> empty circuit balanced = QuantumCircuit(2) balanced.cx(0, 1) # f(x) = x -> a single CNOT
What Actually Happened Here
Notice what you did not learn. You never found out $f(0)$. You never found out $f(1)$. Those values are simply not recoverable from the output — and if you tried to extract them you would need a second query anyway.
What you learned was a global property of $f$: the single bit $f(0) \oplus f(1)$. The superposition let the oracle touch both inputs; the phase kickback turned the outputs into signs; the final Hadamard made those signs interfere so that the answer to the global question landed, deterministically, on one basis state.
Look at the shape of what we just did. It generalises almost verbatim:
Spread — Hadamards create a uniform superposition over the input space. Mark — the oracle imprints information about $f$ into phases. Interfere — a final transform makes wrong answers cancel and right answers reinforce. Measure — sample once.
Deutsch–Jozsa [DJ1992] scales this to $n$ bits. Simon's algorithm [Simon1997] uses the same skeleton to find a hidden XOR-mask exponentially faster than any classical method — and it was Simon's paper that directly inspired Shor. Shor [Shor1997] replaces the final Hadamard with the quantum Fourier transform, so that the interference reveals the period of a function; the period of $a^x \bmod N$ is what factors $N$. Grover [Grover1996] alternates "mark" and "reflect" steps to rotate amplitude gradually onto the marked item.
Different transforms, same skeleton. Learn the skeleton.
9. Universality, and What Is Actually Hard
Two questions now demand answers. Which gates do you need? And — the question almost nobody asks — which gates are expensive?
Universal Gate Sets
A set of gates is universal if any unitary on any number of qubits can be approximated to arbitrary accuracy by circuits built from that set.
- CNOT + all single-qubit gates is universal. Any $n$-qubit unitary decomposes into these [Barenco1995]. This is a continuous set, which is awkward for fault tolerance.
- $\{H,\, T,\, \mathrm{CNOT}\}$ is universal — and finite. Three gates. This is the standard set for fault-tolerant architectures, and the one you should have in your head.
- $\{H,\, \mathrm{Toffoli}\}$ is also universal, which is a small marvel: two real-valued gates suffice, no complex numbers required anywhere.
If a finite gate set generates a dense subgroup of $SU(2)$, then any single-qubit unitary can be approximated to within $\varepsilon$ using $O\bigl(\log^{c}(1/\varepsilon)\bigr)$ gates from that set, with a small constant $c$ [DN2005]. The cost of discreteness is merely polylogarithmic — which is why a finite gate set costs you essentially nothing.
The Result That Should Change Your Mind
Here is where most introductions stop, and where the interesting part begins.
Define the Clifford group as the set of unitaries generated by $\{H,\, S,\, \mathrm{CNOT}\}$. (Equivalently: the unitaries that map Pauli operators to Pauli operators under conjugation. Eq. (18), $HXH = Z$, is exactly an instance of that.) Clifford circuits can prepare Bell states. They can prepare GHZ states on a thousand qubits. They generate maximal entanglement, and they are the backbone of every quantum error-correcting code.
Any circuit consisting only of Clifford gates, preparation of computational basis states, and measurement in the computational basis can be simulated in polynomial time on a classical computer [Gottesman1998, AG2004].
Read that again with Section 4 in mind. Clifford circuits produce vast amounts of entanglement — and your laptop can simulate them efficiently.
The conclusion is unavoidable, and it contradicts what nearly every popular account will tell you:
Entanglement is necessary for quantum speedup, but it is nowhere near sufficient. A circuit can entangle a thousand qubits maximally and still be simulable on a laptop in polynomial time. If entanglement were the resource, Gottesman–Knill would be impossible.
— The correction that separates the informed from the enthusiasticTo be precise about the "necessary" half: for pure-state quantum computation, an exponential speedup does require entanglement that grows without bound with the problem size [JL2003]. So entanglement is a genuine prerequisite. It is simply not the thing that makes the problem hard for a classical simulator.
So What Is the Resource? Magic.
Add a single $T$ gate to a Clifford circuit and the Gottesman–Knill machinery breaks. Classical simulation cost grows exponentially in the number of $T$ gates. The technical name for the property that $T$ supplies — and that Clifford gates cannot manufacture — is magic, or non-stabilizerness [BK2005].
This is not a naming curiosity. It reaches all the way down into hardware, and all the way out into your threat model.
In the surface code — the leading approach to fault tolerance — Clifford gates are comparatively cheap: they can be implemented by moving and merging patches of qubits (lattice surgery) without ever leaving the protected code space.
The $T$ gate cannot be done this way. It requires magic state distillation: a whole subroutine that consumes many noisy ancillas to produce one sufficiently clean $|T\rangle$ resource state. Historically, magic state factories have dominated the space–time cost of a fault-tolerant machine.
This is why serious resource estimates for quantum attacks are quoted in T-counts and Toffoli counts, not in "number of gates." A cryptographer reading a paper claiming "$N$ qubits break RSA" and not asking about the Toffoli count is reading only half of the cost.
Superposition alone: classically simulable. Superposition plus entanglement (Clifford): still classically simulable, by Gottesman–Knill. Superposition plus entanglement plus magic: this is where quantum computation finally becomes something a classical computer cannot follow — and it is also where the engineering becomes brutally expensive.
10. What This All Means for Cryptography
Now we can state the cryptographic implications precisely, rather than dramatically.
Shor: Public-Key Cryptography Is Structurally Broken
Shor's algorithm [Shor1997] finds the period of $x \mapsto a^x \bmod N$ using the quantum Fourier transform as its interference step, and period-finding yields the factorisation of $N$. The same machinery solves discrete logarithms. Therefore RSA, finite-field Diffie–Hellman, DSA, ECDH, and ECDSA all fall to a sufficiently large fault-tolerant quantum computer — not by brute force, but by a polynomial-time algorithm.
There is no parameter increase that saves them. Doubling the RSA modulus roughly cubes the work for Shor; it does not change the asymptotics. This is why migration, not bigger keys, is the answer.
How Much Machine Would It Take?
Here the abstractions of this article become numbers. In 2019, Gidney and Ekerå estimated that factoring a 2048-bit RSA modulus would need about 20 million noisy physical qubits running for roughly 8 hours [GE2019]. In 2025, Gidney sharply revised this: fewer than one million noisy qubits, in under a week [Gidney2025] — a twentyfold reduction in qubit count, achieved not by better hardware but by better circuits.
Look at where the improvement came from, because it validates everything in Section 9: approximate residue arithmetic, denser storage of idle logical qubits, and a cheaper way of producing magic states. The headline gain was a reduction of the Toffoli count by more than two orders of magnitude. The bottleneck was never "qubits." It was magic.
Grover: Symmetric Cryptography Is Bruised, Not Broken
Grover's algorithm [Grover1996] searches an unstructured space of size $N$ in $O(\sqrt{N})$ queries, and this is provably optimal [BBBV1997]. Applied to key search, it takes AES-128 from $2^{128}$ to about $2^{64}$ iterations. That sounds catastrophic. It is not, for three reasons that every cryptographer should be able to recite:
- Each iteration is expensive. One Grover iteration requires a full, reversible, error-corrected AES circuit — including all the ancilla management and uncomputation from Section 5. This is not one AES evaluation; it is an AES evaluation running inside a fault-tolerant machine, and the constant factor is enormous.
- Grover barely parallelises. Running $M$ quantum machines in parallel gives you only a $\sqrt{M}$ speedup, not $M$. Classical brute force parallelises linearly. So you cannot buy your way out of the $2^{64}$ sequential depth — and that serial chain must maintain coherence throughout.
- Doubling the key restores everything. AES-256 under Grover retains roughly $2^{128}$ security, which is out of reach for any physically plausible machine. This is why NIST's post-quantum security categories are anchored to AES and why the mitigation is a one-line configuration change, not a redesign.
Hash functions are similar. Preimage search gets a square-root speedup; collision finding does not meaningfully improve over the classical birthday attack once the enormous quantum memory requirements of the known algorithms are costed honestly. SHA-256 remains, in practice, a 128-bit collision-resistant hash.
The Migration Already Under Way
NIST published its first post-quantum standards on 13 August 2024: FIPS 203 (ML-KEM, from CRYSTALS-Kyber, for key encapsulation), FIPS 204 (ML-DSA, from CRYSTALS-Dilithium, for signatures), and FIPS 205 (SLH-DSA, from SPHINCS+, a hash-based signature backup) [NIST2024]. In March 2025 NIST selected HQC, a code-based KEM, as a diversity backup for ML-KEM in case lattice assumptions are ever weakened. A FALCON-based signature standard (FN-DSA, FIPS 206) remains in development.
The reason the migration cannot wait for the hardware is straightforward. An adversary can record encrypted traffic today and decrypt it whenever a cryptographically relevant quantum computer arrives. Any secret whose confidentiality must outlive the machine — state secrets, medical records, long-lived identity keys — is already exposed if it travels under RSA or ECDH.
The quantum computer does not need to exist yet for the attack to be under way. It only needs to exist before the data stops mattering.
An Honest Reality Check
As of 2026, error-corrected quantum computing has crossed from theory into engineering — Google's Willow processor demonstrated that logical error rates fall exponentially as the surface-code distance grows [Google2025], which is the threshold result the whole field was waiting for. Several groups have now demonstrated on the order of a hundred logical qubits.
A cryptographically relevant machine needs on the order of a few thousand logical qubits, sustained for billions of sequential operations. The gap is large — several orders of magnitude — and it is an engineering gap, not a physics gap. That is precisely why the migration timelines are what they are: nobody credible claims RSA falls next year, and nobody credible claims it never falls.
Quantum information does not only attack cryptography; it supplies primitives that classical physics cannot. No-cloning (Section 5) gives BB84 and quantum key distribution, whose security rests on physics rather than on computational hardness. Bell-inequality violation certifies randomness device-independently — you can prove your random number generator is unpredictable without trusting its manufacturer, which no classical construction can do. Both are direct consequences of the linear algebra in this article.
11. How to Think Correctly: The Misconception Table
Everything above, compressed into the errors it is designed to prevent. If you retain one section of this article, retain this one.
| The Slogan | Why It Misleads | Think Instead |
|---|---|---|
| "A qubit is 0 and 1 at the same time." | Suggests a qubit holds two classical values. It holds neither. | A qubit is a unit vector in $\mathbb{C}^2$. "Superposition" is a statement about a basis, not about the state. |
| "Quantum computers try all answers in parallel." | If true, NP-complete problems would be easy. They are not believed to be. | One state vector evolves; one sample comes out. The work is arranging cancellation on wrong answers. |
| "Superposition is just ignorance about which value it has." | Then $H \cdot H$ could not restore $|0\rangle$ with certainty. It does. | Compare $\rho_{+}$ and $\rho_{\text{mix}}$ in Eq. (7). The coherences are the difference, and they are physical. |
| "Measurement reveals the value that was already there." | Bell's theorem experimentally rules out local pre-assigned values [Bell1964]. | Measurement is a basis-dependent, state-destroying operation governed by the Born rule. |
| "Entanglement transmits information instantly." | Alice's reduced state is $\tfrac12 I$ regardless of what Bob does — Eq. (14). | Entanglement creates correlation, never signalling. Correlations are only visible after a classical comparison. |
| "A qubit stores infinite information." | $\alpha,\beta$ are continuous but inaccessible. | Holevo: $n$ qubits yield at most $n$ classical bits, and the state is destroyed on readout. |
| "Entanglement is what makes quantum computers fast." | Clifford circuits entangle maximally and are classically simulable (Gottesman–Knill). | Entanglement is necessary, not sufficient. The scarce resource is magic — the $T$ gates. |
| "Global phase can be ignored, so all phases can." | Conflates the unobservable global phase with the load-bearing relative phase. | $e^{i\gamma}|\psi\rangle \equiv |\psi\rangle$. But $|+\rangle$ and $|-\rangle$ are perfectly distinguishable states. |
| "Draw the two qubits as two Bloch vectors." | Entangled states have no individual Bloch vectors — each part is mixed. | The Bloch sphere is for one qubit. Beyond that: vectors, matrices, tensor products. |
| "Quantum computers will break all encryption." | Ignores that only structured problems (factoring, DLP) fall. | Public-key falls to Shor. Symmetric and hash survive with doubled parameters. Lattice/code/hash-based schemes are the replacements. |
The Whole Picture in One Chain
Change the Norm
Replace the 1-norm over $\mathbb{R}_{\geq 0}$ with the 2-norm over $\mathbb{C}$. States become unit vectors in $\mathbb{C}^{2^n}$; amplitudes may now be negative or complex.
Unitarity Follows
Linearity plus norm preservation forces every gate to be unitary. Unitarity forces reversibility, which forces oracles and ancillas — and forbids cloning.
Amplitudes Cancel
Because amplitudes carry signs and phases, two paths to the same outcome can annihilate. This — not superposition, not parallelism — is the resource.
Algorithms Are Interference Patterns
Spread with Hadamards, mark with phase kickback, interfere with a final transform, measure once. Deutsch, Simon, Grover, and Shor are all this skeleton with different transforms.
Entanglement Is Not the Bottleneck
Clifford circuits entangle maximally yet simulate classically in polynomial time. The scarce, expensive resource is magic — supplied by $T$ gates, priced in magic-state distillation.
Therefore, Cryptography
Shor kills RSA and ECC in polynomial time. Grover only dents symmetric primitives. The real cost of an attack is measured in Toffolis and magic states — which is exactly why the 2025 RSA estimate improved twentyfold with no new hardware at all.
Exercises
Quantum information is not a spectator sport, and none of these require a computer. Pen, paper, and $2 \times 2$ matrices will do. When you want to go deeper, Nielsen and Chuang [NC2010] is the standard reference and its first four chapters cover everything above at greater length.
Verify $H|+\rangle = |0\rangle$ and $H|-\rangle = |1\rangle$ by direct matrix multiplication. Conclude that "measure in the $X$ basis" is implemented as "apply $H$, then measure in the $Z$ basis."
Prove $HXH = Z$ and $HZH = X$. Then explain, using the Bloch sphere, why $H$ is a $180°$ rotation about the axis $\tfrac{1}{\sqrt2}(\hat{x} + \hat{z})$ — and why that makes $H^2 = I$ obvious without any multiplication.
The gate $Z$ acts trivially on $|0\rangle$ (up to nothing at all) and on $|1\rangle$ (up to a global phase). Yet $Z$ is not the identity. Exhibit a single-qubit state and a measurement that distinguish $Z|\psi\rangle$ from $|\psi\rangle$ with certainty.
Hint: you have already seen the state. It is on the equator.
Verify $\mathrm{SWAP} = \mathrm{CNOT}_{0\to1}\,\mathrm{CNOT}_{1\to0}\,\mathrm{CNOT}_{0\to1}$ by tracking all four computational basis states through the three gates. Then explain why this identity means SWAP creates no entanglement, despite being built entirely from entangling gates.
Prove that the singlet $|\Psi^{-}\rangle = \tfrac{1}{\sqrt2}(|01\rangle - |10\rangle)$ is not a product state. Then write its $2\times2$ coefficient matrix and confirm that it has rank $2$ — connecting the algebraic proof to the rank characterisation of entanglement.
Derive the phase-kickback identity of Eq. (27) from scratch for a general $f : \{0,1\}^n \to \{0,1\}$: show that $U_f\bigl(|x\rangle \otimes |-\rangle\bigr) = (-1)^{f(x)}|x\rangle \otimes |-\rangle$, and hence that $U_f\bigl(H^{\otimes n}|0\rangle^{\otimes n} \otimes |-\rangle\bigr)$ places the entire truth table of $f$ into phases.
Show that a unitary can perfectly clone the pair $\{|0\rangle, |1\rangle\}$, and that a (different) unitary can perfectly clone $\{|+\rangle, |-\rangle\}$ — but that no single unitary clones all four. Explain in one sentence why this is exactly the security argument of BB84.
Compute $\rho_A = \operatorname{Tr}_B\bigl(|\Phi^{+}\rangle\langle\Phi^{+}|\bigr)$ explicitly and confirm Eq. (14). Then argue that $\rho_A$ is unchanged whether Bob measures in the $Z$ basis, the $X$ basis, or not at all — and that this is the no-signalling theorem.
(Superdense coding.) Alice holds qubit $A$ of $|\Phi^{+}\rangle$. Show that applying $I$, $X$, $Z$, or $ZX$ to her qubit alone maps the pair onto the four Bell states of Eq. (13). Since those are orthogonal, Bob can distinguish them perfectly with a Bell measurement. Conclude: one qubit, plus one pre-shared entangled pair, carries two classical bits.
The GHZ state $\tfrac{1}{\sqrt2}(|000\rangle + |111\rangle)$ is maximally entangled across three qubits, and is produced by one $H$ and two CNOTs. All three gates are Clifford. In light of Gottesman–Knill, what exactly does this tell you about the claim "entanglement is the source of quantum computational power"?
This is the most important exercise on the list. If you can answer it in two sentences, you have understood Section 9.
Quick Reference Glossary
| Term | Definition |
|---|---|
| Qubit | A unit vector in $\mathbb{C}^2$, defined up to global phase. Equivalently, a point of $\mathbb{CP}^1$ — the Bloch sphere. |
| Amplitude | A complex coefficient $\alpha_x$ in $|\psi\rangle = \sum_x \alpha_x|x\rangle$. Unlike a probability, it can be negative or complex — and can therefore cancel. |
| Born Rule | $\Pr[x] = |\alpha_x|^2$. The bridge from amplitudes to observable statistics, and the only source of randomness in the theory. |
| Global Phase | A factor $e^{i\gamma}$ multiplying the whole state. Physically undetectable; discard it freely. |
| Relative Phase | A phase between components of a superposition. Fully physical; $|+\rangle$ and $|-\rangle$ differ only by one and are perfectly distinguishable. |
| Interference | Amplitudes from distinct computational paths adding constructively or destructively. The one resource a classical probabilistic computer does not have. |
| Coherence | The off-diagonal entries of the density matrix. What interference consumes; what decoherence destroys. |
| Entanglement | A joint state that admits no factorisation $|\psi_A\rangle \otimes |\psi_B\rangle$. Basis-independent, unlike superposition. |
| Unitary | A matrix with $U^{\dagger}U = I$. Every quantum gate is one; hence every gate is reversible. |
| Oracle $U_f$ | $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$ — the standard reversible embedding of a classical function. |
| Phase Kickback | $U_f(|x\rangle \otimes |-\rangle) = (-1)^{f(x)}|x\rangle \otimes |-\rangle$. Converts a function's output bit into a phase that can interfere. |
| Ancilla | A workspace qubit. Must be uncomputed before reuse, or its residual entanglement destroys the interference you need. |
| Clifford Group | Unitaries generated by $\{H, S, \mathrm{CNOT}\}$; equivalently, those that map Paulis to Paulis. Entangling — yet classically simulable. |
| Gottesman–Knill | Clifford circuits with computational-basis input and measurement are simulable in classical polynomial time. |
| Magic | Non-stabilizerness — the property supplied by $T$ gates that Clifford operations cannot manufacture. The true scarce resource. |
| T-count | The number of $T$ (or Toffoli) gates in a circuit. The currency in which fault-tolerant cost — and therefore quantum attack cost — is actually denominated. |
| No-Cloning | No unitary copies an arbitrary unknown state. A two-line consequence of linearity; the foundation of QKD. |
| Holevo Bound | At most $n$ classical bits can be extracted from $n$ qubits, however cleverly you measure. |
| Circuit Depth | The number of sequential gate layers. Races directly against coherence time. |
| CRQC | Cryptographically Relevant Quantum Computer — one large enough to run Shor against deployed key sizes. Requires on the order of thousands of logical qubits. |
References
[NC2010] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press (2010). The standard reference; Chapters 1–4 cover this article in depth.
[Deutsch1985] Deutsch, D.: Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985). doi:10.1098/rspa.1985.0070
[DJ1992] Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439, 553–558 (1992). doi:10.1098/rspa.1992.0167
[Simon1997] Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997). The paper that inspired Shor.
[Shor1997] Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). doi:10.1137/S0097539795293172
[Grover1996] Grover, L.K.: A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, 212–219 (1996). doi:10.1145/237814.237866
[BBBV1997] Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997). Proves Grover's $\sqrt{N}$ is optimal — and that quantum computers do not simply solve NP.
[Barenco1995] Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995). doi:10.1103/PhysRevA.52.3457
[DN2005] Dawson, C.M., Nielsen, M.A.: The Solovay–Kitaev algorithm. Quantum Inf. Comput. 6(1), 81–95 (2006). arXiv:quant-ph/0505030
[Gottesman1998] Gottesman, D.: The Heisenberg representation of quantum computers. Proc. XXII Int. Colloquium on Group Theoretical Methods in Physics, 32–43 (1999). arXiv:quant-ph/9807006
[AG2004] Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004). doi:10.1103/PhysRevA.70.052328
[JL2003] Jozsa, R., Linden, N.: On the role of entanglement in quantum computational speed-up. Proc. R. Soc. Lond. A 459, 2011–2032 (2003). Establishes that entanglement is necessary — the other half of the Gottesman–Knill picture.
[BK2005] Bravyi, S., Kitaev, A.: Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316 (2005). doi:10.1103/PhysRevA.71.022316 Introduces magic state distillation.
[WZ1982] Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802–803 (1982). doi:10.1038/299802a0
[Dieks1982] Dieks, D.: Communication by EPR devices. Phys. Lett. A 92(6), 271–272 (1982).
[Holevo1973] Holevo, A.S.: Bounds for the quantity of information transmitted by a quantum communication channel. Problems of Information Transmission 9(3), 177–183 (1973).
[BB84] Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. Proc. IEEE Int. Conf. on Computers, Systems and Signal Processing, Bangalore, 175–179 (1984).
[Bell1964] Bell, J.S.: On the Einstein–Podolsky–Rosen paradox. Physics 1(3), 195–200 (1964). See the companion article in this series for a full treatment.
[GE2019] Gidney, C., Ekerå, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021). doi:10.22331/q-2021-04-15-433
[Gidney2025] Gidney, C.: How to factor 2048 bit RSA integers with less than a million noisy qubits. (2025). arXiv:2505.15917. Reduces the Toffoli count by over 100× and the qubit requirement twentyfold, with no change in hardware assumptions.
[Google2025] Google Quantum AI: Quantum error correction below the surface code threshold. Nature 638, 920–926 (2025). doi:10.1038/s41586-024-08449-y
[NIST2024] National Institute of Standards and Technology: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA). Published 13 August 2024. csrc.nist.gov/projects/post-quantum-cryptography. HQC selected as a backup KEM, 11 March 2025.