Classical Information Review

Classical information theory supplies the control model against which many quantum-information claims are stated. Given a protocol, benchmark, or proposed advantage, the task is to identify the alphabet and source distribution, stochastic channel, code and decoder, blocklength, rate, error or security criterion, access model, and total cost before comparing it with a quantum alternative. This page develops that source-to-decoder ledger for finite discrete alphabets, iid sources, and discrete memoryless channels. It uses standard information measures without replacing their canonical mathematical derivations, and it stops before quantum-channel capacities, security proofs, or complexity-class theory.

Required background. Probability Spaces, Light Version supplies finite sample spaces, random variables, and distributions. Conditional Probability supplies the joint, conditional, and marginal probability manipulations used to define channels and decoding errors.

Helpful background. Entropy repairs Shannon, joint, conditional, and binary-entropy conventions; Relative Entropy repairs KL support conditions and statistical interpretation; and Classical Probability versus Quantum Probability marks the boundary between a single classical sample-space model and probabilities generated by quantum states and measurements.

Classical Information as an Operational Baseline

A classical information problem is not specified by an entropy value alone. It is an end-to-end task with a source, a permitted representation, a transformation or communication medium, a decision rule, and a criterion for success. A compact workflow is

source and alphabet
  -> encoder and code
  -> stochastic channel
  -> decoder or decision rule
  -> error, security, rate, and cost report

The objects in that workflow answer different questions:

Layer	Required declaration
source	alphabet, distribution, correlations, and block model
encoder	what input is mapped to which codeword, and with what preprocessing
channel	conditional law, number of uses, memory assumptions, and constraints
decoder	observation-to-output map, including ties, erasures, or aborts
criterion	loss, average or maximal error, secrecy, precision, and confidence
accounting	rate units, access model, memory, repetitions, and total cost

The same physical link can support several tasks, and the same probability distribution can appear in several operational models. A source-coding problem asks how economically a source can be represented. A channel-coding problem asks how reliably messages can be conveyed through noise. A hypothesis test asks which model generated an observation. These tasks may use the same entropy or divergence, but they do not share one interchangeable rate or error criterion.

The baseline is therefore a contract, not merely a formula. Only after the contract is fixed does a classical-to-quantum comparison have a stable denominator.

Sources, Alphabets, and Distributions

Let a discrete source produce a random variable $X$ taking values in a finite alphabet $\mathcal X$ with probability mass function

$$p_X(x)\ge 0, \qquad \sum_{x\in\mathcal X}p_X(x)=1.$$

The alphabet lists possible symbols; the distribution gives their ensemble frequencies. Neither specifies what the symbols mean. A binary alphabet could encode logical values, detector clicks, source labels, error flags, or decisions. Semantic importance must enter through the task or loss function rather than being inferred from probability alone.

For an iid source block $X^n=(X_1,\ldots,X_n)$,

$$p_{X^n}(x^n) = \prod_{i=1}^{n}p_X(x_i).$$

This factorization is an assumption. A stationary source need not be independent, a device can drift, and a channel can have memory. When correlations matter, reporting only the one-symbol marginal $p_X$ discards operationally relevant structure.

A source model should state at least:

• the symbol alphabet and blocklength;
• the probability law or family of laws;
• whether samples are iid, Markovian, adversarial, or otherwise correlated;
• what side information is available to the encoder and decoder;
• whether exact reconstruction, bounded distortion, classification, or another output is required.

The realized sequence $x^n$ is not the distribution $p_{X^n}$. Entropy is an ensemble average, while the information content $-\log_2p_{X^n}(x^n)$ varies from one realization to another. Likewise, an empirical frequency observed in one finite block is an estimator of a source parameter, not automatically the parameter itself.

Entropy, Divergence, and Mutual Information

This page uses base-$2$ logarithms, so entropies and divergences are reported in bits, with $0\log_2 0=0$ by continuity. For $X\sim p_X$, the Shannon entropy is

$$H(X) = -\sum_{x\in\mathcal X}p_X(x)\log_2p_X(x).$$

For a pair $(X,Y)$, the compact dictionary is

$$H(X,Y) = -\sum_{x,y}p_{XY}(x,y)\log_2p_{XY}(x,y),$$ $$H(Y\mid X) = \sum_xp_X(x)H(Y\mid X=x),$$

and

