Probability Amplitudes and Interference

Consider a register holding a single bit. Its possible distinguishable contents, \(0\) and \(1\), are its configurations (and for a \(k\)-bit register, the configurations are the \(2^k\) bit strings of length \(k\)). Whenever we inspect the register, we find it in exactly one configuration.

Before we inspect it, however, what do we know about the register at a given moment? We may have set the bit ourselves to \(0\), so that its configuration is known with certainty. We may know only that an unspecified choice occurred, leaving both \(0\) and \(1\) as live possibilities without saying how often either occurs. Or the bit may have been set by flipping a fair coin, so that \(0\) and \(1\) each carry probability \(1/2\). Whatever model we use, this complete specification of what is known about the register at a given time is its state.

All three kinds of knowledge take the exact same mathematical form: they assign a number \(v_j\)—called a weight—to each configuration \(j\). To keep each weight visibly paired with the configuration it describes, we write configuration \(j\) inside an angled bracket as \(\ket j\), read “ket \(j\),” and express the state as a weighted sum of these kets:

\[v_0\ket0+v_1\ket1.\]

At this stage, a ket sum is simply clean bookkeeping: each term \(v_j\ket j\) pairs configuration \(j\) with its weight \(v_j\). Terms for distinct configurations remain separate, while two terms for the same configuration combine by adding their weights, as in \(\tfrac14\ket0+\tfrac14\ket0=\tfrac12\ket0\).

Although the notation \(v_0\ket0+v_1\ket1\) looks the same in every row, the weights mean different things depending on the setting. In a possibility description, a weight of \(1\) or \(0\) simply records whether a configuration can occur; in a probability description, the weights are nonnegative numbers adding to \(1\) that record how frequently each configuration occurs. In any setting, a state that assigns weight \(1\) to one configuration and \(0\) to all others is called definite, and we write it simply as that configuration’s ket, such as \(\ket0\).

A computation changes the contents of a register step by step. A transition rule specifies which configurations may follow each current configuration in a single step. As a simple example, take the one-bit NOT operation, which flips \(0\) to \(1\) and \(1\) to \(0\).

We can picture any transition rule as a state diagram: we draw a circle for each configuration and an arrow \(i\to j\) whenever the rule allows configuration \(j\) to follow configuration \(i\). Each arrow carries a numerical weight. For a step named \(S\), we write the weight of the arrow from initial configuration \(i\) to final configuration \(j\) as

\[\bra jS\ket i,\]

with the final configuration on the left, the step in the middle, and the initial configuration on the right. We read this symbol from right to left, in the order the action happens: start in configuration \(i\), apply the step \(S\), and arrive at configuration \(j\). An arrow that is absent from the state diagram has weight \(0\). Writing \(X\) for the NOT operation, the two bit-flipping arrows carry weight one, \(\bra1X\ket0=\bra0X\ket1=1\), while the absent self-arrows carry weight zero, \(\bra0X\ket0=\bra1X\ket1=0\).

Applying a transition rule repeatedly generates a run \(c_0,c_1,c_2,\dots\), where \(c_t\) is the configuration after \(t\) steps; starting from \(c_0=0\), two steps of NOT produce the run \(0,1,0\). To visualize multi-step runs without arrows looping back over the same circles, we draw a time-expanded diagram: we copy the column of configurations once for each time \(t=0,1,2,\dots\) and connect consecutive columns using the arrows of the rule. Because every arrow moves forward from one time column to the next, a time-expanded diagram never contains a cycle, and a run of \(t\) steps appears simply as a directed path from time \(0\) to time \(t\).

Transition rules differ in how many arrows leave each configuration and in what their numerical weights represent. Those two differences separate the deterministic, nondeterministic, and probabilistic models that follow.

To see how arrow structure captures reversibility, compare the one-bit NOT operation with RESET, which writes \(0\) regardless of what the bit currently holds:

Starting from \(0\), two steps of NOT produce the run \(0,1,0\), whereas two steps of RESET produce \(0,0,0\). Under both rules, exactly one arrow leaves each configuration: for each starting configuration \(i\), a single successor \(j\) has weight \(\bra jS\ket i=1\) and all other outgoing weights are \(0\). Because there is no branching in the forward direction, the starting configuration determines the entire future run uniquely. Any rule with this property is deterministic: across any number of configurations and time steps, a definite initial configuration traces a single unbranched path to a unique final configuration, and the register remains in a definite state at every step.

Can we also trace a run backward in time? Forward determinism counts outgoing arrows; backward recovery counts incoming arrows. Under NOT, each configuration has exactly one incoming arrow, so knowing the present configuration always identifies the previous configuration uniquely. Under RESET, by contrast, two arrows enter \(0\) (from both \(0\) and \(1\)) and none enters \(1\), so a run that arrives at \(0\) has lost all record of which bit it started from. A deterministic rule in which every configuration also has exactly one incoming arrow is reversible.

A nondeterministic transition rule relaxes the requirement of a unique successor: a configuration may have several permitted outgoing arrows, so specifying the present configuration no longer singles out one inevitable future. Instead, the rule defines a set of permitted runs branching forward in time.

