Reference
Notation
Each symbol the book uses, how to read it aloud, what it means, and where it is explained. Symbols marked as prerequisites are reviewed in Appendix C.
Logic and classical computation
SymbolRead asMeaningExplained in
\(f:\{0,1\}^n\to\{0,1\}\)f from n-bit strings to bitsA Boolean function: one yes/no answer for each \(n\)-bit input string.§2.1.2 Boolean functions and truth tables
\(a\oplus b\)a XOR bExclusive OR: one when exactly one input is one. It is addition modulo two.§2.1.3 Polynomial representation over the binary field
\(k_{\mathrm B}T\ln2\)k B T log twoLandauer’s minimum heat for erasing one equally likely bit at temperature \(T\).§2.3.1 Landauer’s principle
\(x\mapsto y\)x maps to yThe rule that sends each input \(x\) to the output \(y\).§2.3.3 Reversible function embeddings
\(U_f\)U sub fThe reversible oracle for \(f\): it keeps \(x\) and XORs \(f(x)\) into a target, \(U_f\ket{x,y}=\ket{x,y\oplus f(x)}\).Introduced in §2.3.3 Reversible function embeddings; developed in §7.1.3 Reversible quantum oracles
Probability and complex amplitudes
SymbolRead asMeaningExplained in
\(\sum_j\)sum over jAdd the following term for every value of \(j\).Prerequisite; reviewed in Appendix C Linear Algebra Reference
\(P(j\mid i)\)probability of j given iConditional probability: the chance of next state \(j\) when the current state is \(i\).§3.1.5 Probabilistic transitions
\(re^{i\phi}\)r e to the i phiAn amplitude with magnitude \(r\ge0\) and phase \(\phi\). Its outcome probability is \(r^2\).§3.4.1 Complex weights
\(|z|\)magnitude of zThe size of a complex number. \(|z|^2=z^*z\) turns an amplitude into a probability weight.§3.4.1 Complex weights
Vectors and states
SymbolRead asMeaningExplained in
\(v^T\)v transposeTurns a row into a column or a column into a row; \((a,b)^T\) is a column vector.Prerequisite; reviewed in Appendix C Linear Algebra Reference
\(\ket\psi\)ket psiA configuration or state, named \(\psi\). It first records weighted configurations, as in \(\sum_iv_i\ket i\); from the chapter on states it is a column vector. The brackets name it; they are not an operation.Introduced in §3.1.1 States; developed in §4.1.1 State vectors and ket notation
\(\ket0,\ \ket1\)ket zero, ket oneThe computational basis: \(\ket0=(1,0)^T\) and \(\ket1=(0,1)^T\).§4.1.1 State vectors and ket notation
\(\bra jS\ket i\)bra j S ket iThe weight of the arrow from configuration \(i\) to configuration \(j\) under the step \(S\), read right to left. For an operation \(U\) on vectors it is the matrix entry \(U_{ji}\).§3.1.2 Transitions
\(\bra\phi\)bra phiThe final configuration or state in a weight or amplitude, as in \(\bra jS\ket i\); as a vector, the conjugate-transpose row of \(\ket\phi\).Introduced in §3.1.2 Transitions; developed in §4.1.2 Inner products and transition amplitudes
\(\braket\phi\psi\)bra phi ket psiThe inner product \(\sum_j\phi_j^*\psi_j\): the transition amplitude with final state \(\phi\) on the left and initial state \(\psi\) on the right.§4.1.2 Inner products and transition amplitudes
\(\|v\|\)norm of vThe length of a vector, \(\sqrt{\braket vv}\). A state vector has norm one.§4.1.3 Geometric view
\(\ket a\otimes\ket b\)ket a tensor ket bThe joint state of two systems, also written \(\ket{ab}\). Dimensions multiply.Introduced in §4.2.3 The composite-state postulate; developed in §6.1.1 Tensor products and product bases
\(\ket{\Phi^+}\)Bell state phi plusThe entangled state \((\ket{00}+\ket{11})/\sqrt2\).§6.2.1 Bell-state preparation
Operators and measurement
SymbolRead asMeaningExplained in
\(I\)identityThe matrix that leaves every vector unchanged.Prerequisite; reviewed in Appendix C Linear Algebra Reference
\(A^\dagger\)A daggerThe adjoint: the conjugate transpose \((A^*)^T\), defined by \(\braket\phi{A\psi}=\braket{A^\dagger\phi}\psi\).§4.1.5 Reversibility of transitions
\(\operatorname{diag}(a,b)\)diagonal a, bThe diagonal matrix with entries \(a\) and \(b\).§4.1.4 Transition matrices
\(\ket e\bra e\)ket e bra eThe projector onto the unit vector \(\ket e\).§4.2.2 The measurement postulate
\(P_j\)P sub jThe projector for measurement outcome \(j\). The Born rule gives \(p(j)=\|P_j\ket\psi\|^2\).§4.2.2 The measurement postulate
\(X,\ Z,\ H\)X, Z, HThe bit flip, phase flip, and Hadamard gates.Introduced in §3.3.3 The Hadamard step; developed in §8.2.1 Pauli, Hadamard, and rotation gates
\(A^{\otimes n}\)A tensor n\(n\) copies combined by the tensor product. \(H^{\otimes n}\) applies \(H\) to each of \(n\) qubits; \(\ket\psi^{\otimes2}\) is two copies of \(\ket\psi\).§6.1.1 Tensor products and product bases
\(\rho\)rhoA density matrix, describing a preparation that need not be pure.Appendix D Mixed States and General Measurements
\(\operatorname{tr}\)traceThe sum of diagonal entries. With \(\rho\), the Born rule is \(p(j)=\operatorname{tr}(P_j\rho)\).Appendix D Mixed States and General Measurements
Algorithms and complexity
SymbolRead asMeaningExplained in
\((-1)^{f(x)}\)minus one to the f of xThe sign a phase oracle attaches to input \(x\): \(+1\) when \(f(x)=0\), \(-1\) when \(f(x)=1\).§7.3.2 Phase-oracle construction
\(\sin^2\theta=M/N\)sine squared theta equals M over NDefines the search angle \(\theta\) for \(M\) marked items among \(N\).§9.2.2 Initial success amplitude
\(O(g(n))\)big O of g of nAn eventual upper bound up to a constant factor.§10.1.2 Asymptotic notation
\(\Omega(g(n))\)big omega of g of nAn eventual lower bound up to a constant factor.§10.1.2 Asymptotic notation
\(\Theta(g(n))\)big theta of g of nBoth an upper and a lower bound: growth exactly like \(g(n)\) up to constants.§10.1.2 Asymptotic notation
\(\mathrm{BPP}\subseteq\mathrm{BQP}\)BPP is contained in BQPEvery problem in the first class is also in the second.§10.2.2 BPP and BQP
\((\lambda x.t)u\)lambda x dot t, applied to uIn lambda calculus, a function with parameter \(x\) and body \(t\), applied to \(u\).Appendix B Grammars and Lambda Calculus