$$\begin{aligned} I(X{:}Y) &=H(X)+H(Y)-H(X,Y)\\ &=H(Y)-H(Y\mid X). \end{aligned}$$

Entropy measures average uncertainty under a declared ensemble. Conditional entropy measures the uncertainty remaining after the conditioning variable is known. Mutual information measures statistical dependence: it is zero exactly when $P_{XY}=P_XP_Y$ for finite alphabets. It does not by itself establish causation, usefulness, secrecy, or an achievable communication rate.

For distributions $P=(p_x)$ and $Q=(q_x)$ on the same alphabet,

$$D(P\|Q) = \sum_{x:p_x>0}p_x\log_2\frac{p_x}{q_x}.$$

If $p_x>0$ for some $x$ with $q_x=0$, then $D(P\|Q)=+\infty$. The divergence is directed and is not a metric. The identity

$$I(X{:}Y) = D\!\left(P_{XY}\middle\|P_XP_Y\right)$$

connects dependence to distinguishability from the product model. Its proof and the general properties of these quantities remain with the Mathematical Toolkit owners linked above; here the quantities are inputs to source, channel, and comparator audits.

Stochastic Channels and Data Processing

A finite classical channel is a conditional distribution $W(y\mid x)$ from an input alphabet $\mathcal X$ to an output alphabet $\mathcal Y$. This page writes inputs as columns and outputs as rows, so every input column is normalized:

$$\sum_{y\in\mathcal Y}W(y\mid x)=1.$$

For an input law $p_X$, the channel induces

$$p_{XY}(x,y)=p_X(x)W(y\mid x),$$

and

$$p_Y(y)=\sum_xW(y\mid x)p_X(x).$$

The conditional law is not a complete communication system. It does not specify the input distribution, encoder, decoder, blocklength, assistance, cost, or criterion for success.

If $X\to Y\to Z$ is a Markov chain, so that $Z$ is produced from $Y$ without additional access to $X$, then the data-processing inequality gives

$$I(X{:}Z)\le I(X{:}Y).$$

Postprocessing can preserve or discard information about $X$, but it cannot create dependence on $X$ that was absent from $Y$. This statement assumes the declared Markov structure; hidden side information can invalidate an informal application of the inequality.

Worked audit: a binary symmetric channel

Take a uniform binary input and a binary symmetric channel with crossover probability $\epsilon=0.11$. With rows indexed by output $y$ and columns by input $x$,

$$W = \begin{pmatrix} 0.89&0.11\\ 0.11&0.89 \end{pmatrix}.$$

Each column sums to one. Symmetry and the uniform input make $Y$ uniform, so $H(Y)=1$ bit. Given either input, the output flips with probability $0.11$, hence

$$H(Y\mid X) = h_2(0.11) = 0.499915958 \quad\text{bits},$$

where

$$h_2(p) = -p\log_2p-(1-p)\log_2(1-p).$$

Therefore

$$\begin{aligned} I(X{:}Y) &=H(Y)-H(Y\mid X)\\ &=1-h_2(0.11)\\ &=0.500084042 \quad\text{bits per channel use}. \end{aligned}$$

For a BSC, symmetry makes the uniform input capacity achieving, so this value also equals

$$C=\max_{p_X}I(X{:}Y).$$

The capacity is an optimized asymptotic limit for this memoryless channel. It is not an achieved finite-block rate, a gate rate, or hardware throughput.

Source Coding and Compression

A lossless source code represents a source block by a bit string from which the decoder can reconstruct that block. For a one-symbol binary prefix code with codeword lengths $\ell(x)$, the Kraft inequality requires

$$\sum_x2^{-\ell(x)}\le 1,$$

and the mean length is

$$L=\sum_xp_X(x)\ell(x).$$

For any binary prefix code, $L\ge H(X)$. Suitable codes for long iid blocks can approach the entropy rate, but this is an ensemble and asymptotic statement. It does not say that every individual string is compressible, that a one-symbol code achieves $H(X)$, or that model descriptions and implementation overhead are free.

Compression changes the representation of source data. It does not protect the resulting bits against a noisy channel. Conversely, adding redundancy for error correction generally increases the transmitted blocklength. Keeping these two operations separate prevents the common claim that “coding” must either always compress or always expand data.

Worked audit: a biased Bernoulli source

Let $p_X(1)=0.1$ and $p_X(0)=0.9$. Then

