CHAPTER 01

Information, probability, and computation

Learning goals. Encode information in bits, calculate conditional probabilities, distinguish reversible computation, and compare algorithms using stated costs.

1.1 Bits and representations

A bit labels one of two distinguishable alternatives. The labels do not specify the implementation: voltage, magnetization, or optical path may carry a bit if the alternatives can be prepared and read reliably. An $n$-bit string labels $2^n$ possibilities because every new position doubles the count.

The string 10110 represents

$$1\cdot2^4+0\cdot2^3+1\cdot2^2+1\cdot2+0=16+4+2=22.$$

It could instead label a color or database record. Encoding is a convention shared by the algorithm and its users. Confusing a number with its representation causes complexity errors. An integer $N$ requires about $\log_2N$ bits; a procedure using $N$ operations can be exponential in the input length.

NOT exchanges 0 and 1. XOR, written $\oplus$, is addition modulo two: $0\oplus0=1\oplus1=0$ and $0\oplus1=1\oplus0=1$. AND gives 1 exactly when both inputs are 1. A half adder outputs sum $s=a\oplus b$ and carry $c=ab$. For $a=b=1$, $(c,s)=(1,0)$ is binary 10, decimal two.

1.2 Probability and shots

A distribution assigns nonnegative values $p(x)$ summing to one. For a noisy bit, $p(1)=p$ and $p(0)=1-p$. A probability does not mean the bit has a fractional value; it predicts outcome frequencies across repeated preparations.

For independent trials, the probability of a particular sequence multiplies. Exactly $k$ ones in $N$ trials has probability

$$\Pr(K=k)=\binom Nk p^k(1-p)^{N-k}.$$

The binomial coefficient counts the sequences with that many ones. The sample proportion $\hat p=K/N$ has mean $p$ and variance $p(1-p)/N$. Its standard deviation decreases as $1/\sqrt N$. Four times the shots approximately halves statistical uncertainty.

Worked example. For $p=1/4$ and $N=400$,

$$\mathbb E[K]=100,\quad \operatorname{Var}(K)=75,$$ $$\operatorname{sd}(\hat p)=\sqrt{\frac{(1/4)(3/4)}{400}} =\frac{\sqrt3}{80}\approx0.02165.$$

An observed proportion 0.27 is unsurprising. The calculation assumes identically distributed, independent shots. Drift or correlated noise can invalidate the assumption without changing the arithmetic.

Conditional probability is

$$\Pr(A\mid B)=\frac{\Pr(A\cap B)}{\Pr(B)},\qquad \Pr(B)>0.$$

If 60 of 100 runs are accepted and 54 accepted runs are correct, conditional accuracy is $54/60=0.9$. The probability of an accepted correct result per attempted run is $54/100=0.54$. Both numbers matter when evaluating postselection.

Writing the joint probability in two ways gives Bayes’ rule:

$$\Pr(A\mid B)\Pr(B)=\Pr(B\mid A)\Pr(A),$$ $$\Pr(A\mid B)=\frac{\Pr(B\mid A)\Pr(A)}{\Pr(B)}.$$

A decoder uses this idea to infer which error likely produced an observed syndrome. The most likely error need not involve the fewest flipped bits if the prior probabilities differ.

1.3 Entropy and redundancy

Shannon entropy is

$$H(X)=-\sum_xp(x)\log_2p(x),$$

with $0\log_20=0$ by continuity. A fair bit has entropy one; a known bit has entropy zero. This measures uncertainty in a distribution, not memory size or energy [2].

Repeat a bit three times as 000 or 111. Under independent flips of probability $p$, majority voting fails when two or three bits flip:

$$p_\mathrm{fail}=\binom32p^2(1-p)+p^3=3p^2-2p^3.$$

At $p=0.1$ the failure probability is 0.028. Protection costs extra physical bits and assumes reliable encoding and decoding. A common disturbance flipping all three bits defeats the independent-noise model. Quantum codes will preserve arbitrary amplitudes rather than copies of an unknown state, but the need to specify noise remains.

1.4 Reversibility and workspace

A reversible transformation is one-to-one. NOT is reversible. AND alone is not: 00, 01, and 10 produce the same output. A function can be embedded in a reversible map by preserving its input:

$$U_f:(x,y)\longmapsto(x,y\oplus f(x)).$$

Applying it twice restores $y$, because $f(x)\oplus f(x)=0$. When the target starts at zero, it contains $f(x)$ afterward. The retained input prevents information loss.

CNOT maps $(a,b)$ to $(a,b\oplus a)$. Toffoli maps $(a,b,c)$ to $(a,b,c\oplus ab)$. Toffoli computes AND into a zero target while retaining the inputs. Its action permutes eight basis strings, so its matrix is also a quantum unitary.

Intermediate workspace can remain entangled with an answer. The compute–use–uncompute pattern calculates a function, uses it coherently, then reverses the calculation to clear temporary data. This is not housekeeping: distinguishable workspace can destroy interference between alternatives [3].

1.5 Comparing algorithms

Costs include gates, sequential depth, oracle calls, shots, memory, and elapsed time. Low depth can require many parallel qubits. Few queries can hide an expensive oracle. An accurate estimate may require many executions of the entire circuit.

$T(n)=O(n^2)$ means constants $C,n_0$ exist with $T(n)\le Cn^2$ for $n\ge n_0$. It is an asymptotic upper bound, not an exact runtime. $\Theta(n^2)$ includes a matching lower bound. Small-input overhead and constants remain relevant in practice.

P contains decision problems with polynomial-time deterministic classical algorithms. BPP permits bounded-error classical randomization. BQP permits bounded-error quantum computation with uniform polynomial-size circuits. NP means that yes-instances have efficiently verifiable certificates; it does not stand for “not polynomial.” Whether BPP equals BQP is open. No theorem says quantum computers efficiently solve all NP-complete problems.

Factoring has a polynomial-time quantum algorithm but is not known to be NP-complete. Grover gives a quadratic query improvement in unstructured search, not an automatic exponential improvement in every optimization task. A useful comparison specifies the problem, encoding, accuracy, and best applicable classical method.

1.6 Exercises