Saturday, 21 November 2026

Why Can't We Know Everything About a Quantum Coin?

Always heads on this axis,
therefore equally likely 
on the perpendicular axis
Suppose we prepare a quantum coin that always gives Heads when measured vertically.

We know its vertical measurement outcome with certainty.

But what happens if we measure it horizontally?

The result is 50% Heads and 50% Tails.

Always heads on the perpendicular axis,
therefore equally likely
on this axis
Now prepare a different coin that always gives Heads when measured horizontally.

This time, its vertical measurement outcomes are equally likely.

In other words:

Knowing the outcome with certainty in one direction means maximum uncertainty in the perpendicular direction.

This illustrates a fundamental feature of quantum mechanics: complementarity.

The vertical and horizontal measurements describe different properties of the quantum system.

They cannot both have perfectly definite outcomes in the same quantum state.

This is an example of the Heisenberg uncertainty principle - the same broad principle underlying the famous uncertainty relationship between position and momentum.

Importantly, the uncertainty isn't caused by faulty equipment, nor is it simply the result of disturbing the coin while measuring it.

It is inherent in the quantum state itself.

Our clocks help explain why.

When one clock hand has length 1 and the other length 0, vertical measurement is certain. But when we combine those amplitudes to calculate horizontal outcomes, they become equal in magnitude.

Conversely, two equal-length clock hands pointing in the same direction produce a definite horizontal outcome, but equal probabilities vertically.

Neither measurement direction is inherently preferred.

And no clock hands need to move for any of this to happen.

What have we discovered?

Our quantum coin and two stationary clocks have introduced the essential ideas of quantum mechanics:

Superposition: A state can combine multiple measurement possibilities.

Probability amplitudes: Complex numbers describe the quantum state.

Phase: The directions of amplitudes matter, not just their magnitudes.

Interference: Amplitudes can reinforce or cancel.

Measurement: Different measurement directions reveal different properties.

Uncertainty: Complementary properties cannot both have perfectly definite outcomes.

The central insight is remarkably simple:

Quantum mechanics describes probability amplitudes, not merely probabilities.

And much of what makes quantum mechanics surprising follows from how those amplitudes combine when we measure a system in different ways.

Friday, 20 November 2026

How Can Two 50/50 Coins Give Opposite Results?

Coin A: Always heads on the horizontal axis
Coin B: Always tails on the horizontal axis

Adding and subtracting amplitudes creates interference
Previously, we prepared two quantum coins.

Coin A had two clock hands pointing in the same direction.

Coin B had two clock hands pointing in opposite directions.

Both gave 50% Heads and 50% Tails when measured vertically.

Now let's measure them horizontally.

Something remarkable happens.

Coin A always gives Heads when measured horizontally.

Coin B always gives Tails when measured horizontally.

How can changing the measurement direction make such a difference?

The answer is quantum interference.

Let's call the two original clock amplitudes a and b. To calculate the horizontal measurement probabilities, we combine them:

Horizontal Heads amplitude = (a + b)/√2

Horizontal Tails amplitude = (a − b)/√2

For Coin A, the amplitudes point in the same direction (→ and →). Adding them reinforces them, while subtracting them cancels them.

With a = 1/√2 and b = 1/√2, Heads = (1/√2 + 1/√2)/√2 = 1 and Tails = (1/√2 - 1/√2)/√2 = 0.

For Coin B, the amplitudes point in opposite directions (→ and ←). Adding them cancels them, while subtracting them reinforces them.

With a = 1/√2 and b = -1/√2, Heads = (1/√2 + -1/√2)/√2 = 0 and Tails = (1/√2 - -1/√2)/√2 = 1.

This produces completely opposite horizontal measurement outcomes.

The key is that quantum mechanics combines amplitudes before calculating probabilities.

Ordinary probabilities don't contain the relative-phase information needed to explain this interference.

Mathematically, expressing the amplitudes in the horizontal rather than vertical basis involves the Hadamard transform, a two-point Fourier transform.

The physical state hasn't changed merely because we've changed its mathematical description. But measuring horizontally asks a different physical question.

And neither measurement direction is preferred.

A coin that is perfectly predictable horizontally can be completely unpredictable vertically.

Which raises another puzzle:

Could a quantum coin be perfectly predictable in both directions?

Next: The quantum uncertainty principle.

Thursday, 19 November 2026

Can Two Identical-Looking Quantum Coins Be Different?

Coin A: 0° relative phase (on the vertical axis)
Imagine preparing two quantum coins, A and B.

Each has two clocks representing its Heads and Tails amplitudes for a vertical measurement.

Both clock hands have equal length, giving a 50% probability of Heads and a 50% probability of Tails.

Coin B: 180° relative phase (on the vertical axis)

Coins A and B have the same probabilities,
but a different relative phase.
But there's one difference.

Coin A: Both clock hands point right.

Coin B: Heads points right, while Tails points left.

If we measure either coin vertically, we get exactly the same probabilities.

So are they really different?

Yes!

If two coins give the exact same odds every time you flip them, it's tempting to say the difference is meaningless. In classical physics, it would be.

The direction of a clock hand represents the phase of its amplitude.

Coin A has a relative phase of 0° between its two amplitudes.