$$\begin{aligned} H(X) &=h_2(0.1)\\ &=0.468995594 \quad\text{bits per source symbol}. \end{aligned}$$

For $10{,}000$ iid symbols, the first-order entropy benchmark is

$$10{,}000H(X) = 4{,}689.955936 \approx 4{,}690 \quad\text{bits}.$$

This can be compared with the $10{,}000$ bits needed by the raw one-bit-per-symbol representation. It is not the encoded length of every realized block. A binary single-symbol prefix code still needs one bit for each of the two symbols and therefore has mean length one bit per symbol. Approaching the entropy requires block or arithmetic-style coding, together with finite-block, model, header, and implementation overhead.

Channel Coding and Reliable Decoding

A channel code uses redundancy to convey one of $M$ messages through $n$ channel uses. For a discrete memoryless channel,

$$W^n(y^n\mid x^n) = \prod_{i=1}^{n}W(y_i\mid x_i).$$

An encoder maps each message $m\in\{1,\ldots,M\}$ to a codeword $x^n(m)$. A decoder maps the received word $y^n$ to an estimate $\widehat m$ or, when allowed, an erasure or abort. If $M=2^k$, the code rate is

$$R = \frac{k}{n} = \frac{\log_2M}{n} \quad\text{message bits per channel use}.$$

For a discrete memoryless channel, the Shannon capacity is

$$C = \max_{p_X}I(X{:}Y) \quad\text{bits per channel use}.$$

In its asymptotic form, the noisy-channel coding theorem separates rates below capacity, for which sequences of codes can drive error toward zero, from rates above capacity, which are not reliably achievable under the theorem’s assumptions. The theorem does not select a practical code, fix a decoder’s computational cost, or give the latency and throughput of a finite device.

Source and channel rates use different denominators. A source code reports bits per source symbol; a channel code reports message bits per channel use. Connecting them requires an explicit interface. Under the assumptions of a source–channel separation theorem, one may compress and then protect the compressed bits, but those assumptions and both blocklengths must be declared rather than hidden in a single “compression rate.”

Finite Blocks, Error Criteria, and Rates

For $M$ equiprobable messages, the average decoding error is

$$P_{\mathrm e}^{\mathrm{avg}} := \frac1M \sum_{m=1}^{M} \Pr\!\left[\widehat M\ne m\mid M=m\right],$$

whereas the maximal error is

$$P_{\mathrm e}^{\max} := \max_m \Pr\!\left[\widehat M\ne m\mid M=m\right].$$

Always $P_{\mathrm e}^{\mathrm{avg}}\le P_{\mathrm e}^{\max}$ for equiprobable messages. A code can protect common or easy messages well while leaving one message much less reliable, so an unqualified “error rate” is insufficient. A one-shot or selected finite-block result must also remain distinct from an asymptotic sequence-of-codes claim.

A finite-block report should include at least:

Quantity	Meaning
$n$	number of channel uses
$M$	message-set size
$R=\log_2M/n$	nominal code rate
$\varepsilon$	declared average, maximal, or other error target
constraints	energy, bandwidth, memory, latency, or assistance
implementation	encoder and decoder cost, repetitions, and elapsed time

For many memoryless channels under regularity conditions, a normal approximation has the form

$$R^*(n,\varepsilon) = C - \sqrt{\frac{V}{n}}\, Q^{-1}(\varepsilon) + O\!\left(\frac{\log n}{n}\right),$$

where $V$ is the channel dispersion and $Q^{-1}$ is the inverse Gaussian tail function. This is an approximation with a stated regime, not an exact formula for every finite channel and code. Bounds, normal approximations, selected-code performance, and experimentally measured throughput are four different claims.

Even a fully specified $R$ is dimensionless per channel use. Converting it to bits per second requires a channel-use rate and must include synchronization, pilots, decoding, retries, discarded blocks, and other system costs inside the chosen boundary.

Keys, Randomness, and Security Boundaries

A key can have high Shannon entropy and still be known to an adversary. Security requires a relation among the key, adversarial information, protocol transcript, and intended ideal resource—not merely a marginal distribution for $K$.

For a classical key $K$ and adversarial record $E$, marginal uniformity is represented by $P_K=U_K$. Independence would additionally require $P_{KE}=P_KP_E$. A useful classical distance from an ideal uniform independent key is

