Complejidad de optimización sobre grupo unitario

¿Cuál es la complejidad computacional de optimizar varias funciones sobre el grupo unitario $\mathcal{U}(n)$ ?

Una tarea típica, que surgen a menudo en la teoría de la información cuántica, sería maximizar una cantidad de tipo (o superior polinomios de orden en ) sobre toda unitaria matrices . ¿Es este tipo de optimización eficiente (quizás aproximadamente) computable, o es NP-hard? (tal vez esto es bien conocido, pero no he podido encontrar ninguna referencia general) $\mathrm{Tr}AUBU^{\dagger}$ $U$ $U$

cc.complexity-theory reference-request optimization quantum-information Marcin Kotowski
fuente

¿Está bien restringir "varias funciones" a "polinomios sobre las unitarias"?

Artem Kaznatcheev

No sé mucho sobre cómo surgen estos problemas, pero ¿cuál sería el análogo clásico natural de este problema? ¿Conoces la complejidad de ese problema?

Robin Kothari

Hay un muy buen artículo de Roger Brockett de 1991 que muestra cómo expresar la ordenación y la programación lineal esencialmente en la forma que usted describe, pero sobre las matrices ortogonales. Sin embargo, no se menciona la complejidad, pero el hecho de que dos problemas muy diferentes se puedan expresar de la misma manera significa que necesitará saber algo sobre la estructura del problema para hacer una determinación de complejidad: eecs.berkeley.edu/~sburden/research/ jonathan / Brockett1991.pdf

Suresh Venkat

@Artem: sí, en la práctica, los polinomios de bajo grado son los más relevantes, creo.

Marcin Kotowski,

Se reduce a las descomposiciones propias de

en el ejemplo de grado 2 que da. Para

hermitian, la

unitaria se puede utilizar para maximizar la traza haciendo que los espacios propios de

alineen con los de

; entonces es suficiente para maximizar el producto punto de las secuencias de sus valores propios, lo cual es trivial si

son semidefinidos positivos (y un caso al que podemos reducir agregando múltiplos de la identidad para reescalar valores propios). ¿O está interesado en casos mucho más generales, no necesariamente motivados por la mecánica cuántica en sistemas de pequeña dimensión?

A

$A$

B

$B$

A

$A$

B

$B$

U

$U$

U B U^{†}

$U B U^\dagger$

A

$A$

A

$A$

B

$B$

Niel de Beaudrap

Respuestas:

Lo siento, llego tarde! En la teoría de la computación cuántica, hay muchos ejemplos de problemas de optimización sobre el grupo unitario que, sorprendentemente (al menos para mí), se pueden resolver en el tiempo polinomial (clásico) mediante la reducción a la programación semidefinida.

Este fue un primer ejemplo: resolver un problema mío desde 2000, en 2003 Barnum, Saks y Szegedy mostraron que Q (f), la complejidad de consulta cuántica de una función booleana f: {0,1} ⁿ → {0,1 }, se puede calcular en tiempo polinomial en 2 ⁿ (es decir, el tamaño de la tabla de verdad de f). Pensé en esto pero no pude ver cómo hacerlo, ya que uno necesita optimizar la probabilidad de éxito sobre todos los algoritmos de consulta cuántica posibles, cada uno con su propio conjunto de (posiblemente 2 ^n- tamaños) matrices unitarias. Barnum y col. reducido a SDP explotando una "dualidad" entre matrices unitarias y matrices semidefinidas positivas, el denominado isomorfismo Choi-Jamiolkowski. Para un SDP más reciente y más simple que caracteriza a Q (f), vea el artículo de Reichardt de 2010 que muestra que el método adversario de peso negativo es óptimo.

Otro caso importante en el que se ha explotado este truco es en los sistemas de pruebas cuánticas interactivas. Si bien no es intuitivamente obvio, en 2000 Kitaev y Watrous demostraron que QIP ⊆ EXP. al reducir el problema de la optimización sobre las matrices unitarias de tamaño exponencial que surgen en un sistema de prueba interactivo cuántico de 3 rondas, para resolver un SDP de tamaño exponencial simple (nuevamente, creo, usando el isomorfismo Choi-Jamiolkowski entre estados mixtos y matrices unitarias). El reciente avance QIP = PSPACE surgió de mostrar que ese SDP particular podría resolverse aproximadamente aún mejor, en NC (es decir, mediante circuitos de profundidad logarítmica).

Por lo tanto, sea cual sea su problema de optimización específico que involucre al grupo unitario, supongo que se puede resolver más rápido de lo que piensa, si no de una manera aún más simple, ¡entonces mediante reducción a SDP!

Scott Aaronson
fuente

Querido Scott! Barnum, Saks y Szegedy no mencionan explícitamente el isomorfismo Choi-Jamiolkowski, y no entiendo cómo se relaciona esto con su construcción. ¿Podría por favor elaborar sobre esto? Pregunto porque estoy tratando de entender si un resultado similar es posible para el caso de oráculos defectuosos.

Joris

-3

Determinar si dos matrices de Hadamard son equivalentes es un problema completo de isomorfismo gráfico (GI). Brendon McKay tiene un artículo sobre este tema. Ver BD McKay, Hadamard equivalencia vía isomorfismo gráfico, Matemática discreta, 27 (1979) 213-216.

Dursun
fuente

\pm 1

$\pm 1$