Let's say I have a particle in the quantum state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, represented as a density operator (1st matrix) that went through a depolarizing chanel (2nd matrix). Let's call the depolarized matrix $D_p$.

$$ \begin{bmatrix} .5 & .5 \\ .5 & .5 \end{bmatrix} \rightarrow \begin{bmatrix} .5 & .43 \\ .43 & .5 \end{bmatrix} $$ Now, I have two of these $D_p$, and their resulting product state is: $$ D_p^{\otimes 2} = \begin{bmatrix} .5 & .43 \\ .43 & .5 \end{bmatrix} \otimes \begin{bmatrix} .5 & .43 \\ .43 & .5 \end{bmatrix}. $$ Now, if I want want to calculate the probability of finding some state $|\psi\rangle = |0\rangle \otimes |0\rangle$ in the above mentioned product system, then this is what I do: $$ p(|\psi\rangle | D_p^{\otimes 2}) = trace(\psi\rangle\langle \psi | D_p^{\otimes 2}). $$ As you can see, calculating this trace is a $O(N^3)$ complexity operation and becomes very slow for even a small number of particles, i.e. for $D_p^{\otimes 10}$ or higher. Is there a principled way to calculate these probabilities? Without using any matrix multiplication? TIA.

Cross-Posted on quantumcomputing.SE


1 Answer 1


As long as your final state is a product state, everything is a product, and the probabilities for the individual qubits will just multiply. So compute the probabilities for each qubit to be in the respective state and just multiply them.

But even if this is not the case, you can compute $\langle \psi\vert D_p^{\otimes k}\vert\psi\rangle$ rather than the trace, then it only scales as $O(N^2)$, $N=2^k$.

Finally, you could use that $D_p^{\otimes k}$ is a tensor product and multiply $\vert\psi\rangle$ with one $D_p$ at a time. Then, it is easy to see that each of these operations only sums over one index with $2$ settings, which takes $2N$ operations, so the total number of operations is $2kN = O(kN) = O(N\log(N))$.


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.