# Nielsen & Chuang, exercise 2.73 — Density matrix proving the minimum ensemble

I've been trying to solve exercise 2.73 (p.g 105) in Nielsen Chuang, and I'm not sure if i'v been overthinking it and the answer is as simple as i've described below or if I am missing something, or i'm just wrong!

Ex 2.73:

Let $$\rho$$ be a density operator. A minimal ensemble for $$\rho$$ is an ensemble $$\{p_i,|\psi_i\rangle\}$$ containing a number of elements equal to the rank of $$\rho$$. Let $$|\psi\rangle$$ be any state in the support of $$\rho$$. Show that there is a minimal ensemble for $$\rho$$ that contains $$|\psi\rangle$$, and moreover that in any such ensemble $$|\psi\rangle$$ must appear with probability

$$p_i=\frac{1}{\langle\psi_i|\rho^{-1}|\psi_i\rangle}$$

where $$p^{-1}$$ is defined to be the inverse of $$\rho$$, when $$\rho$$ is considered as an operator acting only on the support of $$\rho$$

My answer so far is:

$$\rho$$ is positive the therefore has a spectral decomposition $$\rho=\sum_k\lambda_k|k\rangle\langle k|$$.

The density operator cann be defined as $$\rho=\sum_kp_k|k\rangle\langle k| = \sum_k|\hat{k}\rangle\langle \hat{k}|$$, where $$|\hat{k}\rangle=\sqrt{\lambda_k}|k\rangle$$, and therefore $$|k\rangle = \frac{|\hat{k}\rangle}{\sqrt{\lambda_k}}$$.

For any $$|\psi_i\rangle = \sum_k c_{ik}|k\rangle$$, using the above definition of $$|k\rangle$$:

$$|\psi_i\rangle = \sum_k \frac{c_{ik}}{\sqrt{\lambda_k}}|\hat{k}\rangle$$

The density operator is given by $$\rho=\sum_i|\psi_i\rangle\langle\psi_i|$$, therefore

$$\rho = \sum_{i}\sum_{k}\frac{c_{ik}^2}{\lambda_k}|\hat{k}\rangle \langle\hat{k}|$$.

By the definition of $$\rho$$ is can be seen that $$p_i = \sum_{k}\frac{c_{ik}^2}{\lambda_k}$$.

--- reading this back i'm not sure this is correct at all :(

For the second part working backwards a bit:

$$\langle \psi_i|\rho^{-1}|\psi_i\rangle = \langle \psi_i|\sum_k \left( \frac{1}{\lambda_k}|k\rangle\langle k| \right) |\psi_i\rangle = \sum_k \frac{1}{\lambda_k}\langle \psi_i|k\rangle\langle k |\psi_i\rangle = \sum_{i,k} \frac{1}{\lambda_k}c_{i,k}^2\langle i|k\rangle \langle k |i\rangle$$

Given that $$|i\rangle$$ is of basis $$|k \rangle$$, $$\langle k |i\rangle = \langle i |k\rangle = 1$$ if $$i=k$$, therefore

$$\langle \psi_i|\rho^{-1}|\psi_i\rangle = \sum_{k} \frac{c_{i,k}^2}{\lambda_k}$$, so it then follows that

$$p_i = \frac{1}{\sum_{k} \frac{c_{i,k}^2}{\lambda_k}}$$

However the above result does not match with the result I got for $$p_i$$ in the first part, so one of them is wrong...

• I am aware of the solution in idoc.pub/documents/…, however I find this unsatisfactory and feel as if it has been derived by working backwards, as there is no workings or reasoning given as to why $p_i$ and $q_{i,k}$ are defined as they are in their solution. Apr 17, 2020 at 22:26
• In your linked document, the answers only go up until 2.68. Is the exercise number you provided correct? Apr 17, 2020 at 22:39
• you have to download the pdf and the answers go all the way Apr 17, 2020 at 23:40
• I don't understand what is meant, actually, by "$|\psi \rangle$ appears with probability $p_i = \frac{1}{\langle \psi_i | \rho^{-1}| \psi_i \rangle}$" It doesn't make sense for this to hold for a particular choice of $i$; should this be a summation over $i$? Should the $i$ not be there at all? Is it saying that the probability associated with $\psi_i$ is equal to $\frac{1}{\langle \psi_i | \rho^{-1}| \psi_i \rangle}$? Apr 17, 2020 at 23:49
• I think that is a general concern with this question, I also asked this question on QuantumComputing stack, and a user expressed similar view as you, quantumcomputing.stackexchange.com/questions/11588/… Apr 18, 2020 at 1:06