On a single bit, consider the rule KEEP-OR-FLIP, under which either \(0\) or \(1\) is permitted to follow either configuration. Its state diagram contains all four arrows (\(0\to0\), \(0\to1\), \(1\to0\), and \(1\to1\)). Starting from \(0\) at time \(0\), two steps admit four distinct paths in the time-expanded diagram:

\[0\to0\to0,\qquad0\to1\to0,\qquad0\to0\to1,\qquad0\to1\to1.\]

A multi-step path is possible when every transition along it is permitted by the rule, and a configuration is reachable at time \(t\) when at least one possible path from the start ends there. Under KEEP-OR-FLIP, both \(0\) and \(1\) are reachable after two steps. In a general multi-state, multi-step run, paths branch and reconverge across successive steps, and the reachable configurations at time \(t\) are simply those arrived at by at least one permitted path. In nondeterministic models of computation, acceptance is defined by the same existential test: an input is accepted if at least one permitted run reaches an accepting configuration.

Crucially, nondeterminism is a statement about logical possibility, not a physical mechanism for choosing randomly among paths. Even when an asymmetric rule admits more paths to one endpoint than to another, having more paths does not make that endpoint “more likely”—both endpoints are simply reachable. Counting possible paths and assigning outcome probabilities are distinct tasks; to predict how often each outcome occurs, we must attach quantitative probabilities to the arrows.

A probabilistic transition rule supplies the quantitative information that nondeterminism leaves unspecified: the probability of transitioning to each next configuration \(j\), given that the register is currently in configuration \(i\). The weight of the arrow \(i\to j\) under step \(S\) is now the conditional probability of \(j\) given \(i\), written \(P(j\mid i)\):

\[\bra jS\ket i=P(j\mid i).\]

Because probabilities are nonnegative and some next configuration must occur at each step, the weights leaving every configuration \(i\) are nonnegative numbers that add to one: \(\sum_j\bra jS\ket i=1\).

Writing the transition probability as \(P(j\mid i)\) assumes that the current configuration \(i\) contains all the information needed to predict the next step: once \(i\) is known, earlier history does not alter the probabilities of the outgoing arrows. (If earlier history did matter in a physical system, that history would have to be included as part of the configuration.) A stochastic process with this memoryless property is called Markov.

As our standard example on one bit, consider COIN: whatever value the bit currently holds, replace it with the result of a fresh fair coin flip. Its permitted arrows are the same four arrows as KEEP-OR-FLIP, but each arrow now carries probability \(1/2\), so \(\bra j{\mathrm{COIN}}\ket i=1/2\) for every \(i,j\in\{0,1\}\).

Now trace two steps of COIN starting from configuration \(0\). Along the path \(0\to1\to0\), the first step has probability \(1/2\), and the second step has conditional probability \(1/2\) given the intermediate configuration \(1\); multiplying them gives a path probability of \((1/2)(1/2)=1/4\). The alternative path to zero, \(0\to0\to0\), also has probability \(1/4\). Because these two paths are mutually exclusive histories, their probabilities add:

\[P(c_2=0)=\tfrac14+\tfrac14=\tfrac12,\]

where \(c_2\) denotes the configuration after two steps, and by the same reasoning \(P(c_2=1)=1/2\). Unlike a deterministic rule, COIN does not fix the outcome of an individual run; unlike a nondeterministic rule, it predicts the statistical distribution of outcomes over repeated runs—and applying COIN twice in a row leaves the bit completely random. Over any multi-state, multi-step sequence of transitions, conditional probabilities multiply along each path and add wherever paths reconverge at a final configuration.

A path in a time-expanded diagram specifies the exact configuration visited at every intermediate time step, so following that path requires taking every transition along it in sequence. Suppose a step \(S\) is followed by a step \(T\). The two-step path \(i\to j\to k\) uses the arrow from \(i\) to \(j\) under \(S\) and then the arrow from \(j\) to \(k\) under \(T\). According to the product rule, the weight of the path is the product of its individual arrow weights:

\[\bra kT\ket j\,\bra jS\ket i.\]

Read from right to left, the factors appear in the chronological order in which the steps act: the first step \(S\) stands immediately next to the initial configuration \(i\), and the second step \(T\) acts on the intermediate configuration \(j\). When the same rule acts at both steps, we simply set \(T=S\).

Notice how multiplication automatically enforces the logic of each model. For deterministic and nondeterministic rules, where every permitted arrow has weight \(1\) and every forbidden arrow has weight \(0\), the product equals \(1\) precisely when every transition along the path is permitted; a single forbidden transition anywhere along the route contributes a factor of \(0\) and eliminates the path.

For a probabilistic rule, where arrow weights are conditional probabilities, multiplying along the path gives the probability of that specific multi-step history. Crucially, the factors \(\bra jS\ket i\) and \(\bra kT\ket j\) are conditional probabilities for successive steps rather than probabilities of independent events: the Markov property guarantees that once the intermediate configuration \(j\) is given, the probability of the next transition \(j\to k\) depends only on \(j\) and not on earlier history.