Coin B has a relative phase of 180°.

These are different quantum states, even though their vertical measurement probabilities are identical.

In quantum mechanics, probability amplitudes are complex numbers. They have both a magnitude and a phase.

Importantly, it is the relative phase that matters. Rotating both clock hands by the same angle changes neither coin's measurement probabilities.

There's another subtlety: these clock-hand angles are mathematical angles, not the physical direction in which we measure the coin.

The vertical measurement tells us about the lengths of the clock hands but cannot distinguish these two preparations.

So how could we detect the difference?

What if we measured the coins horizontally instead?

Next: The surprising power of quantum interference.

Wednesday, 18 November 2026

How Can Two Clocks Describe a Quantum Coin?

Figure 1: Always heads (on the vertical axis)
Probability = (clock-hand length)2
An ordinary coin has probabilities. A quantum coin has something more exotic: probability amplitudes.

To understand these, imagine two clocks, each with a single hand.

Neither clock is running. The hands remain stationary.

One clock represents the amplitude for Heads and the other represents the amplitude for Tails, when measuring vertically.

Each hand has two properties:

Length determines the probability of its outcome. The probability is the square of the hand's length.

Direction represents its phase, which we will explore later.

Suppose the Heads clock has a hand of length 1 while the Tails clock has no hand (length 0), as illustrated in Figure 1. The probabilities are:

P(Heads) = 1² = 100%

P(Tails) = 0² = 0%

Figure 2: Equal superposition of heads and tails (on the horizontal axis)
Probability = (clock-hand length)2
Now suppose both hands have a length of 1/√2, as illustrated in Figure 2. The probabilities become:

P(Heads) = (1/√2)² = 50%

P(Tails) = (1/√2)² = 50%

This is an example of superposition: the quantum state combines amplitudes for both possible outcomes.

If we translate those two clocks into standard quantum notation, it looks like this:

|ψ⟩ = a|H⟩ + b|T⟩

Here, a and b represent the two clock hands.

In quantum computing, this two-state system is a qubit (quantum bit) - just as an ordinary coin with two outcomes is analogous to a classical bit (0 or 1).

Standard quantum computing notation simply labels Heads and Tails as |0⟩ and |1⟩ instead:

|ψ⟩ = a|0⟩ + b|1⟩

Together, the two clocks describe a single quantum coin (|ψ⟩), combining its Heads and Tails components relative to our chosen measurement direction.

But why do the hands have directions as well as lengths?

Can two coins have identical probabilities but different quantum states?

Next: The mystery of the clock hands.

Tuesday, 17 November 2026

Visualizing a quantum coin

A quantum coin. It is valid to measure the coin along any axis.
Most introductions to quantum mechanics (and quantum computing) jump straight into complex numbers and mathematical symbols, which make simple ideas feel harder than they are. In this short series of posts I will explain key quantum concepts using familiar objects.

Imagine a special coin, a quantum coin, that behaves a little differently from an ordinary coin.

We have a device that enables us to measure a quantum coin along a chosen axis: vertical, horizontal, depth-wise or, indeed, any arbitrary direction. The result of the measurement will be either Heads or Tails, just like a regular coin.

This may seem strange. But it's analogous to a real quantum experiment in which we measure an electron's spin along different axes - the physical basis for a qubit, the fundamental building block of a quantum computer.

Our imaginary coin simply makes the idea more familiar. Now for a puzzle.

Suppose we prepare a quantum coin and measure it along the vertical axis many times, preparing it identically for each experiment.

We find that Heads and Tails are equally likely: 50% each.

Does this mean the coin is fundamentally random?

Not necessarily!

When we measure identically prepared coins along the horizontal axis instead, we might find that every single measurement gives Heads.

The coin is completely unpredictable in one direction but perfectly predictable in another.

How can that be?

To understand the answer, we'll need two clocks.

Next: How can two clocks describe a quantum coin?

Monday, 17 November 2025

Modeling simple quantum systems

Figure 1: A two-state system (qubit)
In this post I'll model some simple systems using the equations of quantum mechanics, culminating in the qubit (illustrated in Figure 1) - the building-block of quantum computing.[1]

The time evolution of a quantum system, where the unitary operator \(U\) transforms the state of the system at time \(0\) to time \(t\), is defined as:

\[\psi(t) = U(t)\psi(0) \tag{1} \]

Operator \(U\), where the Hamiltonian \(H\) encodes the system's energy levels (spectrum), is defined as:[2]

\[U(t) = e^{−iHt} \tag{2} \]

Time evolution intuition: Time evolution is phase accumulation: in the energy basis, each component of \(\psi\) picks up a phase \(e^{-iE_k t}\). For each component, visualize a clock hand (or arrow) that spins at a rate set by its energy.

Differentiating and using \(\frac{d}{dt}U(t) = -iHU(t)\) gives the Schrödinger equation:[3]

\[i \frac{d}{dt}\psi(t) = H \psi(t) \tag{3} \]

