Simulating Classical Probabilistic Transitions with superoperators

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

Answer 1

With further understanding coming from the expanded question, I'm entirely revising my answer, but the original version is kept below in case it's useful.

The point, clearly, is to show how to simulate a probabilistic classical computation. So, we will store a classical distribution by using a diagonal density matrix: $$ \rho=\sum_ip_i|i\rangle\langle i|. $$ For any stochastic matrix $$ S=\sum_{i,j}s_{ij}|i\rangle\langle j|, $$ with $\sum_is_{ij}=1$ for all $j$, we want to be able to create a new distribution $$ \rho'=\sum_jq_j|j\rangle\langle j| $$ with $q_j=\sum_ip_is_{ji}$.

We can do this by introducing two ancillas each of dimension $M$ (note, this is a diversion from what the question asked), initially in state $|00\rangle$, and by applying a unitary $U$ that acts as $$ U|i\rangle|0\rangle|0\rangle=\sum_{j}\sqrt{s_{ji}}|j\rangle|i\rangle|j\rangle. $$ It should be obvious that the state is correctly normalised, and that different values of $i$ yield orthogonal states, which are the necessary conditions for being able to define such a unitary.

Using the unitary, we evolve $$ \rho\rightarrow U\rho U^\dagger=\sum_{i,j,k}p_i\sqrt{s_{ji}s_{ki}}|j\rangle\langle k|\otimes |i\rangle\langle i|\otimes |j\rangle\langle k|. $$ If we trace out the two ancillas (equivalently, measure and forget), this forces $j=k$, and we get the answer $$ \sum_{i,j}p_is_{ji}|j\rangle\langle j|, $$ as desired.

---

I've not entirely understood how you're trying to argue this, so let me convey how I would go about answering it.

Imagine your system is in a state $\rho$. You want to implement a classical probabilistic transformation on it, which I would interpret as meaning "with probability $p_i$, implement the unitary $U_i$ for $i=0,1,\ldots M-1$.". We do this by introducing an $M$-level ancilla, initially in the $|0\rangle$ state. I'm now going to describe a two-step process (although these two steps should be combined). First, implement a unitary on the ancilla that performs the conversion $$ |0\rangle\rightarrow\sum_{i=0}^{M-1}\sqrt{p_i}|i\rangle. $$ Second, implement the unitary $$ \sum_{i=0}^{M-1}|i\rangle\langle i|\otimes U_i, $$ where the ancilla is the control and the original system is the target.

If we now measure the ancilla system, we get answer $i$ with probability $p_i$, and the original system is in the state $U_i\rho U_i^\dagger$. Hence, if we forget the measurement result, we would have to describe the whole thing as $$ \sum_i p_iU_i\rho U_i^\dagger, $$ which has had the unitaries $U_i$ applied according to a classical probability distribution. If you select the unitaries to be permutation matrices, that describes classical probabilistic transitions, if I'm understanding the term as intended.

Answer 2

Suppose you want to obtain a transition matrix sending $N$ inputs into $M$ outputs.

You can then start with $N$ orthonormal vectors of length $MK$ with $K$ the dimension of the ancillary space (note that you can always think of such an orthonormal set of vectors as a subset of columns of some larger unitary matrix, like it is done in the question). Denote the $n$-th such vector with $v^{(n)}$, whose components are written as $v^{(n)}_{mk}$, where indexes the different outputs and $k$ is a coordinate in the ancillary space (in the original post we have $N=M=K=2$).

Then, the transition matrix $S$ is a $M\times N$ matrix defined elementwise by $S_{mn}=\sum_{k=1}^K |v^{(n)}_{mk}|^2$. The columns of this matrix always sum up to one, but the rows only do when $N=MK$.