Cálculo eficiente del permanente de una matriz mediante computación cuántica

Dibujo20130215 classical vs quantum random walk with photons

El permanente de una matriz cuadrada N×N se define como el determinante, pero sin alternar los signos de los factores. No hay ningún algoritmo clásico eficiente para calcular el permanente de una matriz general (aunque hay algoritmos de coste polinómico para ciertos tipos de matrices). Se publica en Science un algoritmo cuántico eficiente para calcular el permanente de una matriz que utiliza un ordenador cuántico analógico basado en caminos aleatorios. La matriz se define mediante el acoplo de N guías ópticas coplanares, fabricadas en la superficie de un chip, que son recorridas por fotones acoplados entre sí por las fuerzas de intercambio (las que resultan de la simetría de la función de onda asociada a que son partículas indistinguibles). Midiendo la probabilidad de encontrar un fotón a la salida de las guías se puede calcular el valor del permanente de la matriz. Más aún, la computación cuántica con caminos aleatorios es universal, permite simular cualquier ordenador cuántico basado en puertas lógicas, aunque se requiere un polinomio de grado doce en el número de cubits, como también se publica hoy en Science, lo que lo hace eficiente, pero no práctico. Nos lo cuenta James D. Franson, “Beating Classical Computing Without a Quantum Computer,” Science 339: 767-768, 15 Feb 2013, que se hace eco de los artículos de Matthew A. Broome et al., “Photonic Boson Sampling in a Tunable Circuit,” Science 339: 794-798, 15 Feb 2013, Andrew M. Childs et al., “Universal Computation by Multiparticle Quantum Walk,” Science 339: 791-794, 15 Feb 2013, y Justin B. Spring et al., “Boson Sampling on a Photonic Chip,” Science 339: 798-801, 15 Feb 2013.

Sigue leyendo