Schrödinger equation intuition: Visualize each energy component of \(\psi(t)\) as a clock hand rotating on the complex plane. Its time derivative is the tangent to that rotating clock hand (i.e., the clock hand rotated 90° clockwise and scaled by its energy). Multiplying by \(i\) rotates that tangent back to the radial direction. In the energy basis, applying \(H\) to \(\psi(t)\) simply scales each energy component by its corresponding energy level. Thus \(i \frac{d}{dt}\psi(t)\) (tangent rotated back) and \(H \psi(t)\) (component-wise scaling) are the same vector, giving the Schrödinger equation.

A trivial one-state system (no phase change)


Consider a particle with a frequency of 0Hz. Set \(H=0\) and \(\psi(0)=1\). Then

\[\psi(t)=e^{-i\cdot 0\cdot t}\cdot 1 = 1 \]

for all \(t\) (as illustrated in Figure 2). For a one-state system, there is only one possible measurement outcome, namely, that single state.

Figure 2: \(\psi(t) = 1\) (0Hz)
horizontal-axis: time | lateral axes: complex amplitude

0Hz system intuition: We are, in effect, modeling a clock whose hand does not rotate (0Hz). Hence the graph shows the amplitude fixed in its initial phase over time. Note, however, that we cannot subsequently measure the angle (phase) of the clock hand, or even its frequency (more on this below).

A one-state system with a 1Hz phase (global phase change only)


Now consider a particle with a frequency of 1Hz. Set \(H = \theta\) and \(\psi(0)=1\). Then

\[\psi(t)=e^{-i\cdot \theta \cdot t} \cdot 1 = e^{-i\cdot \theta \cdot t} \]

where \(\theta\) is a scalar.

Figure 3: \(\psi(t) = e^{-i\cdot\tau\cdot t}\) (1Hz)

The amplitudes at selected times per Figure 3 for \(\theta = \tau\) (where \(\theta\) is the energy eigenvalue and \(\tau \equiv 2\pi\), representing the radians in one cycle):

\[t=0,1: 1, \quad t=0.25: -i,\]
\[t=0.5: -1, \quad t=0.75: i.\]


As noted before: for a one-state system, there is only one possible measurement outcome, namely, that single state. Since the global phase (including both the degree of rotation around the complex plane and its rate of change) is unobservable in quantum systems, this system is indistinguishable from the earlier 0Hz system. The different oscillations become relevant for multi-state systems which we will consider next.

1Hz system intuition: Now we're modeling a clock whose hand rotates once per second (1Hz). Hence the graph shows the amplitude rotating in a unit circle from 1 through -i, -1 and i back to 1. This is visualized as a corkscrew along the time axis. As noted earlier, we cannot measure the angle of the clock hand or its frequency. Only relative phase (between two or more clocks) can be measured. Each clock is, in effect, enclosed in its own black box with no way to experimentally distinguish them.

A superposed two-state system (qubit)


Now consider a two-dimensional Hilbert space comprising a ground state (with \(0\) energy) and an excited state (with \(\tau\) energy) in equal superposition.[4][5] For example, a spin-½ particle with up (0Hz ground) and down (1Hz excited) states.

Hilbert space intuition: Consider the familiar 2D Euclidean plane that represent lengths in an x and y direction, and also angles and magnitude. A 2D Hilbert space allows the x and y coordinates to be complex numbers. This retains the familiar geometry but adds structure for phases and interference. A vector in a 2D Hilbert space (i.e., a qubit) can be visualized as a point on the surface of a Bloch sphere where the latitude represents proximity to the poles (0 and 1) and the longitude represents the relative phase between them.

Energy basis \(\{|E_0\rangle,|E_1\rangle\}\) with

\[H_{energy} = \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix}, \quad \psi_{energy}(0) = \dfrac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \]

Time evolution:

\[\begin{align}\psi_{energy}(t) &= U_{energy}(t)\psi_{energy}(0) \\ &= e^{−iH_{energy}t} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 0 \\ 0 & e^{−i \tau t}\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 \\ e^{−i \tau t}\end{bmatrix} \end{align} \]

Figure 4: \(|\psi_{energy}(t)⟩ = \frac{1}{\sqrt2}(|E_0⟩ + e^{-i \tau t}|E_1⟩)\) (0Hz+1Hz)

The (superposed) amplitudes at selected times per Figure 4:

\[t=0,1: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}, \quad t=0.25: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\-i\end{bmatrix},\]
\[t=0.5: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix}, \quad t=0.75: \dfrac{1}{\sqrt2}\begin{bmatrix}1\\i\end{bmatrix}.\]

These amplitudes are the linear combination of the amplitudes for the one-state systems in Figures 2 and 3 (normalized such that the square of the magnitudes equals 1). 

Vector intuition: The vectors have two elements, associated with the two component states. Since the magnitude of the individual amplitudes for each state are \(\tfrac{1}{\sqrt2}\) at all points, the probability of measuring a particular state is \(\tfrac{1}{2}\) (per the Born rule, \((\tfrac{1}{\sqrt2})^2\)).