Sketch of proof: We need the following fact:

Fact: Any density operator has a minimal ensemble.

This can be proven with the spectral theorem. However, this is the only thing that we need the spectral theorem for.

Recall that an operator $$\rho$$ is positive semidefinite iff for all vectors $$|\phi \rangle$$, we have $$\langle \phi |\rho | \phi \rangle > 0$$. For part one, use the fact that $$\langle \psi|\rho|\psi \rangle$$ to show that there exists an $$\alpha$$ with $$0<\alpha<1$$ for which $$\sigma = \rho - \alpha |\psi \rangle \langle \psi |$$ is positive semdefinite. Now, take any ensemble $$\{p_i,|\psi_i\rangle \}$$ for $$\hat \sigma = \frac{\sigma}{1-\alpha}$$, and show that $$\{(1-\alpha)p_i,|\psi_i\rangle\} \cup \{\alpha, |\psi\rangle\}$$ is an ensemble for $$\rho$$.

I'm not quite sure what they're asking for part $$2$$, but here are my thoughts. Let $$r$$ denote the rank of $$\rho$$, and let $$\alpha_* = \frac{1}{\langle \psi |\rho^{-1}|\psi\rangle}$$. It suffices to note/show that $$\sigma = \rho - \alpha |\psi \rangle \langle \psi |$$ will fail to be positive semidefinite for $$\alpha > \alpha_*$$, and that $$\sigma$$ will have rank $$r$$ (instead of $$r-1$$) when $$\alpha < \alpha_*$$.

Proof that this is the correct value for $$\alpha_*$$: With the Schur complement, we see that $$\rho - \alpha xx^\dagger$$ is positive semidefinite iff the matrix $$M = \pmatrix{\rho & x\\x^\dagger & \alpha^{-1}}$$ is positive semidefinite. By taking the Schur complement relative to $$\rho$$, we find that $$M$$ is positive semidefinite iff $$\alpha^{-1} - x^\dagger\rho^{-1}x \geq 0$$, which is to say that $$\alpha \leq \alpha_* = \frac{1}{x^\dagger\rho^{-1}x}$$, as was desired.

A matrix version of the proof given on the QIT SE site:

