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

Question

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!

Answer 1

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.

Answer 2

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.