Born rule intuition: The two states can be represented as the adjacent and opposite sides of a right-angled triangle, with the hypotenuse of unit length \(1\). Per the Pythagorean Theorem, if the magnitudes of the two states are \(0.6\) and \(0.8\), then the probability of measuring those states per the Born rule is \(0.6^2  = 0.36\) and \(0.8^2 = 0.64\) respectively (with \(0.36 + 0.64  = 1\)). In the main qubit example, the triangle side lengths are each \(\tfrac{1}{\sqrt2}\) whose squares are each \(\tfrac{1}{2}\) (summing to 1). A measurement is a projection onto one of the sides per the Born probabilities. Thus, in the main qubit example, there is an equal probability of measuring either state (i.e., 0Hz or 1Hz, ground or excited, 0 or 1).

Time (Hadamard/DFT-2) basis. Define \(|T_0\rangle, |T_1\rangle\) via the Hadamard:

\[\begin{align}\psi_{time}(t) &= \mathcal{F}^{-1} \psi_{energy}(t) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2}\begin{bmatrix} 1 \\ e^{−i \tau t} \end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]


Figure 5: \(|\psi_{time}(t)⟩ = \frac{1}{2}(1 + e^{-i \tau t})|T_0⟩ + \frac{1}{2}(1 - e^{-i \tau t})|T_1⟩ \)

The (superposed) amplitudes at selected times per Figure 5:[6]

\[t=0,1: \begin{bmatrix}1\\0\end{bmatrix}, \quad t=0.25: \dfrac{1}{2} \begin{bmatrix}1 - i\\1 + i\end{bmatrix},\]
\[t=0.5: \begin{bmatrix}0\\1\end{bmatrix}, \quad t=0.75: \dfrac{1}{2} \begin{bmatrix}1 + i\\1 - i\end{bmatrix}.\]

A measurement in the time basis (with eigenstates \(|T_0\rangle, |T_1\rangle\)) at physical time \(t=0\) would return the eigenstate \(|T_0\rangle\) (i.e., the spin-½ particle ground state in the time basis) with certainty and at physical time \(t=0.25\) would return either eigenstate with equal probability.

Qubit intuition: The two independent clocks discussed earlier can be superposed in a single two-state system (a qubit). A measurement projects onto just one of the clocks (0Hz or 1Hz, ground or excited, 0 or 1). In the standard (energy) basis, the two clocks are modeled per Figure 4, with the measurement of either 0Hz or 1Hz being equally likely at any point in time. In the Fourier (time) basis, the relative phase between the two clocks are modeled per Figure 5, with the probability of measuring either T0 or T1 (which is + or -, in-phase or out-of-phase, 0 or 1) being dependent on the time of measurement.

Relative phase intuition: In Figure 4, the straight bright purple line models the 0Hz stopped clock hand whereas the curved dim purple line models the 1Hz moving clock hand. In Figure 5, the bright green line models how correlated the two clock hands are (how in-phase they are, i.e., the phase difference) while the dim green line models how anti-correlated the two clock hands are (how out-of-phase they are). So at t=0, the two hands point in the same direction, while at t=0.5, the two hands point in the opposite direction. Note that the purple lines don't exhibit interference since just the stopped clock or the moving clock state is measured (but, to reiterate, not its phase). This is analogous to measuring a particle at just one of the slits in the double-slit experiment. However the green lines are each interference patterns since they represent the phase between both clock hands. Remove one of the clocks and the interference pattern disappears.

Wrapping up


We started with the basic rule for how quantum systems change over time and built up from the simplest case: a system that never changes to one that oscillates and then to a two-state system (a qubit). An energy level is analogous to a tiny clock hand spinning at its own speed. With just one clock, nothing interesting happens, but with two clocks spinning at different rates, their positions combine to create interference patterns. These two-clock systems, or qubits, are the building blocks of quantum computing.


Related posts







Footnotes


[1] Units, \(\tau\), and representations


Using Planck units with \(\hbar=1\) and representing the radians in one cycle with \(\tau\equiv 2\pi\), then

\[h=\tau,\qquad E=hf=\tau f = \omega,\]

referencing Planck's constant (\(h\)), energy (\(E\)), frequency (\(f\)) and angular frequency (\(\omega\)).

A quantum state is a complex wavefunction written here either in the energy basis or in a convenient “time (Fourier)” basis. In a one-state system these coincide (so any Heisenberg trade-off is vacuous). In finite-dimensional quantum systems, a “time basis” is not the eigenbasis of a fundamental time operator. It is a complementary basis obtained by a unitary transformation (Hadamard/DFT in 2D). Such systems satisfy SU(2) (spin-½) commutation relations, e.g.  \([Sx​,Sy​]=iSz\), but not canonical commutation, such as \([E,T]=iI\). Here, \(Sx\) corresponds to energy, \(Sy\) to time and \(Sz\) to the relative phase between energy and time.


[2] Exponentiating the Hamiltonian


The Hamiltonian \(H\) is a diagonal matrix that encodes the system's energy levels \(E_k\) along the diagonal. For a one-state system, it reduces to a scalar.

One-state system. With \(E_f=\tau f\) (the energy at a specific frequency),

\[H=E_f,\qquad U(t)=e^{-iHt}=e^{-iE_f t}.\]

Two-state system. With energy basis \(\{|E_0\rangle,|E_1\rangle\}\)),