$$d_{\mathrm{TV}}\!\left(P_{KE},U_KP_E\right) := \frac12 \sum_{k,e} \left| P_{KE}(k,e)-U_K(k)P_E(e) \right|.$$

If this distance is large, an adversary can distinguish the real joint distribution from the ideal resource even when $H(K)$ is maximal. A nominal key length also says nothing by itself about freshness, authentication, leakage during reconciliation, implementation compromise, or safe composition with another protocol.

The one-time pad illustrates the boundary sharply: information-theoretic secrecy needs a uniform secret key independent of the message and adversary, at least as long as the message, and never reused. This page owns that diagnostic distinction. Quantum Key Distribution owns protocol-specific and composable-security analysis, including finite-key accounting and authentication assumptions.

Complexity, Access, and Cost Models

An algorithmic comparison begins before the first counted operation. The same mathematical input can be supplied as an explicit list, a stream of samples, a prepared quantum state, a sparse-access oracle, a block encoding, or a QRAM query interface. These inputs expose different information at different construction costs.

Every baseline should declare:

Contract item	Required question
representation	Is the input explicit, sampled, streamed, state encoded, or oracle encoded?
access	What does one query return, and can it be made coherently?
construction	Who builds the data structure, state, oracle, or block encoding?
output	Is the answer a full vector, scalar estimate, decision, or sample?
accuracy	Which norm, loss, precision, failure probability, and confidence apply?
resources	Which queries, gates, samples, memory, communication, energy, and time count?

Quantum Oracles specializes this ledger for coherent quantum access, supplied inverse, controlled, powered, or family capabilities, and reductions between oracle forms. This page retains the general task, representation, output, accuracy, construction, and total-cost comparator used to decide whether classical and quantum procedures receive equivalent information and owe equivalently useful outputs.

A query-complexity separation compares algorithms inside a query model. It is not automatically a gate-count, memory, wall-clock, energy, or application-level advantage. Likewise, a circuit that processes an amplitude-encoded state in polylogarithmic depth does not imply that arbitrary classical data can be loaded in polylogarithmic total time.

Query Complexity owns matched fixed-cap deterministic, randomized, exact, zero-error, and bounded-error query measures and their lower-bound certificates inside an already fixed black-box model. This review retains the broader comparator across representation, construction, output utility, accuracy, and total cost beyond query count.

The Quantum Algorithms and Complexity chapter guide applies this matched representation, access, output, error, construction, and total-cost boundary to a complete algorithm claim. Quantum Complexity Classes owns formal class definitions, promises, reductions, and oracle qualifications. The classical baseline here asks the prior operational question: do the classical and quantum procedures receive equivalent access and have to produce equivalently useful outputs?

Build a Fair Classical Comparator

To audit a proposed quantum advantage, fill in the classical ledger before comparing headline operation counts:

Ledger field	What must be fixed
task	decision, search, sampling, estimation, communication, or reconstruction
source	alphabet, instance distribution, correlations, and side information
input contract	representation, encoding, and access operations
process	stochastic channel, classical algorithm, code, and decoder
block structure	source length, channel uses, batches, and repetitions
acceptance	output form, loss, precision, error, security, success or failure probability, and confidence
resources	queries, samples, gates, memory, communication, and assistance
hidden work	loading, preprocessing, compilation, decoding, verification, and readout
normalization	per symbol, use, sample, accepted output, or elapsed second
evidence scope	theorem, simulation, benchmark, experiment, or projection

Then apply four checks.

1. Match information access. Neither side receives a stronger oracle, a precomputed data structure, or unpriced advice.
2. Match the output. A quantum sample or scalar estimate is not compared with a classical requirement to print an entire vector.
3. Match accuracy and success. Precision, approximation metric, error target, confidence, postselection, and retry policy are the same.
4. Compare total cost. Include input preparation, classical control, memory, communication, verification, and repetitions as well as the advertised inner loop.

A comparator can be theoretical or empirical, but its status must be explicit. A complexity-theoretic lower bound, the fastest published classical implementation, and a convenient baseline script are different comparators. Claims, Hype, and Evidence Standards classifies the resulting claim, Algorithmic Benchmarking owns the executable end-to-end benchmark, and Verification of Quantum Advantage owns the dated classical frontier and validation burden.

Choose the Canonical Owner

This review composes a baseline from standard tools. It does not become a second home for their derivations or for downstream quantum results.

