Una búsqueda fácil en Google me llevó al Algoritmo de aproximación de Gurvits de Generalización y Desrandomización de Scott Aaronson para lo permanente . El resumen dice que
Alrededor de 2002, Leonid Gurvits dio un sorprendente algoritmo aleatorio para aproximar el permanente de una matriz n * n A. El algoritmo se ejecuta en tiempo O (n ^ 2 / eps ^ 2) y se aproxima a Per (A) dentro de eps * || A || ^ n error aditivo. Una ventaja importante del algoritmo de Gurvits es que funciona para matrices arbitrarias, no solo para matrices no negativas. Esto lo hace altamente relevante para la óptica cuántica, donde los permanentes de matrices complejas de norma limitada juegan un papel central. De hecho, la existencia del algoritmo de Gurvits es la razón por la cual, en su trabajo reciente sobre la dureza de la óptica cuántica, Aaronson y Arkhipov (AA) tuvieron que hablar sobre problemas de muestreo en lugar de problemas de estimación.
Es # P-Difícil calcular el permanente de una matriz, a diferencia del cálculo del determinante que requiere tiempo polinómico.
- En mecánica cuántica, ¿está comprobado que un objeto no existe a menos que lo mire?
- ¿Qué piensan los ateos y los escépticos sobre la legitimidad de la mecánica cuántica? ¿Lo compran todo?
- ¿Por qué las computadoras cuánticas se consideran "límites de la tecnología humana"?
- ¿Cuáles son los hechos más alucinantes relacionados con la física cuántica?
- ¿Cuál es el estado de la computación cuántica?
