8
$\begingroup$

Suppose $\rho$ is an $n$-qubit state and $\vec{x}$ is a vector of coefficients in the Pauli representation (also called the Bloch or coherence vector). That is $$ x_k = {\rm Tr}(\rho \sigma_k), $$ where $$ \sigma_k = \sigma_{k_0}\otimes\sigma_{k_1}\otimes\cdots\otimes\sigma_{k_{n-1}}, $$ and each $\sigma_{k_j}\in\{\sigma_0=I,\sigma_1=X,\sigma_2=Y,\sigma_3=Z\}$ is a single qubit Pauli operator.

Now the question is, given a vector $\vec{x}$, what is the most computationally efficient method to determine if the state $$ \rho = \frac1{2^n} \sum_k x_k \sigma_k $$ is a valid density matrix.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Is your question about whether there is a nice constraint on $\vec{x}$ such that $\rho$ is positive, in the $n$-qubit setting just like in the 1-qubit case? Of course, I don't know of such a constraint and would be very interested to find out. $\endgroup$
    – user2186
    May 7, 2013 at 22:56

1 Answer 1

Reset to default
6
$\begingroup$

This was too long for a comment.

There are two papers that have a nice characterization of positivity in terms of the Bloch vector: quant-ph/0301152 and quant-ph/0302024. You might be able to use dynamic programming to speed up a check of positivity by using the conditions in these papers. Basically, they reduce the positivity constraint to a constraint on the characteristic polynomial of $\rho$. Using the well-known connection between coefficients of characteristic polynomials and elementary symmetric polynomials, they can derive necessary and sufficient conditions for positivity of the eigenvalues.

Then the idea is the following. Store the iterated "star" products of the Bloch vectors (see the paper for the definition... it's sort of like a cross product). There are only $d$ of them. Then use Newton's identity to compute the constraints.

I can't immediately see how to compute the star product in time $o(d^3)$ (little-oh), though, so this probably doesn't work. But I haven't thought about it, either.

Another possible issue is that this might not be numerically stable. Again, I haven't thought about it, that's why this should have been a comment.

UPDATE: Maris has privately told me that his comment below is only meant to imply that a single star product can be computed in time $O(d^2)$. That is insufficient for a fast algorithm. There are $d$ conditions that have to be checked, so the total runtime is still $O(d^3)$ for this approach.

In fact, I highly doubt that there is an algorithm that runs faster than $O(d^\omega)$ (matrix multiplication time), since all you've done is rewrite the matrix in a new matrix basis, and even then you would probably have to exploit structure. I think the best you can hope for is $O(d^3)$, which is an equivalent runtime to just a naive approach.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Yes, this is the way to do it. The star product is defined in terms of a symmetric tensor $d_{ijk}$ which in turn is defined via $\{\lambda_i,\lambda_j\} = 2 d_{ijk} \lambda_k$ for $i \neq j$. For fixed $k$ there are only $d$ pairs $(i,j)$ that give a non-zero $d_{ijk}$, so that should let you compute the star product in $d^2$ time. $\endgroup$
    – Māris Ozols
    May 8, 2013 at 3:31
  • 1
    $\begingroup$ Oh, right! For Paulis this $d$ tensor is sparse. That lets you get away with a fast algorithm. Neat! $\endgroup$
    – Steve Flammia
    May 8, 2013 at 5:54

Your Answer

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

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