For our fair-coin operation COIN, every arrow has weight \(1/2\), so each two-step path carries weight \((1/2)(1/2)=1/4\), and a path of \(t\) steps carries weight \(2^{-t}\). The product rule fixes the contribution of a single history; whenever several histories reach the same final configuration, we need a second rule to combine them.

Asking whether a run ends at configuration \(k\) specifies where the trajectory finishes without specifying which intermediate configurations it visited along the way. According to the sum rule, the total weight of transitioning from start \(i\) to endpoint \(k\) is the sum of the contributions of all paths that connect \(i\) to \(k\). Over two steps—first \(S\) and then \(T\)—the paths from \(i\) to \(k\) differ only in the intermediate configuration \(j\) visited at time \(1\), so their combined weight is

\[\bra kTS\ket i=\sum_j\bra kT\ket j\,\bra jS\ket i.\]

Each term in the sum accounts for one route \(i\to j\to k\) via the product rule, and summing over all \(j\) accounts for every possible route to \(k\). The left-hand side \(\bra kTS\ket i\) views the two-step sequence as a single composite step \(TS\) (with \(S\) applied first, on the right), whose effective arrow weight from \(i\) to \(k\) is this sum of path weights.

Under a deterministic rule, only one path from \(i\) is permitted, so the sum equals \(1\) at its unique endpoint and \(0\) everywhere else. Under a nondeterministic rule with \(0/1\) arrow weights, the sum counts how many permitted paths lead from \(i\) to \(k\); a positive count means that \(k\) is reachable, though the count itself is not a probability.

Under a probabilistic rule, paths that pass through different intermediate configurations \(j\) are mutually exclusive histories, so their probabilities add to give the two-step transition probability \(P_2(k\mid i)=\bra kSS\ket i\):

\[P_2(k\mid i)=\sum_jP(k\mid j)P(j\mid i).\]

For two steps of COIN from \(0\), this sum is \(1/4+1/4=1/2\) at both \(k=0\) and \(k=1\). Notice a decisive feature shared by all three classical models: every arrow weight—and therefore every path weight—is nonnegative. Opening an additional permitted path to an endpoint \(k\) can increase that endpoint’s total weight or leave it unchanged, but can never reduce it. This nonnegativity barrier is precisely what quantum transitions will overturn.

So far, each multi-step calculation has started from a single definite configuration. The exact same sum and product rules govern how a step \(S\) updates any general state \(\sum_iv_i\ket i\) that starts with weight \(v_i\) on each configuration \(i\).

In a single step under \(S\), starting at configuration \(i\) with weight \(v_i\) and following the arrow \(i\to j\) with weight \(\bra jS\ket i\) contributes the product \(\bra jS\ket i\,v_i\) to configuration \(j\). Summing these contributions over all starting configurations \(i\) gives the updated weight \(v^\prime_j\) at configuration \(j\):

\[v^\prime_j=\sum_i\bra jS\ket i\,v_i.\]

Ket notation turns this update into a straightforward algebraic substitution. First, a step \(S\) sends each definite configuration \(\ket i\) to the weighted sum of its successor configurations:

\[S\ket i=\sum_j\bra jS\ket i\,\ket j,\]

so that, for instance, \(\mathrm{COIN}\ket0=\tfrac12\ket0+\tfrac12\ket1\). Next, a general state \(\sum_iv_i\ket i\) updates to \(\sum_iv_i\,S\ket i\): each configuration’s successor sum is weighted by \(v_i\), and terms that land on the same configuration \(\ket j\) combine by adding their weights. Collecting the total weight on \(\ket j\) reproduces \(v^\prime_j\) automatically.

Updating the state step by step summarizes everything about the past that is needed to predict future steps, without keeping a separate list of all earlier paths. For COIN, any initial probability distribution \((v_0,v_1)\) with \(v_0+v_1=1\) updates in one step to \(v^\prime_0=v^\prime_1=(v_0+v_1)/2=1/2\): a single fair coin toss erases all trace of the initial state.

Whether a step can be undone depends on what this state update preserves. A reversible deterministic rule permutes the configurations one-to-one, so reversing its arrows restores every initial state. On two bits, where each configuration gets its own ket, CNOT acts by permuting \(\ket{10}\) and \(\ket{11}\): \(\mathrm{CNOT}\ket{00}=\ket{00}\), \(\mathrm{CNOT}\ket{01}=\ket{01}\), \(\mathrm{CNOT}\ket{10}=\ket{11}\), and \(\mathrm{CNOT}\ket{11}=\ket{10}\).

By contrast, both RESET and COIN map distinct initial states to the exact same final state, so no operation acting on that final state alone can recover which initial state prepared it. In fact, a probabilistic rule on finitely many configurations can be inverted by another probabilistic rule only if it is already deterministic and reversible—once a step spreads a definite state into a genuine probability distribution, nonnegative weights cannot re-concentrate it into a definite state without merging configurations.

