Skip to content

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 n-bit string labels 2 n 2^n possibilities because every new position doubles the count.

The string 10110 represents

1⋅2 4+0⋅2 3+1⋅2 2+1⋅2+0=16+4+2=22.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 N requires about log 2 N\log_2N bits; a procedure using N N operations can be exponential in the input length.

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

## 1.2 Probability and shots

A distribution assigns nonnegative values p(x)p(x) summing to one. For a noisy bit, p(1)=p p(1)=p and p(0)=1−p 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 k ones in N N trials has probability

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

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

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

𝔼[K]=100,Var(K)=75,\mathbb E[K]=100,\quad \operatorname{Var}(K)=75, sd(p̂)=(1/4)(3/4)400=3 80≈0.02165.\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∣B)=Pr(A∩B)Pr(B),Pr(B)>0.\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 54/60=0.9. The probability of an accepted correct result per attempted run is 54/100=0.54 54/100=0.54. Both numbers matter when evaluating postselection.

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

Pr(A∣B)Pr(B)=Pr(B∣A)Pr(A),\Pr(A\mid B)\Pr(B)=\Pr(B\mid A)\Pr(A), Pr(A∣B)=Pr(B∣A)Pr(A)Pr(B).\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)=−∑x p(x)log 2 p(x),H(X)=-\sum_xp(x)\log_2p(x),

with 0 log 20=0 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 p, majority voting fails when two or three bits flip:

p f a i l=(3 2)p 2(1−p)+p 3=3 p 2−2 p 3.p_\mathrm{fail}=\binom32p^2(1-p)+p^3=3p^2-2p^3.

At p=0.1 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)↦(x,y⊕f(x)).U_f:(x,y)\longmapsto(x,y\oplus f(x)).

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

CNOT maps (a,b)(a,b) to (a,b⊕a)(a,b\oplus a). Toffoli maps (a,b,c)(a,b,c) to (a,b,c⊕a b)(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].

Laboratory L01 — Reversible logic and repetition. Explore CNOT and Toffoli truth tables. Change the flip probability and compare unencoded and three-bit failure probabilities. Identify the independence assumption.

## 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)T(n)=O(n^2) means constants C,n 0 C,n_0 exist with T(n)≤C n 2 T(n)\le Cn^2 for n≥n 0 n\ge n_0. It is an asymptotic upper bound, not an exact runtime. Θ(n 2)\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

1.1. Convert 45 to six-bit binary and count the possible strings.

Show solution / guidance

45=32+8+4+1 45=32+8+4+1, giving 101101. Six bits label 2 6=64 2^6=64 strings.

1.2. For outcome probability 0.8, find the standard deviation of the observed proportion in 100 and 1,600 shots.

Show solution / guidance

0.16/100=0.04\sqrt{0.16/100}=0.04 and 0.16/1600=0.01\sqrt{0.16/1600}=0.01. Sixteen times the shots gives four times smaller standard deviation.

1.3. Factor 3 p 2−2 p 3−p 3p^2-2p^3-p. When does repetition help?

Show solution / guidance

It is −p(2 p−1)(p−1)-p(2p-1)(p-1), negative for 0<p<1/2 0<p<1/2. It vanishes at 0,1/2,1 0,1/2,1. A known channel with p>1/2 p>1/2 can first have its outputs relabeled.

1.4. Explain why AND alone cannot be unitary and Toffoli can.

Show solution / guidance

AND merges orthogonal inputs and changes dimension. A unitary preserves inner products and dimension. Toffoli is a bijective basis permutation with orthonormal matrix columns.

1.5. An algorithm calls an oracle N\sqrt N times; each call costs N N elementary operations. What work is hidden by a query count?

Show solution / guidance

The calls alone cost N 3/2 N^{3/2} elementary operations. An oracle-call bound does not include implementation, preparation, or other algorithmic work unless explicitly stated.

IN THIS CHAPTER