\[H=\begin{bmatrix}E_0&0\\[2pt]0&E_1\end{bmatrix},\qquad U(t)=e^{-iHt}=\begin{bmatrix}e^{-iE_0 t}&0\\[2pt]0&e^{-iE_1 t}\end{bmatrix}.\]

Eigen/evolution relations (operator form):

\[H|E_n\rangle=E_n|E_n\rangle,\qquad U(t)|E_n\rangle=e^{-iE_n t}|E_n\rangle\quad(n=0,1).\]

[3] Deriving the Schrödinger equation


Starting from \(\psi(t)=U(t)\psi(0)\) with \(U(t)=e^{-iHt}\) and time-independent \(H\),

\[\begin{align}i \frac{d}{dt}\psi(t) &= i \frac{d}{dt}e^{−iHt}\psi(0) \\ &= i \cdot -iH e^{−iHt}\psi(0) \\ &= H \psi(t). \end{align} \]

[4] Transforming between the time and energy representations


The time and energy representations of a quantum system are related via a unitary Fourier transform:

\[\psi_{energy} = \mathcal{F} \psi_{time} , \quad \psi_{time} = \mathcal{F}^{-1} \psi_{energy} .\]

One-state system: the Identity matrix,

\[\mathcal{F}_1 = \mathcal{F}_1^{-1} = \begin{bmatrix}1\end{bmatrix} . \]

Two-state system: the Hadamard/DFT-2,

\[\mathcal{F}_2 = \mathcal{F}_2^{-1} = \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} . \]

[5] Energy and time bases


In the two-state system with \(\hbar=1\) and \(\tau\equiv 2\pi\) we set

\[ H_{\text{energy}}=\begin{bmatrix}0&0\\[2pt]0&\tau\end{bmatrix}.\]

So \(|E_0\rangle, |E_1\rangle\) satisfy

\[H_{\text{energy}}|E_0\rangle=0\,|E_0\rangle,\qquad H_{\text{energy}}|E_1\rangle=\tau\,|E_1\rangle,\]

and, in the energy basis coordinates,

\[|E_0\rangle = \begin{bmatrix}1\\0\end{bmatrix},\qquad |E_1\rangle = \begin{bmatrix}0\\1\end{bmatrix}.\]

We also define the time (Hadamard/DFT-2) basis by
\[|T_0\rangle=\frac{1}{\sqrt2}(|E_0\rangle+|E_1\rangle)=\frac{1}{\sqrt2}\begin{bmatrix}1\\[2pt]1\end{bmatrix},\qquad |T_1\rangle=\frac{1}{\sqrt2}(|E_0\rangle-|E_1\rangle)=\frac{1}{\sqrt2}\begin{bmatrix}1\\[2pt]-1\end{bmatrix}.\]

[6] Transform-then-evolve (and other alternatives)


A second method for calculating \( \psi_{time}(t) \) is to transform \(H_{energy} \) and \(\psi_{energy}(0)\) to the time basis first and then evolve the state.

\[\begin{align}H_{time} &= \mathcal{F}^{-1} H_{energy} \mathcal{F} \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \\ &= \begin{bmatrix}\pi & -\pi\\-\pi & \pi\end{bmatrix} \end{align} \]

\[\begin{align}\psi_{time}(0) &= \mathcal{F}^{-1} \psi_{energy}(0) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix} \\ &= \begin{bmatrix}1\\0\end{bmatrix} \end{align} \]

\[\begin{align}\psi_{time}(t) &= U_{time}(t)\psi_{time}(0) \\ &= e^{−iH_{time}t} \begin{bmatrix}1\\0\end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix}1 + e^{−i \tau t} & 1 - e^{−i \tau t} \\ 1 - e^{−i \tau t} & 1 + e^{−i \tau t}\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]

A third method for calculating \( \psi_{time}(t) \) is via the Schrödinger equation.

\[i \frac{d}{dt}\psi(t) = H \psi(t), \quad H_{energy} = \begin{bmatrix}0 & 0\\0 & \tau\end{bmatrix}, \quad \psi_{energy}(0) = \dfrac{1}{\sqrt2} \begin{bmatrix}1\\1\end{bmatrix}.\]

Because the Hamiltonian is diagonal, the Schrödinger equation decouples into independent equations for each component. For the first component:

\[ i \frac{d}{dt}\psi_0(t) = 0 \cdot \psi_0(t) = 0 \]

\[ \frac{d}{dt}\psi_0(t) = 0 \implies \psi_0(t) = \psi_0(0) = \frac{1}{\sqrt2} \]

For the second component:

\[ i \frac{d}{dt}\psi_1(t) = \tau \cdot \psi_1(t) \]

\[\psi_1(t) = \psi_1(0) e^{−i \tau t} = \frac{1}{\sqrt2} e^{−i \tau t}\]

Therefore, the solution in the energy basis is:

\[\psi_{energy}(t) = \frac{1}{\sqrt2} \begin{bmatrix}\psi_0(t) \\ \psi_1(t) \end{bmatrix} = \frac{1}{\sqrt2} \begin{bmatrix}1 \\ e^{−i \tau t}\end{bmatrix}\]

Finally, transform \(\psi_{energy}(t)\) to the time basis:

