I'm working on the following exercise:
> "Show how a classical probabilistic transition on an M -state system can be simulated
by a quantum algorithm by adding an additional M -state ‘ancilla’ system, applying a
unitary operation to the joint system, and then measuring and discarding the ancilla
system."
- "An Introduction to Quantum Computing" by Phillip Kaye.

**I am wondering if my attempt below is correct, and if not, if I could have a hint how to go about correcting it.** 

My interpretation of the exercise is that I only need to show an example of a super-operator that represents a classical probabilistic transition and not showing this is true in general (although, I am curious how to go about showing this in general). In addition, the classical system needs to be represented by a stochastic matrix that cannot be represented by any unitary (e.g. for stochastic matrix $S$, $\nexists U$ (unitary) s.t. $S_{(i,j)} = |U_{(i,j)}|^2$), else we wouldn't need to use a "super-operator".

Where a super-operator is: $\rho \mapsto Tr_B(\rho \otimes |0...0\rangle\langle0...0|)$, where $B$ is the ancillary system.

Consider a 2-state classical probabilistic system (to make the math simple) represented as qubits: $|0\rangle, |1\rangle$, represented as a vector w.r.t. the standard basis as $[1, 0]^t, [0, 1]^t$ respectively. Then add an ancilla, $|0\rangle$ to construct two elements of a 4-state system : $|00\rangle, |2\rangle = |10\rangle$ represented as tensors w.r.t. the standard basis as $[1, 0, 0, 0]^t, [0,0,1,0]^t$.

Define the unitary operator on the joint-system:
$$U = \begin{pmatrix}
\lambda_{11} & \lambda_{12} & \lambda_{13} & \lambda_{14}\\
\lambda_{21} & \lambda_{22} & \lambda_{23} & \lambda_{24}\\
\lambda_{31} & \lambda_{32} & \lambda_{33} & \lambda_{34}\\
\lambda_{41} & \lambda_{42} & \lambda_{43} & \lambda_{44}\\
\end{pmatrix},$$

assuming the classical system starts in the state $|00\rangle$.

Call the initial 2-state system $A$, and the ancilla as $B$. Applying the super-operator:

$$\operatorname{Tr}_B(U|00\rangle\langle 00|U^\dagger) = \begin{pmatrix}
|\lambda_{11}|^2 + |\lambda_{21}|^2 & \lambda_{11}\lambda_{31}^* + \lambda_{21}\lambda_{41}^* \\
 \lambda_{31}\lambda_{11}^* + \lambda_{41}\lambda_{21}^*& |\lambda_{31}|^2 + |\lambda_{41}|^2 \\
\end{pmatrix} = \rho_0.$$

Similarly, for $|10\rangle$,

$$\operatorname{Tr}_B(U|10\rangle\langle 10|U^\dagger) = \begin{pmatrix}
|\lambda_{13}|^2 + |\lambda_{23}|^2 & \lambda_{13}\lambda_{33}^* + \lambda_{23}\lambda_{43}^* \\
 \lambda_{33}\lambda_{13}^* + \lambda_{43}\lambda_{23}^*& |\lambda_{33}|^2 + |\lambda_{43}|^2 \\
\end{pmatrix} = \rho_1.$$

This is the part I am dubious about:

The transition: $|0\rangle \mapsto |1\rangle$ is represented by the (0,1) entry of the density matrix $\rho_0$ (or the component $|0\rangle\langle 1|)$ and the transition: $|0\rangle \mapsto |0\rangle$ is represented by the (0,0) entry of $\rho_0$ (or the component $|0\rangle\langle 0|)$

If the system started in $|1\rangle$:
 $|1\rangle \mapsto |0\rangle$ is represented by the (1,0) entry of the density matrix $\rho_1$ and the transition: $|1\rangle \mapsto |1\rangle$ is represented by the (1,1) entry of $\rho_1$

Since the system being simulated is classical super-positions aren't considered as inputs.

Thus this super operator w.r.t. the unitary operator above, represents the 2 x 2 stochastic matrix (as long as the entries in each column sum to 1)

$$\begin{pmatrix}
|\lambda_{11}|^2 + |\lambda_{21}|^2 & \lambda_{33}\lambda_{13}^* + \lambda_{43}\lambda_{23}^*  \\
 \lambda_{13}\lambda_{33}^* + \lambda_{23}\lambda_{43}^*& |\lambda_{33}|^2 + |\lambda_{43}|^2 \\
\end{pmatrix} = S$$

Thus to represent the trivial transition matrix:
$$S = \begin{pmatrix}
1 & 1 \\
0 & 0 \\
\end{pmatrix}$$
where entry (i,j) represents the probability of transitioning from j to i (so the columns need to sum to 1), which can't be represented by any 2 x 2 unitary

We can make $U = \begin{pmatrix}
0 & 0 & 1 & 0\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
\end{pmatrix}$ 

**Update (all parts of the exercise)**
[![All parts of the problem][1]][1]


  [1]: https://i.sstatic.net/ZIyJ0.jpg