Up to now, our weights have either counted permitted paths or represented probabilities, so they were always nonnegative. Let us keep the exact same state diagrams, time-expanded paths, and sum-and-product rules, but allow a configuration in a state or an arrow in a transition rule to carry a negative real weight. For the moment, treat this as a mathematical extension of our path bookkeeping; we will connect these weights to observable probabilities in Section 3.3.3.

Under the product rule, the weight of a path is still the product of its individual arrow weights. For a two-step path \(i\to j\to k\) under a step \(S\) applied twice, the path weight is

\[\bra kS\ket j\,\bra jS\ket i.\]

Because the factors are signed real numbers, their signs multiply along the path. A path with an odd number of negative arrow weights has a negative weight, whereas a path with an even number of negative arrow weights has a positive weight: for example, \((1/2)(-1/2)=-1/4\), while \((-1/2)(-1/2)=+1/4\). Traversing a second negative arrow therefore reverses the sign of a contribution that was already negative.

Similarly, when the starting configuration \(i\) itself carries an initial state weight \(v_i\), the contribution reaching \(k\) along the path \(i\to j\to k\) is \(\bra kS\ket j\,\bra jS\ket i\,v_i\), which incorporates the sign of \(v_i\) alongside the signs of the arrows.

A negative path weight is neither a negative probability nor a negative number of paths; it is a signed contribution to the sum at the path’s endpoint. The path itself remains present in the diagram, but its sign governs whether it reinforces or opposes other paths that meet at the same destination.

The sum rule still computes the total weight between a starting configuration \(i\) and an endpoint \(k\) by adding the contributions of all paths from \(i\) to \(k\). When a two-step run passes through two possible intermediate configurations \(j_1\) and \(j_2\), the combined weight is

\[\bra kSS\ket i=\bra kS\ket{j_1}\,\bra{j_1}S\ket i+\bra kS\ket{j_2}\,\bra{j_2}S\ket i.\]

Denote the arrow weights along the first route \(i\to j_1\to k\) by \(a,c\) and those along the second route \(i\to j_2\to k\) by \(b,d\). The two path contributions are \(ca\) and \(db\), giving a total weight of \(ca+db\) at \(k\). If \(a=b=c=1/2\) and \(d=-1/2\), then

\[\bra kSS\ket i=\frac14-\frac14=0.\]

Although both paths are permitted and each carries a nonzero weight of magnitude \(1/4\), their combined contribution at \(k\) vanishes completely. This offsetting of nonzero path contributions with opposite signs is cancellation. With nonnegative weights, a sum of path weights can vanish only when every individual path has weight zero; with signed weights, active paths can cancel one another out.

Cancellation can also be partial, as in \(1/4-1/8=1/8\), while contributions that share the same sign reinforce one another, as in \(1/4+1/4=1/2\) or \(-1/4-1/4=-1/2\). Because a path can bring a negative contribution, opening an extra path to an endpoint can now reduce its total weight, and blocking a negative path can increase it.

Crucially, only contributions arriving at the same final configuration are added together. A weight of \(+1/4\) at configuration \(0\) and a weight of \(-1/4\) at configuration \(1\) belong to distinct endpoints and remain separate components of the state. In ket notation, \(\tfrac14\ket0-\tfrac14\ket0=0\ket0\), whereas \(\tfrac14\ket0-\tfrac14\ket1\) retains both terms.

Consequently, the single-step update for state weights keeps the exact algebraic form established in Section 3.2.3:

