La positividad en la Pauli/Bloch/coherencia representación vectorial

Question

Supongamos $\rho$ $n$- qubit estado y $\vec{x}$ es un vector de coeficientes en la Pauli representación (también llamada la de Bloch o a la coherencia del vector). Que es $$ x_k = {\rm Tr}(\rho \sigma_k), $$ donde $$ \sigma_k = \sigma_{k_0}\otimes\sigma_{k_1}\otimes\cdots\otimes\sigma_{k_{n-1}}, $$ y cada una de las $\sigma_{k_j}\in\{\sigma_0=I,\sigma_1=X,\sigma_2=Y,\sigma_3=Z\}$ es de un solo qubit operador de Pauli.

Ahora la pregunta es, dado un vector $\vec{x}$, ¿cuál es la más eficiente computacionalmente método para determinar si el estado $$ \rho = \frac1{2^n} \sum_k x_k \sigma_k $$ es válida la densidad de la matriz.

Answer 1

Esto era demasiado largo para un comentario.

Hay dos documentos que tienen una buena caracterización de la positividad en términos del vector de Bloch: quant-ph/0301152 y quant-ph/0302024. Usted puede ser capaz de utilizar programación dinámica para acelerar la verificación de positividad mediante el uso de las condiciones en estos documentos. Básicamente, se reduce la positividad de la restricción a una restricción en el polinomio característico de a $\rho$. El uso de la bien conocida relación entre los coeficientes de los polinomios característicos de primaria y simétrica polinomios, se pueden derivar las condiciones necesarias y suficientes para la positividad de los valores propios.

Entonces la idea es la siguiente. La tienda de la iterada "estrella" de los productos de la de Bloch vectores (véase el documento para la definición... es como una especie de producto cruzado). Sólo hay $d$ de ellos. A continuación, utilice Newton identidad para calcular las restricciones.

Yo no puede ver inmediatamente cómo calcular el producto estrella en el tiempo $o(d^3)$ (poco-oh), sin embargo, esto probablemente no funcionará. Pero no he pensado en ello, tampoco.

Otro posible problema es que esto no puede ser numéricamente estable. De nuevo, no he pensado en ello, es por eso que este debería haber sido un comentario.

ACTUALIZACIÓN: Maris ha privado me dijo que su comentario a continuación es sólo implica que un solo producto estrella puede ser calculado en tiempo de $O(d^2)$. Que es insuficiente para un algoritmo rápido. Hay $d$ condiciones que deben ser verificados, por lo que el tiempo total de operación es todavía $O(d^3)$ para este enfoque.

De hecho, dudo mucho que no hay un algoritmo que se ejecuta más rápido que $O(d^\omega)$ (la multiplicación de la matriz de tiempo), ya que todo lo que hemos hecho es reescribir la matriz en una matriz nueva base, e incluso entonces usted probablemente tendría que aprovechar la estructura. Creo que lo mejor que podemos esperar es $O(d^3)$, que es un equivalente de tiempo de ejecución a un enfoque ingenuo.