\[\begin{align}\psi_{time}(t) &= \mathcal{F}^{-1} \psi_{energy}(t) \\ &= \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} \frac{1}{\sqrt2}\begin{bmatrix} 1 \\ e^{−i \tau t} \end{bmatrix} \\ &= \frac{1}{2}\begin{bmatrix}1 + e^{−i \tau t} \\ 1 - e^{−i \tau t}\end{bmatrix} \end{align} \]

Sunday, 21 April 2024

Fast (Fourier) multiplication

Figure 1: Representing the numbers 12 and 345 as frequency spectra,
 transforming them to time signals and multiplying.
One consequence of being able to convert between time signal and frequency spectrum representations is that they can be applied to the multiplication of multi-digit numbers in a way that is both straightforward and (potentially) quicker.

Consider the process of multiplying \(12\) by \(345\). I've fully expanded the intermediate steps with the colors representing the one's, ten's, hundred's and thousand's columns.
\[\begin{array}{r} 12\\ × \enspace 345\\ \hline \color{green}{10}\\ \color{red}{5}\enspace\\ _1 \color{red}{8}\enspace\\ \color{blue}{4}\enspace\enspace\\ _1 \color{blue}{6}\enspace\enspace\\ \color{goldenrod}{3}\enspace\enspace\enspace\\ \hline 4140 \end{array}\]
This operation is similarly represented in the following table where each number is separated into its digits and independently multiplied.

\( \begin{array}{|c|c|c|} \hline & & \color{gray}{10^1} & \color{gray}{10^0} \\ \hline & × & 1 & 2 \\ \hline \color{gray}{10^2} & 3 & \color{goldenrod}{3} & \color{blue}{6} \\ \hline \color{gray}{10^1} & 4 & \color{blue}{4} & \color{red}{8} \\ \hline \color{gray}{10^0} & 5 & \color{red}{5} & \color{green}{10} \\ \hline \end{array} \)

Calculating this, we get:

\(\begin{aligned}12 \cdot 345 & = (1  \!\cdot\!  {\color{gray}{10^1}} + 2  \!\cdot\!  {\color{gray}{10^0}})  \!\cdot\!  (3  \!\cdot\!  {\color{gray}{10^2}} + 4  \!\cdot\!  {\color{gray}{10^1}} + 5  \!\cdot\!  {\color{gray}{10^0}}) \\ & = 1  \!\cdot\!  {\color{gray}{10^1}}  \!\cdot\!  3  \!\cdot\!  {\color{gray}{10^2}} + 2  \!\cdot\!  {\color{gray}{10^0}}  \!\cdot\!  3  \!\cdot\!  {\color{gray}{10^2}} \, + \\ & \hspace{1.25em} 1  \!\cdot\!  {\color{gray}{10^1}}  \!\cdot\!  4  \!\cdot\!  {\color{gray}{10^1}} + 2  \!\cdot\!  {\color{gray}{10^0}}  \!\cdot\!  4  \!\cdot\!  {\color{gray}{10^1}} \, + \\ & \hspace{1.25em} 1  \!\cdot\!  {\color{gray}{10^1}}  \!\cdot\!  5  \!\cdot\!  {\color{gray}{10^0}} + 2  \!\cdot\!  {\color{gray}{10^0}}  \!\cdot\!  5  \!\cdot\!  {\color{gray}{10^0}} \\ & = {\color{goldenrod}{3}}  \!\cdot\!  {\color{gray}{10^3}} + {\color{blue}{6}}  \!\cdot\!  {\color{gray}{10^2}} + {\color{blue}{4}}  \!\cdot\!  {\color{gray}{10^2}} + {\color{red}{8}}  \!\cdot\!  {\color{gray}{10^1}} + {\color{red}{5}}  \!\cdot\!  {\color{gray}{10^1}} + {\color{green}{10}}  \!\cdot\!  {\color{gray}{10^0}} \\ & = {\color{goldenrod}{3}}  \!\cdot\!  {\color{gray}{10^3}} + ({\color{blue}{6}} + {\color{blue}{4}})  \!\cdot\!  {\color{gray}{10^2}} + ({\color{red}{8}} + {\color{red}{5}})  \!\cdot\!  {\color{gray}{10^1}} + {\color{green}{10}}  \!\cdot\!  {\color{gray}{10^0}} \\ & = {\color{goldenrod}{3}}  \!\cdot\!  {\color{gray}{10^3}} + {\color{blue}{10}}  \!\cdot\!  {\color{gray}{10^2}} + {\color{red}{13}}  \!\cdot\!  {\color{gray}{10^1}} + {\color{green}{10}}  \!\cdot\!  {\color{gray}{10^0}} \\ & = 4140 \end{aligned}\)

The coefficients \( [{\color{goldenrod}{3}}, {\color{blue}{10}}, {\color{red}{13}}, {\color{green}{10}}] \) are the convolution of \([1, 2]\) and \([3, 4, 5]\). Six component multiplications are required, thus performing in \( O(n^2) \) time.

A convolution can also be visualized as flipping the second number, sliding it under the first number, and accumulating products of corresponding digits along the way. For example, for \(12\) and \(345\):

  12    12     12    12
  ×     ××     ××     ×
543    543     543    543
-------------------------
  3     4      5      10
       + 6    + 8
