Return to Question

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)

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) part (c) is the question asked above

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}$

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)

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 state $|00\rangle$

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

$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$

$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}$

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}$