Quantum Information & Computation — formula sheet
Every boxed result from the 18 derivations of this unit on one page, for revision. Each title links to the full derivation, with its assumptions and where the formula breaks down. Constants: physical constants table.
The No-Cloning Theorem
A single fixed unitary can perfectly duplicate at most a set of mutually orthogonal states. The moment two inputs overlap without coinciding (\( 0<\lvert\langle\psi\vert\phi\rangle\rvert<1 \)), no unitary can copy both, and hence none can copy an arbitrary unknown state. Linearity alone kills universal cloning; the inner-product form (Step 8) shows the same conclusion follows from unitarity without ever choosing a basis.
Reduced States and the Partial Trace
The reduced density matrix is obtained by "summing over" — tracing out — everything belonging to \(B\). It is the one and only operator on \(\mathcal{H}_A\) that reproduces the Born-rule statistics of every local observable \(M_A\otimes I_B\). For an entangled \(\rho_{AB}\) it is generically a mixed state even when \(\rho_{AB}\) is pure: entanglement, viewed locally, looks like classical uncertainty.
Schmidt Decomposition of Bipartite States
Any bipartite pure state is a diagonal correlation between two local orthonormal bases: Alice's \(k\)-th mode is perfectly paired with Bob's \(k\)-th mode, weighted by \(\sigma_k\). The Schmidt rank \(r\) counts how many such pairs are active. \(r=1\) means \(|\psi\rangle=|1\rangle_A|1\rangle_B\) — a product state, no entanglement; \(r>1\) means the parties are entangled, and a flat spectrum \(\sigma_k=1/\sqrt r\) is maximal entanglement for that rank. The squared coefficients are the eigenvalues shared by \(\rho_A\) and \(\rho_B\), so the entanglement entropy \(S=-\sum_k\sigma_k^2\log\sigma_k^2\) is symmetric between the parties.
Quantum Channels: Kraus and Stinespring
Any physical evolution of a quantum system is a stochastic sum of "branches" \(\hat{K}_a\), each a possible influence of the environment; the completeness relation says the branch probabilities sum to one. Equivalently, the system was never really open — it was one factor of a larger world evolving by a single unitary \(\hat{U}\), and the apparent randomness is our tracing away of the environment. The minimal number of Kraus operators, \(r=\operatorname{rank}\hat J\le d^2\), is the Kraus rank, the smallest environment that can generate the channel.
CHSH Inequality and the Tsirelson Bound
The same four-term correlator that any local-realistic world holds at or below \(2\) can, in quantum mechanics with an entangled state, climb to \(2\sqrt2\approx2.828\) — and no state or observables push it past that. The gap \([2,\,2\sqrt2]\) is the measurable quantum advantage; the ceiling \(2\sqrt2\) is a hard consequence of Hilbert-space structure, not of any specific state.
Quantum Teleportation
An unknown qubit is transported perfectly (fidelity \(F=1\)) using exactly one shared ebit and two classical bits. Each of the four measurement outcomes is equally likely with probability \(\tfrac14\) and carries no information about \( \alpha,\beta \); the state is reconstructed at Bob only after his Pauli correction. The original at Alice is left maximally mixed, so exactly one copy exists at every instant \(-\) consistent with no-cloning \(-\) and because the classical bits travel no faster than light, no signalling is possible.
Superdense Coding
A single physical qubit, drawn from a pre-shared entangled pair and stamped with one of four local Pauli operations, carries a full two-bit message. The entanglement doubles the classical capacity of the channel: the map \((j,k)\mapsto U_{jk}=X^{k}Z^{j}\) encodes, the Bell measurement \((H\otimes I)\,\mathrm{CNOT}\) decodes, and recovery is exact. The second bit is paid for not by the channel but by the ebit consumed in the process.
Universality of CNOT with Single-Qubit Gates
Any coherent \( n \)-qubit operation, however entangling, is an exact finite word in the two-letter alphabet {CNOT, arbitrary single-qubit gate}. CNOT is the sole source of entanglement; the local rotations supply all the continuous freedom. The word length is finite but for a generic \( U \) grows like \( 4^n \).
The Solovay-Kitaev Theorem
Any single-qubit unitary can be compiled into an inverse-closed universal gate set with a number of gates that grows only as a fixed power of \(\log(1/\varepsilon)\), not as \(1/\varepsilon\). Each recursion level replaces the current error \(\varepsilon_{n-1}\) with \(c_{\mathrm{gc}}\varepsilon_{n-1}^{3/2}\) — a super-linear contraction — at the cost of multiplying the word length by \(5\). Because accuracy improves as a power tower while length grows geometrically, the trade-off is exponentially favourable. The exponent \(c\) is not fundamental: better commutator constructions and balanced generators lower it toward \(1\) (state-of-the-art numeric synthesis for specific sets reaches essentially \(c\to1\)).
Deutsch-Jozsa Oracle Separation
After exactly one oracle call, measure the \(n\) query qubits. Observing the all-zeros string certifies "constant"; observing any nonzero string certifies "balanced". The answer is exact — there is no error probability — because the balanced case makes the \(0^n\) amplitude vanish identically by cancellation, not merely make it small. A deterministic classical prover needs \(2^{n-1}+1\) evaluations in the worst case (having seen \(2^{n-1}\) equal outputs, one more equal output forces "constant"; a single disagreement forces "balanced").
Grover Search and Its Optimality
The number of oracle queries needed to find a unique marked item among \(N\) is asymptotically \(\tfrac{\pi}{4}\sqrt N\), a quadratic improvement over the classical \(\Theta(N)\) (expected \(N/2\) probes). The lower bound \(\Omega(\sqrt N)\) proves no quantum strategy does better for an unstructured oracle: the amplitude that any \(T\)-query algorithm can build up on a specific target grows only as \(T/\sqrt N\), so distinguishing all \(N\) marks demands \(T\gtrsim\sqrt N\).
The Quantum Fourier Transform Circuit
The exponentially large Fourier matrix collapses to a product of single-qubit rotations whose phases are the trailing binary fractions of the input. Building each factor needs one Hadamard plus a decreasing ladder of controlled-phase gates, so the entire \(2^{n}\times2^{n}\) unitary is compiled in a number of primitive gates that grows only quadratically in the qubit count.
Quantum Phase Estimation
Running the circuit and measuring the counting register returns an \(n\)-bit integer \(b\); dividing by \(2^{n}\) gives an estimate of the eigenphase. If \(\varphi\) is exactly representable in \(n\) bits the answer is deterministic; otherwise the output distribution is a sharp interference comb peaked at the nearest binary fraction, and a single shot lands within \(2^{-n}\) of the true phase with probability at least \(4/\pi^{2}\). To guarantee \(m\) correct bits with success probability \(1-\epsilon\), run with \(n=m+\lceil\log_2(2+\tfrac{1}{2\epsilon})\rceil\) counting qubits.
Shor's Algorithm: Order Finding and Factoring
Phase estimation on the modular-multiplication unitary reads off a random multiple s/r of the reciprocal period; continued fractions strip the random numerator s to expose r; and a single even, non-trivial order hands two proper factors of N to Euclid's algorithm. The favourable-a condition (r even and ar/2 ≢ −1) holds for at least half of the admissible bases, so a handful of random a suffices.
Von Neumann Entropy and Subadditivity
The quantum entropy is nothing but the classical Shannon entropy of the probabilities {pk} read off the density matrix in its own eigenbasis; measurement in any other basis can only increase it. For a joint system, the total ignorance is at most the sum of the ignorance about each part (subadditivity, with the deficit equal to the mutual information I(A:B)) and at least the difference of the two (Araki–Lieb). The lower bound is what forces a highly entangled pure whole to have low total entropy while its parts are individually very mixed.
The Holevo Bound
The classical mutual information any measurement can create between the prepared label and its outcome is capped by the Holevo χ — the entropy of the average state minus the average entropy of the members. Since S(ÏÌ„) ≤ log2 d and the average entropy is ≥ 0, a d-level system yields at most log2 d bits; a qubit (d = 2) yields at most one bit, no matter how cleverly encoded or measured.
Landauer's Erasure Principle
Destroying one bit of information — collapsing two equally likely memory states into one — forces at least kBT ln 2 of heat out of the memory and into the surrounding bath, and raises the bath's entropy by at least kB ln 2. The cost is per erased bit, scales linearly with temperature, and is completely independent of how the bit is physically encoded. The minimum work that must be supplied to perform the erasure equals this same kBT ln 2 in the quasistatic limit.
Stabilizer Codes and Error Discretization
Whatever continuous error channel ℰ struck the codeword, the act of measuring the stabilizer generators forces a random but definite outcome — the syndrome s — and simultaneously collapses the state to as if a single Pauli Ps had occurred. The apparatus never "sees" the continuum; it reports one of finitely many syndromes. Applying the corresponding Pauli recovery Ps† returns the exact original codeword. A code that corrects every Pauli in its correctable set therefore corrects every error, continuous ones included. Separately, any circuit of Clifford gates plus Pauli measurement on such states is classically simulable in poly(n) time.