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 All parts of the problem

  • 1
    $\begingroup$ how did you derive your formula for $S$? If that is the stochastic matrix storing the input-output probabilities after tracing out the ancilla, shouldn't all of the elements of $S$ be diagonal elements of the $\rho_i$? How does putting the coherences (the terms such as $\lambda_{33}\lambda^*_{13}$) in there make sense, considering that those are not even real numbers in general? $\endgroup$
    – glS
    Commented Dec 11, 2019 at 12:28
  • $\begingroup$ Ok wow, yeah; my decision to use the anti-diagonal elements makes no sense. I'm realizing that most of my solution makes no sense. Only thing is, I dont know exactly what the diagonal elements here represent in regards to the stochastic matrix. Since as density matrices, the diagonal elements are $|0\langle\rangle1|$ , $|1\langle\rangle0|$. I was trying to use the components of these to represent transitions (like 0 to 1 and 1 to 0). But I think that makes no sense, and @DaftWullie's answer makes a lot more sense. $\endgroup$
    – dylan7
    Commented Dec 11, 2019 at 16:24
  • $\begingroup$ I'm just wondering how @DaftWullie's post applies for the "general case"; showing this process, or some process can represent all classical probabilistic transitions as the question asks, and to prove this. $\endgroup$
    – dylan7
    Commented Dec 11, 2019 at 16:26
  • $\begingroup$ Correction : actually, I realized you cant even get the trivial transition matrix from my definition of $S$. $\endgroup$
    – dylan7
    Commented Dec 11, 2019 at 16:32

2 Answers 2


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.

  • $\begingroup$ So in the case of the transition that puts all states into a given state $i$ with probability $1$, since the $p_i$ are not based on the initial state $\rho$, we would still end up always applying a unitary to the initial state (regardless of what it is). This implies we can't implement such a "probabilistic" transition( even though it is technically deterministic), right ? Since the required permutation matrix is all ones in one row and zero everywhere else (not unitary). Like the trivial one from my post. $\endgroup$
    – dylan7
    Commented Dec 10, 2019 at 13:50
  • $\begingroup$ Basically we could then only apply one of the unitaries to $rho$ (I get the whole operation you described overall is not unitary with $p_i =1$) even though this "deterministic " transition matrix is not unitary. $\endgroup$
    – dylan7
    Commented Dec 10, 2019 at 14:48
  • 1
    $\begingroup$ The "trivial" transformation in your question is not covered by the set of cases that my solution provides. I'm not entirely certain that it should (because I'm not really sure exactly what class of operations the question is asking about). In that specific case, there is a solution one can easily give: start the ancilla in $|0\rangle$, perform swap with the original system, and then do the measure/forget process. $\endgroup$
    – DaftWullie
    Commented Dec 10, 2019 at 15:30
  • $\begingroup$ I added a picture with all parts of the problem. This might help add some clarity as to the class of operators the question is asking for. $\endgroup$
    – dylan7
    Commented Dec 10, 2019 at 17:19

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

  • $\begingroup$ The rows don’t need to sum to 1 even if N=M. See the example S in the original post. $\endgroup$
    – DaftWullie
    Commented Dec 12, 2019 at 6:04
  • $\begingroup$ @DaftWullie thanks, I meant to write $N=MK$ $\endgroup$
    – glS
    Commented Dec 12, 2019 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.