-------------------------
  3     10     13     10
                
As before, six component multiplications are required.

However it so happens that if the numbers are each associated with a frequency spectrum (or, alternatively, a time signal), and transformed and multiplied in the dual domain then only four component multiplications are required, thus performing in \( O(n) \) time.[1]

Essentially, multiplying in the original domain (akin to standard multiplication) consists of multiplying digits and then adding the results. Whereas transforming and multiplying in the dual domain consists of adding digits and then multiplying the results.

As an analogy, consider how we might evaluate \((2 + 3) \cdot 7\). The multiplication-first approach is \(2 \cdot 7 + 3 \cdot 7 = 14 + 21 = 35\), requiring two multiplications. The multiplication-last approach is \((2 + 3) \cdot 7 = 5 \cdot 7 = 35\), requiring only one multiplication.

So how do we apply the multiplication-last approach for \(12 \cdot 345\)?

The first step is to represent each number as a frequency spectrum. The number \(12\) is represented as \([2, 1, 0, 0]\) and the number \(345\) is represented as \([5, 4, 3, 0]\). The digits are arranged in least-significant digit order, that is, by the one's digit first, then the ten's digit, and so on. They are also zero-padded to the output spectrum length which is equal to the total number of input digits minus one, that is, \(2 + 3 - 1 = 4\).

An inverse discrete Fourier transform is performed on each spectrum to produce their respective time signals:[2]

\(IDFT\,[2,1,0,0] = [3, 2+i, 1, 2-i]\)

\(IDFT\,[5,4,3,0] = [12, 2+4i, 4, 2-4i]\)

Next, each corresponding time sample is multiplied. This takes \(O(n)\) time.

\([3 \cdot 12, (2+i) \cdot (2+4i), 1 \cdot 4, (2-i) \cdot (2-4i)] = [36, 10i, 4, -10i]\)

A discrete Fourier transform is then performed to produce the final product spectrum (see Figure 1):[3]

\(DFT\,[36, 10i, 4, -10i] = [10, 13, 10, 3]\)

Flipping the order gives the coefficients \( [{\color{goldenrod}{3}}, {\color{blue}{10}}, {\color{red}{13}}, {\color{green}{10}}] \), therefore:

\( 12 \cdot 345 = {\color{goldenrod}{3}} \cdot {\color{gray}{10^3}} + {\color{blue}{10}} \cdot {\color{gray}{10^2}} + {\color{red}{13}} \cdot {\color{gray}{10^1}} + {\color{green}{10}} \cdot {\color{gray}{10^0}} = 4140 \)

The fastest algorithm for the IDFT/DFT is the fast Fourier transform which takes \(O(n\, log\, n)\) time and so the Fourier multiplication method improves on the conventional \(O(n^2)\) multiplication method for large numbers.

--

[1] The equivalence of convolution in the frequency domain and pointwise multiplication in the time domain (and vice-versa) is expressed by the convolution theorem.

Below is Python code for calculating the convolution and FFT-based multiplication for 12 and 345. Note that 1/4 scaling occurs in the forward transform (np.fft.fft).

import numpy as np

conv_result = np.convolve([1,2], [3,4,5])
print("Convolution:", conv_result.tolist())

fft_result = np.flip(np.fft.fft(np.fft.ifft(np.flip([0,0,1,2]), norm="forward") * np.fft.ifft(np.flip([0,3,4,5]), norm="forward"), norm="forward"))

print("FFT-based multiplication:", fft_result.real.astype(int).tolist())

Output:

Convolution: [3, 10, 13, 10]
FFT-based multiplication: [3, 10, 13, 10]

Note: if the numbers were represented as time signals rather than frequency spectra then the following line would be substituted (which switches the fft and ifft functions and defaults to norm="backward"). The output is identical.

fft_result = np.flip(np.fft.ifft(np.fft.fft(np.flip([0,0,1,2])) * np.fft.fft(np.flip([0,3,4,5]))))

[2] The math for the IDFT transforms is below. For each number, each digit is associated with a specific frequency over a time period - in this case, zero cycles for digits \(2\) and \(5\), one cycle for digits \(1\) and \(4\), and two cycles for digit \(3\). The resulting components of the IDFT transform are the samples at four regular points over the time period. To calculate the sample at each time point, each digit (as a complex amplitude) is rotated on the complex plane according to its associated frequency. In this case, the rotations are the fourth roots of unity: \(e^{2\pi ki/4}\) where \(k=0,1,2,3\) giving \(1, i, -1, -i\) (i.e., quarter turns from 1 on the complex unit circle).

\(\begin{aligned} IDFT\,[2,1,0,0] & = [2 \!\cdot\! 1 + 1 \!\cdot\! 1, \\ & \hspace{1.6em} 2 \!\cdot\! 1 + 1 \!\cdot\! i, \\ & \hspace{1.6em} 2 \!\cdot\! 1 + 1 \!\cdot\! -1, \\ & \hspace{1.6em} 2 \!\cdot\! 1 + 1 \!\cdot\! -i] \\ & \\ & = [2+1, \\ & \hspace{1.6em} 2+i, \\ & \hspace{1.6em} 2-1, \\ & \hspace{1.6em} 2-i] \\ & \\ & = [3, 2+i, 1, 2-i] \end{aligned}\)