Question	Canonical destination
How should I enter this chapter?	Information-Theoretic Foundations routes by carrier, state, process, measure, and task.
Which broader learning sequence should I follow?	The Quantum Information Roadmap supplies the staged route.
Which mathematical prerequisites need repair?	Math Needed for Quantum Information maps QI tasks to their mathematical owners.
Where are Shannon-entropy derivations and properties?	Mathematical Toolkit Entropy.
Where are KL support, positivity, and statistical meaning?	Mathematical Toolkit Relative Entropy.
Why does quantum probability require more than one classical sample space?	Classical Probability versus Quantum Probability.
What distinguishes a bit, qubit, mode, device, and logical encoding?	Bits, Qubits, Qudits, and Modes.
Where do von Neumann entropy, quantum relative entropy, and quantum data processing live?	Quantum Entropy.
Where are CPTP maps, Kraus, Choi, Stinespring, and quantum noise?	Quantum Channels and Noise.
Where are classical–quantum ensembles, Holevo and coherent information, quantum communication tasks, and capacity families?	Communication with Quantum Systems.
Where is composable key security?	Quantum Key Distribution.
Where are formal complexity classes and reductions?	Quantum Complexity Classes.
Where is a claim classified and calibrated?	Claims, Hype, and Evidence Standards.
Where is end-to-end performance benchmarked?	Algorithmic Benchmarking.
Where is an advantage claim validated against the classical frontier?	Verification of Quantum Advantage.

Full coding-theorem proofs, lossy rate–distortion theory, continuous variables and differential entropy, error exponents, network information theory, cryptographic constructions, quantum capacities, and complexity-class theory belong with those specialist owners or future dedicated pages.

Common Baseline and Coding Mistakes

Treating entropy as a property of one realized string. $H(X)$ averages over a declared ensemble. The self-information of a realization is $-\log_2p_X(x)$, and no lossless compressor can shorten every possible input string.

Leaving the logarithm base implicit. Base $2$ gives bits and base $e$ gives nats. Changing the base rescales the number; it does not change the underlying distribution.

Ignoring support in KL divergence. A term with positive $p_x$ and zero $q_x$ makes $D(P\|Q)$ infinite. Reversing the arguments can therefore change a finite divergence into an infinite one.

Calling mutual information causal. $I(X{:}Y)>0$ detects dependence. It does not identify a causal direction or rule out a common cause.

Hiding the channel orientation. A matrix can be row stochastic or column stochastic by convention. State which index is the input, verify the corresponding normalization, and then compute the output law consistently.

Confusing source coding with channel coding. Compression removes predictable redundancy; error-correcting codes add structured redundancy. Their rates have different numerators and denominators.

Reporting capacity as finite throughput. Capacity is an optimized asymptotic boundary under declared channel assumptions and constraints. A finite implementation must report its selected code, decoder, target error, latency, retries, and channel-use rate.

Using “error rate” without a criterion. Average and maximal message error can differ substantially. A worst-case guarantee cannot be inferred from an average alone.

Equating key entropy with secrecy. A marginally uniform key may be perfectly correlated with an adversary. Security also requires independence, freshness, authentication assumptions, and a suitable composable criterion.

Pricing an oracle only for the quantum algorithm. A fair comparison states how both algorithms obtain the input, what construction and loading cost, and whether their outputs and success requirements match.

Forgetting the classical boundary of a quantum experiment. A quantum measurement produces a classical record, but different incompatible measurements are not thereby random variables on one measurement-independent classical sample space.

Exercises

1. Binary-erasure source/channel/decoder ledger

Let $P_X(1)=0.3$. Use a binary erasure channel with erasure probability $\delta=0.2$, the identity encoder, blocklength one, output alphabet $\{0,1,?\}$, and a decoder that maps an erasure to $0$. Write the complete one-use ledger and compute the average and maximal decoding errors.

Solution

The source alphabet is $\mathcal X=\{0,1\}$ with

$$P_X(0)=0.7, \qquad P_X(1)=0.3.$$

With outputs ordered as $0,1,?$ and inputs ordered as $0,1$, the nonzero channel probabilities are

$$W(0\mid0)=W(1\mid1)=0.8, \qquad W(?\mid0)=W(?\mid1)=0.2,$$

