# Reconstructing state from density matrix (and implications for Grover search)

If I am given a density matrix $$\rho$$ that I know corresponds to a pure state (i.e., $$\rho = |\psi\rangle\langle\psi|$$ for some $$|\psi\rangle$$), then is it possible for me to infer the state $$|\psi\rangle$$?

My intuition says yes; for example, if we let $$|\psi\rangle=\sum_i \alpha_i |a_i\rangle$$ for some orthonormal basis $$\{|a_i\rangle\}$$, then we know that $$\rho = \sum_{ij} \alpha_i\alpha_j^* |a_i\rangle\langle a_j|$$. By orthonormality, the matrix element $$\rho_{ij} = \alpha_i\alpha_j^*$$.

If this is indeed the case, then why can't we simply use the oracle from Grover's algorithm to reconstruct the solution? Let $$x^*$$ be the solution to some search problem. In class, we learned that it is easy to implement an operator $$\mathcal{O}_{x^*}$$ such that $$\mathcal{O}_{x^*}|x^*\rangle = - |x^*\rangle$$ and $$\mathcal{O}_{x^*}|x\rangle = - |x\rangle$$. Then, we can rewrite $$\mathcal{O}_{x^*}$$ as follows:

$$\mathcal{O}_{x^*} = I - |x^*\rangle\langle x^*|$$

Rearranging, we get $$|x^*\rangle\langle x^*| = I - \mathcal{O}_{x^*}$$. This, to me, looks like an expression for a density matrix. So if we can easily construct $$\mathcal{O}_{x^*}$$, as claimed, then it seems like we should also be able to infer $$|x^*\rangle$$. I know I must have some sort of logical flaw in my argument (perhaps relating to what we know/ assumptions we make about the basis?) but I can't quite pin it down. Thanks for the help!

• Is the question about general methods to reconstruct state out of a pure density matrix, or about the correctness of your reconstruction method using Grover's algorithm? Commented Dec 7, 2021 at 1:19
• Both! I started with the question about reconstructing states out of pure density matrices because I was not 100% sure about it, and was thinking that might be the logical flaw in the Grover algorithm argument Commented Dec 7, 2021 at 18:33
• @redfive If you ask two barely related questions in one post, what would be the right/accepted answer? Commented Feb 5, 2022 at 12:39

The matrix $$\mathcal{O}_{x^*}$$ is huge. If you are looking for a satisfying value for a predicate with a 100-bit input, it is $$2^{100}\times 2^{100}$$, or more if you consider ancillary qubits. Its value is known only as a product of matrices representing primitive gates. Calculating an element of the matrix is computationally equivalent to calculating whether an input satisfies the predicate. Looking for the solution in the matrix is just a classical brute-force search.

For the first part of your question: You can reconstruct the state (up to a global phase factor, which is unphysical anyway) from a pure density matrix. Recall $$\rho$$ is a positive Hermitian operator with unit trace, and the eigenvalues of $$\rho$$ are the classical weights for various possible states in the mix. A pure $$\rho$$ has a single non-zero eigenvalue $$1$$, all others being $$0$$. So simply diagonalize $$\rho$$ and the eigenvector with eigenvalue $$1$$ is the state.