\[v'_j=\sum_i\bra jS\ket i\,v_i.\]

Multiplication carries each signed contribution forward along its arrow, and addition combines the contributions that meet at each endpoint \(j\). Over a general multi-state, multi-step sequence of transitions, paths of the same sign reinforce one another while paths of opposite sign partially or completely cancel at the configurations where they reconverge. What remains is to see how a single operation can use cancellation to invert itself, and how signed weights relate to observable probabilities.

We can now use path cancellation to build a step \(H\) on one bit that spreads a definite input across both configurations, yet undoes itself when applied twice. Give three arrows of \(H\) the positive weight \(c\) and give the remaining arrow \(1\to1\) the opposite weight \(-c\):

\[\bra0H\ket0=\bra1H\ket0=\bra0H\ket1=c,\qquad \bra1H\ket1=-c.\]

Start at configuration \(0\) with weight \(1\). After one step, the state is \(H\ket0=c\ket0+c\ket1\). Over two steps from \(0\), the two paths returning to \(0\)—namely \(0\to0\to0\) and \(0\to1\to0\)—each contribute \(c\cdot c=c^2\), reinforcing to give \(2c^2\) at \(0\). Meanwhile, the two paths leading to \(1\)—namely \(0\to0\to1\) and \(0\to1\to1\)—contribute \(c^2\) and \((-c)c=-c^2\), which cancel to give \(0\) at \(1\).

To recover the original weight \(1\) at configuration \(0\) after two steps, we must set \(2c^2=1\), or \(c=1/\sqrt2\). This choice defines the Hadamard operation:

\[\bra0H\ket0=\bra1H\ket0=\bra0H\ket1=\tfrac1{\sqrt2},\qquad \bra1H\ket1=-\tfrac1{\sqrt2}.\]

In ket notation, applying \(H\) to each definite configuration gives

\[H\ket0=\frac{\ket0+\ket1}{\sqrt2},\qquad H\ket1=\frac{\ket0-\ket1}{\sqrt2}.\]

Each term on the right-hand side records one outgoing arrow from the input, weighted by \(\bra jH\ket i\). Notice that \(H\ket0\) and \(H\ket1\) differ only in the minus sign before \(\ket1\) in \(H\ket1\)—the direct signature of the negative self-loop \(\bra1H\ket1=-1/\sqrt2\).

Notice that the factor \(1/\sqrt2\) was fixed purely by composition: two applications must restore the starting weight. Starting from configuration \(1\) confirms the other half of the check: the two paths to \(0\) contribute \((1/\sqrt2)(1/\sqrt2)=1/2\) and \((1/\sqrt2)(-1/\sqrt2)=-1/2\), which cancel to \(0\), while the two paths to \(1\) contribute \(1/2\) and \((-1/\sqrt2)(-1/\sqrt2)=+1/2\), which reinforce to \(1\). Thus \(\bra kHH\ket i\) equals \(1\) when \(k=i\) and \(0\) otherwise: \(HH=I\), where \(I\) is the identity step whose only arrows are self-loops of weight \(1\) (\(\bra jI\ket i=1\) for \(j=i\) and \(0\) otherwise).

Now examine the weights after a single step of \(H\). Because the weights can be negative and need not add to \(1\), they cannot themselves be probabilities. Yet from either definite input, the squares of the outgoing weights are nonnegative and add to one:

\[c^2+c^2=c^2+(-c)^2=\tfrac12+\tfrac12=1.\]

Here each squared weight equals \(1/2\). This observation suggests associating the probability of observing each configuration with the square of its weight, while keeping the signed weights themselves to govern step-by-step composition and cancellation. This serves as a motivation for the quantum probability rule rather than a derivation of it; we will state the general rule for complex weights in the next section.

For a general input state \(v_0\ket0+v_1\ket1\), the single-step update under \(H\) is

\[H(v_0\ket0+v_1\ket1)=\frac{v_0+v_1}{\sqrt2}\ket0+\frac{v_0-v_1}{\sqrt2}\ket1,\]

and applying \(H\) a second time returns \(v_0\ket0+v_1\ket1\). Unlike COIN, the intermediate state after one Hadamard step preserves the full distinction between \(\ket0\) and \(\ket1\) in the relative sign of \(\ket1\), and that sign determines which endpoint cancels and which reinforces on the second step. If we replaced the negative arrow of \(H\) by \(+1/\sqrt2\), both \(\ket0\) and \(\ket1\) would map to the same state \((\ket0+\ket1)/\sqrt2\), destroying cancellation and making the step irreversible.

Negative real weights gave us a two-way choice of sign—plus or minus along the number line—and made self-inverse cancellation possible. What if we replace that two-way sign with a continuously varying direction in a plane?

The Hadamard operation satisfies \(H^2=I\), undoing itself in two steps. Can we instead construct a square root of NOT—an operation \(\sqrt X\) whose two-step composition flips the bit, \(\sqrt X\sqrt X=X\)? On a single bit, neither deterministic reversible operation has this property, since both the identity \(I\) and NOT (\(X\)) square to \(I\).

Let us look for a symmetric step \(\sqrt X\) with stay-weight \(a=\bra0\sqrt X\ket0=\bra1\sqrt X\ket1\) and switch-weight \(b=\bra1\sqrt X\ket0=\bra0\sqrt X\ket1\). Over two steps from either starting configuration, staying twice or switching twice returns to the initial configuration with combined weight \(a^2+b^2\), whereas staying then switching or switching then staying reaches the opposite configuration with combined weight \(ab+ba=2ab\). For the two-step operation to equal NOT, these path sums must satisfy

\[a^2+b^2=0,\qquad2ab=1.\]

If \(a\) and \(b\) are real numbers—even negative ones—their squares \(a^2\) and \(b^2\) are both nonnegative, so \(a^2+b^2=0\) forces \(a=b=0\), contradicting \(2ab=1\). Can a nonzero number have a negative square? Not on the real number line, but in the complex plane. Picture a complex number \(u+iv\) as the point (or arrow from the origin) \((u,v)\), and add two complex numbers by adding their arrows head to tail. Multiplying an arrow by the imaginary unit \(i\) rotates it counterclockwise by a quarter turn, since \(i(u+iv)=-v+iu\); two quarter turns make a half turn, which reverses every arrow and gives \(i^2=-1\). Because squares of complex numbers can point in opposite directions, they can cancel one another. Specifically, choose

\[a=\frac{1+i}{2},\qquad b=\frac{1-i}{2}.\]

Then \(a^2=i/2\), \(b^2=-i/2\) (so \(a^2+b^2=0\)), and \(2ab=1\). Applied twice, this step implements NOT exactly. Weights that may be complex numbers are called amplitudes, and they obey the exact same sum and product rules as real weights.

Having found complex amplitudes that compose to NOT, how do we connect them to outcome probabilities? For real weights, squaring produced a nonnegative number, but here the ordinary squares \(a^2=i/2\) and \(b^2=-i/2\) are imaginary. Multiplying a complex weight by its complex conjugate provides the natural generalization: for \(z=u+iv\), its conjugate is \(z^*=u-iv\), and their product is

\[zz^*=(u+iv)(u-iv)=u^2+v^2=|z|^2.\]

This nonnegative real quantity \(|z|^2\) is the squared magnitude of \(z\) (the squared length of its arrow in the plane), and it reduces to the ordinary square when \(z\) is real. We therefore propose the Born rule: a configuration with amplitude \(v_j\) is observed with probability

\[p(j)=v_jv_j^*=|v_j|^2.\]

To describe the direction of a complex amplitude geometrically, we write any nonzero amplitude \(z\) as an arrow of length \(r=|z|\) at an angle \(\phi\) counterclockwise from the positive real axis. Using Euler’s formula \(e^{i\phi}=\cos\phi+i\sin\phi\) for the unit arrow at angle \(\phi\), we have \(z=re^{i\phi}\), where \(r=|z|\) is the magnitude and \(\phi\) is the phase. By the trigonometric angle-addition formulas, multiplying two unit arrows adds their phases, \(e^{i\alpha}e^{i\beta}=\cos(\alpha+\beta)+i\sin(\alpha+\beta)=e^{i(\alpha+\beta)}\), whereas taking the probability \(|z|^2=r^2\) keeps the magnitude and discards the phase. Positive and negative real weights correspond to phases \(0\) and \(\pi\); complex amplitudes supply all the angles in between, allowing two states with identical outcome probabilities to evolve into different outcome probabilities on a subsequent step.

Under the probability rule \(p(j)=|v_j|^2\), the requirement that outcome probabilities across all configurations sum to one becomes a condition on the state’s amplitudes:

\[\sum_jp(j)=1\quad\Longleftrightarrow\quad\sum_j|v_j|^2=1.\]

This condition is called normalization. For the outgoing weights of \(\sqrt X\), we have \(|a|^2=(1/2)^2+(1/2)^2=1/2\) and \(|b|^2=(1/2)^2+(-1/2)^2=1/2\), which sum to \(1\), just as the Hadamard weights \(\pm1/\sqrt2\) give probabilities \(1/2\) and \(1/2\).

Along a single path, squared magnitudes multiply cleanly because \(|z_1z_2|^2=(z_1z_2)(z_1z_2)^*=|z_1|^2|z_2|^2\). When several paths meet at a common configuration, however, we add their complex amplitudes before taking the squared magnitude. For two path contributions \(A\) and \(B\), expanding \((A+B)(A^*+B^*)\) gives

\[|A+B|^2=|A|^2+|B|^2+AB^*+A^*B.\]

The cross terms \(AB^*+A^*B\) record how the two contributions reinforce or cancel. In two steps of \(\sqrt X\), the two return routes contribute \(A=i/2\) and \(B=-i/2\); their amplitude sum is \(A+B=0\), giving return probability \(|0|^2=0\), whereas adding their separate path probabilities \(|A|^2+|B|^2=1/4+1/4=1/2\) would miss the cancellation altogether.

Because interference raises the probability of some configurations and lowers the probability of others, what condition on a step \(S\) guarantees that total probability is conserved—remaining equal to \(1\)—for every normalized input state? For a step \(S\) on any number of configurations, updating \(v'_j=\sum_i\bra jS\ket i\,v_i\) and summing \(|v'_j|^2={v'_j}^*v'_j\) over all outputs \(j\) groups the terms into same-input terms (\(i=k\)) and distinct-input cross terms (\(i\ne k\)):

\[\sum_j|v'_j|^2=\sum_i|v_i|^2\sum_j|\bra jS\ket i|^2+\sum_{i\ne k}v_i^*v_k\sum_j\bigl(\bra jS\ket i\bigr)^*\bra jS\ket k.\]

Conserving total probability across all superpositions therefore requires two conditions on \(S\): the outgoing normalization condition,

\[\sum_j|\bra jS\ket i|^2=1,\]

and the cross-sum condition,

\[\sum_j\bigl(\bra jS\ket i\bigr)^*\bra jS\ket k=0\qquad(i\ne k).\]

Notice what the product \(\bigl(\bra jS\ket i\bigr)^*\bra jS\ket k\) inside these sums represents as a path. The factor \(\bra jS\ket k\) is the weight of the forward arrow \(k\to j\) in \(S\). In \(S\), the weight \(\bra jS\ket i\) belongs to the arrow \(i\to j\); if we form a second step by reversing every arrow of \(S\) (turning \(i\to j\) into \(j\to i\)) and taking the complex conjugate of its weight \(\bigl(\bra jS\ket i\bigr)^*\), then \(\bigl(\bra jS\ket i\bigr)^*\bra jS\ket k\) is the path product of the two-step route \(k\to j\to i\) that steps forward under \(S\) and steps back along the reversed, conjugated arrows.

On a single bit with outgoing weights \(a=\bra0S\ket0\), \(b=\bra1S\ket0\) from \(0\) and \(c=\bra0S\ket1\), \(d=\bra1S\ket1\) from \(1\), the figure shows both kinds of two-step paths:

First, for \(i=k\), the return paths start and end at the same configuration (\(0\to j\to0\) or \(1\to j\to1\)). By the outgoing normalization condition, the two return routes from \(0\) (\(0\xrightarrow{a}0\xrightarrow{a^*}0\) and \(0\xrightarrow{b}1\xrightarrow{b^*}0\)) sum to \(|a|^2+|b|^2=1\), and those from \(1\) sum to \(|c|^2+|d|^2=1\).

Second, for \(i\ne k\), the cross paths connect different configurations (\(0\to j\to1\) or \(1\to j\to0\)). Starting at \(0\) and ending at \(1\), one cross path passes through \(j=0\) with weight \(c^*a\) (\(0\xrightarrow{a}0\xrightarrow{c^*}1\)) and the other passes through \(j=1\) with weight \(d^*b\) (\(0\xrightarrow{b}1\xrightarrow{d^*}1\)). By the cross-sum condition, any constructive interference at \(j=0\) is balanced by destructive interference at \(j=1\), so the two cross paths between \(0\) and \(1\) cancel completely:

\[c^*a+d^*b=0\qquad\bigl(\text{and by conjugation }a^*c+b^*d=0\bigr).\]

Because the return paths \(i\to j\to i\) sum to \(1\) and the cross paths \(k\to j\to i\) (\(i\ne k\)) cancel to \(0\), conservation of probability automatically makes the step \(S\) reversible: following \(S\) with the step obtained by reversing every arrow and conjugating its weight undoes \(S\) completely, returning each configuration to itself with amplitude \(1\) and sending \(0\) to every other configuration.

Our step \(\sqrt X\) satisfies both conditions: its return paths sum to \(|a|^2+|b|^2=1/2+1/2=1\), and its cross paths between \(0\) and \(1\) cancel to

\[a^*b+b^*a=-\frac i2+\frac i2=0.\]

Whenever multiple paths terminate at the same configuration \(k\), we add their path amplitudes first and then take the squared magnitude:

\[p(k)=\Bigl|\sum_{\text{paths to }k}\text{path amplitude}\Bigr|^2.\]

Because amplitudes carry signs and phases, the paths meeting at \(k\) can reinforce or cancel. Across two Hadamard steps starting from \(0\), the two paths to \(0\) each contribute \(+1/2\), summing to \(1\) and yielding probability \(|1|^2=1\); the two paths to \(1\) contribute \(+1/2\) and \(-1/2\), canceling to \(0\) and yielding probability \(|0|^2=0\).

If we instead took the squared magnitude of each path separately and added those probabilities, both endpoints would receive \(1/4+1/4=1/2\). Adding the amplitudes before squaring raises the probability at one endpoint and lowers it at the other—an effect called interference. Interference is constructive when the resulting probability exceeds the sum of the separate squared magnitudes, and destructive when it is smaller. Paths whose amplitudes combine in this phase-sensitive way are called coherent.

For complex amplitudes, the phases of the contributing terms govern how they interfere. Suppose we multiply every amplitude in a state by the same phase factor \(e^{i\theta}\), rotating every arrow in the complex plane through the same angle \(\theta\). Every subsequent path product and endpoint sum simply acquires that same overall factor \(e^{i\theta}\), and because \(|e^{i\theta}|=1\), no outcome probability changes now or after any later transitions. Such a common phase factor across all configurations is called a global phase, and it has no observable effect.

By contrast, the phase difference between two amplitudes in a state (or between two competing paths) is their relative phase, and changing it directly alters how their amplitudes add. Consider the one-bit state

\[\frac{\ket0+e^{i\phi}\ket1}{\sqrt2}.\]

At this stage, \(0\) and \(1\) each have outcome probability \(|1/\sqrt2|^2=|e^{i\phi}/\sqrt2|^2=1/2\), regardless of \(\phi\). After a Hadamard step \(H\), however, the two contributions arriving at configuration \(0\) are \(1/2\) and \(e^{i\phi}/2\), whose sum depends on the relative phase \(\phi\):

\[p(0)=\left|\frac{1+e^{i\phi}}2\right|^2=\frac{1+\cos\phi}{2}.\]

At \(\phi=0\), the two contributions point in the same direction and interfere constructively to give \(p(0)=1\); at \(\phi=\pi\), they point in opposite directions and cancel completely to give \(p(0)=0\); at \(\phi=\pi/2\), they are perpendicular in the complex plane and give \(p(0)=1/2\). Even though all three initial states have identical outcome probabilities before \(H\), their relative phase determines the outcome probabilities after \(H\).

A simple gate that shifts relative phase is the phase-flip operation \(Z\), which leaves the amplitude at \(0\) unchanged (\(\bra0Z\ket0=1\)) and multiplies the amplitude at \(1\) by \(-1\) (\(\bra1Z\ket1=-1\)), with no arrows between \(0\) and \(1\). Applying \(Z\) adds \(\pi\) to the relative phase \(\phi\). Whereas two Hadamard steps from \(0\) return to \(0\) with certainty, inserting \(Z\) between them reverses the interference and produces \(1\) with certainty instead. Quantum algorithms deliberately introduce such phase shifts so that paths leading to wrong answers cancel while paths leading to desired answers reinforce.

Up to now, we have tracked a single working bit in isolation, where two Hadamard steps starting from \(0\) always return the bit to \(0\) because the two paths to \(1\) contribute \(+1/2\) and \(-1/2\) at the same configuration and cancel. In a multi-bit computation, however, intermediate steps often interact with other bits, such as temporary workspace. If information about which intermediate configuration (\(0\) or \(1\)) the working bit passed through is left imprinted on any outside bit, the expected interference on the working bit will not occur. Because a configuration of the machine specifies the values of all bits that participate in the run, leaving different values imprinted on an outside bit sends the paths to different complete configurations, preventing their amplitudes from combining and canceling.

To see this failure explicitly, adjoin a second bit initialized to \(0\) to serve as an outside record. A complete configuration of the two-bit system now carries a two-bit label \(ij\), where \(i\) is the value of the working bit and \(j\) is the value of the outside record bit. Crucially, \(10\) and \(11\) are distinct complete configurations even though the working bit is \(1\) in both. We apply our standard path rules—multiplying weights along each path, summing amplitudes that arrive at the same complete configuration, and taking squared magnitudes—to these two-bit configurations.

Starting from \(\ket{00}\), apply \(H\) to the working bit while leaving the outside bit unchanged, producing the state \((\ket{00}+\ket{10})/\sqrt2\). Next, suppose an intermediate operation imprints the working bit’s configuration onto the outside bit via a controlled-NOT (CNOT) gate with the working bit as control and the outside bit as target:

\[\mathrm{CNOT}\ket{00}=\ket{00},\quad\mathrm{CNOT}\ket{01}=\ket{01},\quad\mathrm{CNOT}\ket{10}=\ket{11},\quad\mathrm{CNOT}\ket{11}=\ket{10},\]

each with transition weight \(1\). Because the outside bit flips to \(1\) only along the branch where the working bit is \(1\), the state becomes \((\ket{00}+\ket{11})/\sqrt2\). Now apply the second \(H\) step to the working bit alone: from \(00\) it reaches \(00\) and \(10\) with weight \(+1/\sqrt2\) each, whereas from \(11\) it reaches \(01\) with weight \(+1/\sqrt2\) and \(11\) with weight \(-1/\sqrt2\).

Multiplying along the four branches gives the final state

\[\tfrac12\ket{00}+\tfrac12\ket{01}+\tfrac12\ket{10}-\tfrac12\ket{11}.\]

Instead of returning the working bit to \(0\) with certainty as expected, the second Hadamard step now leaves the working bit completely random. Look closely at the two branches where the working bit finishes in \(1\): their amplitudes are still \(+1/2\) and \(-1/2\), but because the outside bit retains different values on the two branches, those amplitudes land at two different complete configurations, \(10\) and \(11\). Because the sum rule only combines amplitudes at the exact same complete configuration, these two terms cannot cancel. Each of the four complete configurations has probability \(|\pm1/2|^2=1/4\), so the probability of finding the working bit in \(1\) is

\[p(\text{first label}=1)=p(10)+p(11)=\frac14+\frac14=\frac12.\]

Merely ignoring the outside bit at the end of the run does not merge \(10\) and \(11\) into one configuration. Whenever information distinguishing the intermediate paths is left imprinted on any outside bit, the paths terminate at different complete endpoints and the expected interference fails to occur—whether or not anyone ever inspects that outside bit.

To restore the expected behavior on the working bit, the computation must erase the imprint on the outside bit before the final \(H\) step acts. Because CNOT is its own inverse, applying a second CNOT immediately after the first sends \(00\) back to \(00\) and \(11\) back to \(10\), resetting the outside bit to \(0\) on both branches while keeping their amplitudes at \(1/\sqrt2\). With the outside bit back in the same state \(0\) along both routes, the final \(H\) again sends both branches to the same complete endpoints \(00\) and \(10\): the contributions \(+1/2\) and \(-1/2\) at \(10\) cancel to \(0\), while the two contributions at \(00\) reinforce to \(1\), restoring a certain return to \(00\).

This is why uncomputation—introduced in Section 2.4.3 to reset temporary workspace—is essential in quantum computation. In a classical reversible circuit, leftover values on workspace bits merely occupy memory; in a quantum circuit, any intermediate information left imprinted on outside workspace bits splits the endpoints of interfering paths and prevents the expected output from occurring. Uncomputation actively reverses the gates that created those outside imprints before interference takes place. In Chapter 4, we express these weighted sums of kets as complex vectors and state the general postulates for quantum states, evolution, measurement, and composite systems.