Let $$D = \operatorname{diag}(p_1,\dots,p_r)$$, and let $$a_1,\dots,a_r$$ be the linearly independent vectors (corresponding to $$\hat \psi_i = \sqrt{p_i}\psi_i$$. Let $$A$$ be the matrix with columns $$A$$; we have $$\rho = AA^\dagger$$. Note that $$A = \rho \rho^{-1} A = AA^\dagger \rho^{-1} A= A[A^\dagger\rho^{-1}A].$$ $$A$$ has linearly independent columns and is therefore left-cancellable. Conclude that $$A^\dagger \rho^{-1} A = I_{r}$$. If we consider the $$j,j$$ entry, we have $$1 = a_j^\dagger\rho^{-1}a_j \leadsto 1 = \langle \hat \psi_j | \rho^{-1} | \hat \psi_j \rangle = p_j \cdot \langle \psi_j | \rho^{-1} | \psi_j \rangle.$$

Second version of the matrix proof: $$\rho - \alpha xx^\dagger$$ is positive semidefinite iff $$\rho^{-1/2}[\rho - \alpha xx^\dagger] \rho^{-1/2} = I - \alpha (\rho^{-1/2}x)(\rho^{-1/2}x)^\dagger$$ is postive semidefinite. It's easy to see that the lowest eigenvalue of this matrix is $$1-\lambda$$, where $$\lambda$$ is the largest eigenvalue of $$\alpha (\rho^{-1/2}x)(\rho^{-1/2}x)^\dagger$$. Because this matrix has rank $$1$$, we see that $$\lambda = \operatorname{Tr}(\alpha (\rho^{-1/2}x)(\rho^{-1/2}x)^\dagger) = \alpha (\rho^{-1/2}x)^\dagger) (\rho^{-1/2}x) = \alpha x^\dagger \rho^{-1} x.$$ We reach a threshold at $$\lambda = 1$$, i.e. $$\alpha = \frac{1}{x^\dagger \rho^{-1} x}$$.

• Please let me know if anything is unclear; I am willing to prove any of the steps in detail, or at least provide a reference. That said, I would suggest that it is a useful exercise to try to fill in the blanks on your own. Apr 17, 2020 at 22:41
• my one question is why do we assume the form of $\hat{\sigma}$, is there any theoretical basis, or just a fact of life? Apr 18, 2020 at 1:09
• @Sam $\hat \sigma$ is just $\frac{\sigma}{\operatorname{Tr}(\sigma)}$, i.e. $\sigma$ normalized so that it has trace $1$. The fact that $\operatorname{Tr}(\sigma) = 1 - \alpha$ follows from $$\operatorname{Tr}(\sigma) = \operatorname{Tr}(\rho) - \alpha \operatorname{Tr}(|\psi \rangle \langle \psi |) = 1 - \alpha\cdot 1.$$ Apr 18, 2020 at 1:12
• @Sam and the point of $\sigma$ here is that if $|\psi \rangle$ is part of an ensemble with probability $p$, it must hold that $\rho = p |\psi \rangle \langle \psi| + [\text{stuff}]$. Stuff is the sum over the rest of the ensemble, which is necessarily positive definite with trace $1-p$. Apr 18, 2020 at 1:15
• I had assumed that $p$ would equal $\langle \psi | \rho | \psi \rangle$, which was incorrect. Latest edit fixes this and provides a proof of the result with a different technique to that used in the answer to your other post. I suspect that an approach via calculus can be taken as well if we minimize $y^*(\rho - \alpha xx^*)y = y^*y - \alpha |x^*y|^2$. Apr 18, 2020 at 2:07

I think the following may help solve your doubt as to how the solution found here https://idoc.pub/documents/chuang-nielsen-unofficial-solutions-d477ed8ozy42 comes about.

From the Unitary freedom in the ensemble for density matrices and the spectral theorem it must be true that \begin{align} &\sum_k \lambda_k |k\rangle \langle k| \equiv \sum_k |\tilde{k} \rangle \langle \tilde{k}| = \sum_i |\tilde{\psi}_i\rangle \langle \tilde{\psi}_i| = \sum_i p_i |\psi_i\rangle \langle \psi_i| \iff |\tilde{\psi}_i\rangle = \sum_k u_{ik} |\tilde{k}\rangle \\ &\implies \sqrt{p_i}|\psi_i\rangle = \sum_k u_ik \sqrt{\lambda_k}|k\rangle \end{align} The sums range from $$k=1,2\dots d$$ where $$d$$ is the Rank of $$\rho$$. The fact that such ensemble of $$\{p_i,\psi_i \}$$ exists follows directly from $$$$\pmatrix{|\psi_1\rangle & \dots & |\psi_d\rangle}^{T} = U\pmatrix{|1\rangle & \dots |d\rangle}^{T}$$$$ What the problem asks is to prove that any state $$|\psi_j\rangle = \sum_k c_{ik} |k\rangle$$ can be part of such an ensemble. From the above, is it direct to derive that for this to be possible it must be true \begin{align} u_{jk} = \frac{c_{jk}\sqrt{p_j}}{\sqrt{\lambda_k}} \text{ and as} \sum_k |u_{jk}|^2 = 1 \implies p_j\sum_k \frac{|c_{jk}|^2}{\lambda_k} = 1 \implies p_j = \frac{1}{\sum_k \frac{|c_{jk}|^2}{\lambda_k}} \end{align} With this, you know exactly what the $$j$$ row of $$U$$ must be and using Gram-Schmidt you can construct the rest of U and choose the $$p_i$$ so that the sum $$\sum p_i = 1$$. To finish the problem now is straightforward, remember that in general the probability to obtain the state $$|\psi_m\rangle$$ is given by \begin{align} p_m = \text{Tr}(M_m^{\dagger}M_m\rho) \end{align} So if you choose $$M_j = |\psi_j\rangle \langle \psi_j|$$ \begin{align} p_j = \text{Tr}(|\psi_j\rangle\langle\psi_j|\rho) = \langle \psi_j|\rho|\psi_j\rangle \end{align} And it follows the little nice result in this case that $$\langle \psi_j|\rho|\psi_j\rangle = 1/ \langle \psi_j|\rho^{-1}|\psi_j\rangle$$.