with $W(1\mid0)=W(0\mid1)=0$. For each fixed input $x$, summing over the three outputs gives one, consistent with the page’s output-row/input-column orientation. The identity encoder sends $x$ itself in one channel use. The decoder is

$$g(0)=0, \qquad g(1)=1, \qquad g(?)=0.$$

If $X=0$, both a received $0$ and an erasure decode to $0$, so the conditional error is zero. If $X=1$, an erasure is decoded incorrectly, so the conditional error is $0.2$. Therefore

$$P_{\mathrm e}^{\mathrm{avg}} = 0.7(0)+0.3(0.2) = 0.06,$$

and

$$P_{\mathrm e}^{\max} = \max\{0,0.2\} = 0.2.$$

The nominal uncoded rate is one source symbol per channel use, but that statement is meaningful only with the declared blocklength, decoder, source distribution, and error criterion.

2. Logarithm and support audit

For $P=(1,0)$ and $Q=(1/2,1/2)$, compute $H(P)$, $H(Q)$, $D(P\|Q)$, and $D(Q\|P)$ using base-$2$ logarithms.

Solution

Using $0\log_2 0=0$,

$$H(P) = -1\log_2 1-0\log_2 0 = 0,$$

whereas

$$H(Q) = -2\left(\frac12\log_2\frac12\right) = 1 \quad\text{bit}.$$

Only the first component contributes to $D(P\|Q)$:

$$D(P\|Q) = 1\log_2\frac{1}{1/2} = 1 \quad\text{bit}.$$

For the reverse divergence, $Q$ assigns positive probability $1/2$ to the second symbol while $P$ assigns it probability zero. The support condition therefore gives

$$D(Q\|P)=+\infty.$$

The last result is not obtained by treating division by zero informally; it follows from the extended-value definition when the support of the first distribution is not contained in the support of the second.

3. Exact dyadic prefix code

For symbol probabilities

$$p=\left(\frac12,\frac14,\frac18,\frac18\right),$$

consider the codewords $0$, $10$, $110$, and $111$. Verify prefix-freeness through the Kraft sum and compare the mean length with the entropy.

Solution

The codeword lengths are $(1,2,3,3)$. The Kraft sum is

$$2^{-1}+2^{-2}+2^{-3}+2^{-3} = \frac12+\frac14+\frac18+\frac18 = 1.$$

The displayed code is prefix free: no listed codeword is the beginning of another. Its mean length is

$$\begin{aligned} L &=\frac12(1)+\frac14(2)+\frac18(3)+\frac18(3)\\ &=\frac74\\ &=1.75 \quad\text{bits per symbol}. \end{aligned}$$

Because each probability is dyadic and $\ell_i=-\log_2p_i$, the entropy is

$$H(X) = \sum_i p_i\ell_i = 1.75 \quad\text{bits per symbol}.$$

Exact equality is possible here because the ideal lengths are integers satisfying Kraft equality. A general one-symbol distribution has noninteger ideal lengths and need not admit $L=H(X)$.

4. Three-fold repetition at finite blocklength

Send one message bit through three independent uses of a BSC with crossover probability $0.1$, and decode by majority vote. Compute the block error and code rate, then compare the result with uncoded transmission.

Solution

Majority decoding fails when exactly two or all three channel outputs flip. Independence gives

$$\begin{aligned} P_{\mathrm e} &=\binom32(0.1)^2(0.9)+(0.1)^3\\ &=3(0.01)(0.9)+0.001\\ &=0.028. \end{aligned}$$

One message bit uses three channel uses, so

$$R=\frac13 \quad\text{message bit per channel use}.$$

Uncoded transmission has error $0.1$ at rate one message bit per channel use. Repetition lowers the error to $0.028$ but also lowers the rate by a factor of three and increases latency. This one finite code does not establish capacity or an asymptotic optimum.

5. Cascaded BSC and data processing

Cascade BSCs with crossover probabilities $0.1$ and $0.2$. For a uniform input, compute the effective crossover and the mutual information before and after the second channel.

Solution

The final bit differs from the input exactly when one of the two channels flips and the other does not. Thus

$$\epsilon_{\mathrm{eff}} = 0.1(1-0.2)+(1-0.1)0.2 = 0.26.$$

For a uniform input to a BSC,

$$I=1-h_2(\epsilon).$$

After the first channel,

