No-cloning Theorem

In a classical computer there is no problem to copy an arbitrary piece of data. However, in quantum computer this is not the case. This is the consequence of a straightforward observation in linear algebra, called the "No-cloning Theorem". In the formalism of quantum computation, we use a unit vector in a Hilbert space to represent the state of a quantum bit. Operations on quantum bits are represented by unitary operators on the Hilbert space. To represent a system with more than one quantum bit, we use tensor products. Here is the No-cloning Theorem in this formulation.


No-cloning Theorem. Let $\mathcal{H}$ be a vector space (over $\mathbb{R}$ or $\mathbb{C}$) of dimension larger than 1. There do not exist a linear operator $U$ on $\mathcal{H} \otimes \mathcal{H}$ and a nonzero vector $v_0 \in \mathcal{H}$ such that $U(x \otimes v_0) = x \otimes x$ for all $x \in \mathcal{H}$.
Proof: Suppose such a $U$ and $v_0$ exist. Choose a nonzero vector $v \in \mathcal{H}$ such that $v, v_0$ are linearly independent. Then $U(v_0 \otimes v_0) = v_0 \otimes v_0, U(v \otimes v_0) = v \otimes v$ and $U((v + v_0) \otimes v_0) = (v + v_0) \otimes (v + v_0) = v \otimes v + v_0 \otimes v + v \otimes v_0 + v_0 \otimes v_0$. But linearity of $U$ demands $U((v + v_0) \otimes v_0) = U(v \otimes v_0) + U(v_0 \otimes v_0) = v \otimes v + v_0 \otimes v_0$. This is a contradiction.

Additive functions on the real line

A function $f: \mathbb{R} \rightarrow \mathbb{R}$ is said to be additive if $f(x + y) = f(x) + f(y)$ for every $x, y \in \mathbb{R}$. Typical examples of additive functions are the linear ones, i.e. $f(x) = ax$ where $a$ is a real constant. One question is that are they the only possibilities? If we further require that $f$ to be continuous, then the answer is positive. But in general, the answer is no and one can use basic linear algebra to construct counter-examples.

The trick is that we can regard $\mathbb{R}$ as a vector space over $\mathbb{Q}$ (and the dimension is infinite, exercise). Let $\beta$ be a $\mathbb{Q}$-basis of $\mathbb{R}$ which contains 1. This can be done by a standard application of Zorn's Lemma. Define $f: \mathbb{R} \rightarrow \mathbb{R}$ on $\beta$ as below and extend $\mathbb{Q}$-linearly. Take $f(1) = 1$ and $f(v) = 0$ whenever $1 \neq v \in \beta$. By definition, $f$ is $\mathbb{Q}$-linear, so it is additive. To see that $f$ is not $\mathbb{R}$-linear, let $0 \neq x \in \mathbb{R}$ be spanned $\mathbb{Q}$-linearly by basis vectors in $\beta$ excluding 1. Then $f(x) = 0$ by construction but $xf(1) = x \neq f(x)$. 

The law of a random variable

Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space and $X$ be a random variable on $\Omega$. The law (or distribution) of $X$ is the (Borel) probability measure on the real line defined by
\[ \mathbb{P}_X(A) = \mathbb{P}(X \in A) \]
for every Borel $A \subseteq \mathbb{R}$.

Conversely, suppose we are given a probability measure $\mu$ on $\mathbb{R}$. We can build a random variable so that its law is precisely $\mu$. Take $\Omega = [0, 1]$, $\mathcal{F}$ be the Borel $\sigma$-algebra and $\mathbb{P}$ be the Lebesgue measure. For each $\omega \in \Omega$, let
\[ X(\omega) = \inf \{t \in \mathbb{R}: \mu((-\infty, t]) \geq \omega\}. \]
This defines a random variable $X$ on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$.

Claim: The law of $X$ is $\mu$.
Proof: Fix any real number $a$. We need to show that $\mathbb{P}(X \leq a) = \mu((-\infty, a])$. Now for every $\omega \in \Omega$,
\[ \begin{aligned}
&X(\omega) \leq a \\
&\Leftrightarrow \inf \{t \in \mathbb{R}: \mu((-\infty, t]) \geq \omega\} \leq a \\
&\Leftrightarrow \forall n \in \mathbb{N} \inf \{t \in \mathbb{R}: \mu((-\infty, t]) \geq \omega\} < a + \frac{1}{n} \\
&\Leftrightarrow \forall n \in \mathbb{N} \mu((-\infty, a + \frac{1}{n}]) \geq \omega \\
&\Leftrightarrow \mu((-\infty, a]) \geq \omega. \\
\end{aligned} \]
Hence we have that $\mathbb{P}(X \leq a) = \mathbb{P}(\{\omega \in \Omega: \mu((-\infty, a]) \geq \omega\}) = \mathbb{P}([0,  \mu((-\infty, a])]) =  \mu((-\infty, a])$. Q.E.D.

Reference:
Bass - Probabilistic Techniques in Analysis