For the initial time point no time has yet passed, so each digit remains unrotated (i.e., multiplied by \(1\)). At the second time point, digit \(2\) remains unrotated since its frequency is zero cycles and digit \(1\) is rotated by 90° (i.e., multiplied by \(i\)) since its frequency is one cycle. At the third time point, digit \(2\) remains unrotated and digit \(1\) is rotated by 180° (i.e., multiplied by \(-1\)). At the fourth time point, digit \(2\) remains unrotated and digit \(1\) is rotated by 270° (i.e., multiplied by \(-i\)).

\(\begin{aligned} IDFT\,[5,4,3,0] & = [5 \!\cdot\! 1 + 4 \!\cdot\! 1 + 3 \!\cdot\! 1, \\ & \hspace{1.6em} 5 \!\cdot\! 1 + 4 \!\cdot\! i + 3 \!\cdot\! -1, \\ & \hspace{1.6em} 5 \!\cdot\! 1 + 4 \!\cdot\! -1 + 3 \!\cdot\! 1, \\ & \hspace{1.6em} 5 \!\cdot\! 1 + 4 \!\cdot\! -i+3 \!\cdot\! -1] \\ & \\ & = [5+4+3, \\ & \hspace{1.6em} 5+4i-3, \\ & \hspace{1.6em} 5-4+3, \\ & \hspace{1.6em} 5-4i-3] \\ & \\ & = [12, 2+4i, 4, 2-4i] \end{aligned}\)

Similarly, for the initial time point no time has yet passed, so each digit remains unrotated (i.e., multiplied by \(1\)). At the second time point, digit \(5\) remains unrotated since its frequency is zero cycles, digit \(4\) is rotated by 90° (i.e., multiplied by \(i\)) since its frequency is one cycle and digit \(3\) is rotated by 180° (i.e., multiplied by \(-1\)) since its frequency is two cycles. At the third time point, each digit is rotated by 0°, 180° and 360° (or 0°) respectively. At the fourth time point, each digit is rotated by 0°, 270° (or -90°) and 540° (or 180°) respectively.

[3] The expanded math for the transforms and multiply operation.

\(DFT\,(IDFT\,[2,1,0,0] \cdot IDFT\,[5,4,3,0])\)

\(\begin{aligned}\hspace{0.8em} = \, DFT\,[ & (2 \!\cdot\! 1 + 1 \!\cdot\!  1)  \!\cdot\!   (5 \!\cdot\!  1 + 4 \!\cdot\!  1 + 3 \!\cdot\!  1), \\ & (2 \!\cdot\!  1 + 1 \!\cdot\!  i)  \!\cdot\!   (5 \!\cdot\!  1 + 4 \!\cdot\!  i + 3 \!\cdot\!  -1), \\ & (2 \!\cdot\!  1 + 1 \!\cdot\!  -1)  \!\cdot\!   (5 \!\cdot\!  1 + 4 \!\cdot\!  -1 + 3 \!\cdot\!  1), \\ & (2 \!\cdot\!  1 + 1 \!\cdot\!  -i)  \!\cdot\!   (5 \!\cdot\!  1 + 4 \!\cdot\!  -i + 3 \!\cdot\!  -1)] \\ & \\ =  \, DFT\,[ & (2 + 1) \!\cdot\! (5 + 4 + 3),\\ &  (2 + i) \!\cdot\! (5 + 4i -3),\\ &  (2 - 1) \!\cdot\! (5 - 4 + 3),\\ &  (2 - i) \!\cdot\! (5 - 4i - 3)]\end{aligned}\)

\(\begin{aligned}\hspace{0.6em} & = \, DFT\,[3 \cdot 12, (2+i) \cdot (2+4i), 1 \cdot 4, (2-i) \cdot (2-4i)] \\ & \\ & = \, DFT\,[36, 10i, 4, -10i]\end{aligned}\)

\(\begin{aligned}\hspace{0.8em} = \tfrac{1}{4} [ & 36 \!\cdot\! 1 + 10i \!\cdot\! 1 + 4 \!\cdot\! 1 - 10i \!\cdot\! 1, \\ & 36 \!\cdot\! 1 + 10i \!\cdot\! -i + 4 \!\cdot\! -1 - 10i \!\cdot\! i, \\ & 36 \!\cdot\! 1 + 10i \!\cdot\! -1 + 4 \!\cdot\! 1 - 10i \!\cdot\! -1, \\ & 36 \!\cdot\! 1 + 10i \!\cdot\! i + 4 \!\cdot\! -1 - 10i \!\cdot\! -i] \end{aligned}\)

\(\begin{aligned}\hspace{0.8em} = \tfrac{1}{4} [ & 36 + 10i + 4 - 10i, \\ & 36 + 10 - 4 + 10, \\ & 36 - 10i + 4 + 10i, \\ & 36 - 10 - 4 - 10] \end{aligned}\)

\(\begin{aligned}\hspace{0.8em} & = \tfrac{1}{4} [40, 52, 40, 12] \\ & \\ & = [10, 13, 10, 3]\end{aligned}\)