$$I(X{:}Y) = 1-h_2(0.1) = 0.531004406 \quad\text{bits}.$$

After the second channel,

$$I(X{:}Z) = 1-h_2(0.26) = 0.173253628 \quad\text{bits}.$$

The variables form the Markov chain $X\to Y\to Z$, and the numerical result explicitly satisfies

$$I(X{:}Z)\le I(X{:}Y).$$

The second channel has discarded information about $X$; it has not created a new observation of $X$.

6. Average versus maximal error

Three equiprobable messages have conditional decoding-error probabilities $(0,0,0.3)$. Compute the average and maximal errors. What is missing from a report that quotes only a “$10\%$ error rate”?

Solution

Equiprobable messages give

$$P_{\mathrm e}^{\mathrm{avg}} = \frac{0+0+0.3}{3} = 0.1.$$

The worst conditional error is

$$P_{\mathrm e}^{\max} = \max\{0,0,0.3\} = 0.3.$$

Thus “$10\%$ error” is accurate only if it is labeled as the average under the uniform message distribution. It hides a message whose failure probability is $30\%$. A requirement framed in maximal error would reject this code at a $10\%$ threshold.

7. Uniform but completely leaked key

Let $K$ be a uniform bit and let an adversary hold $E=K$. Compute $H(K)$ and the total-variation distance from the ideal independent distribution $U_KP_E$.

Solution

The marginal key distribution is uniform, so

$$H(K)=1 \quad\text{bit}.$$

The real joint distribution has

$$P_{KE}(0,0)=P_{KE}(1,1)=\frac12,$$

and zero probability on $(0,1)$ and $(1,0)$. Because $E$ is also marginally uniform, the ideal product distribution $U_KP_E$ assigns probability $1/4$ to each of the four pairs. Therefore

$$\begin{aligned} d_{\mathrm{TV}}(P_{KE},U_KP_E) &=\frac12\sum_{k,e} \left|P_{KE}(k,e)-\frac14\right|\\ &=\frac12\left(4\cdot\frac14\right)\\ &=\frac12. \end{aligned}$$

The key has maximal marginal entropy but is completely known to the adversary. Entropy and nominal length do not imply secrecy or independence; a protocol-level composable claim belongs with the QKD owner.

8. Repair an N-vector quantum-speedup claim

A proposal states, “The quantum algorithm processes an $N$-component vector exponentially faster.” Replace this with a matched classical-to-quantum comparator that could support or refute a precise advantage claim.

Solution

First specify the task and input. For example, decide whether both algorithms receive an explicit classical vector, sample access, an entry oracle, a prebuilt QRAM data structure, or an already prepared amplitude-encoded state. If a data structure or state must be constructed for this instance, include its loading, preprocessing, memory, and update cost on the side that uses it.

Next match the requested output. Producing the full $N$-component vector is not the same task as estimating one scalar, deciding a predicate, or drawing a sample. State the precision or loss, failure probability, confidence, and any promise on the inputs. Include state preparations, oracle calls, quantum gates, measurements, classical postprocessing, verification, and repetitions needed to meet that output contract.

The resulting ledger is

instance distribution and promise
  -> classical and quantum input representations
  -> matched access or oracle contract
  -> construction, loading, and preprocessing
  -> algorithm and requested output
  -> precision, error, success, and repetitions
  -> memory and total end-to-end cost

A separation in oracle queries can then be reported as a query-complexity result under that oracle. It is not automatically a separation in gate count, wall-clock time, energy, or application value. Formal class claims route to Quantum Complexity Classes, evidence calibration to Claims, executable accounting to Algorithmic Benchmarking, and a dated advantage verdict to Verification of Quantum Advantage.

References

• S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press (2009).
• T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley (2006).
• I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed., Cambridge University Press (2011).
• O. Goldreich, Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press (2001).
• D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press (2003).
• Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel Coding Rate in the Finite Blocklength Regime,” IEEE Transactions on Information Theory 56, 2307–2359 (2010), doi:10.1109/TIT.2010.2043769.
• C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 379–423 and 623–656 (1948), doi:10.1002/j.1538-7305.1948.tb01338.x.
• C. E. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal 28, 656–715 (1949), doi:10.1002/j.1538-7305.1949.tb00928.x.
• M. M. Wilde, Quantum Information Theory, 2nd ed., Cambridge University Press (2017), doi:10.1017/9781316809976.