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.

Hay ordenadores clásicos digitales (basados en bits y puertas lógicas) y analógicos; también hay ordenadores cuánticos “digitales” (basados en cubits y circuitos de puertas lógicas cuánticas) y “analógicos” (como los basados en caminos aleatorios cuánticos). Los tres artículos que se publican en Science muestran que un ordenador cuántico analógico basado en caminos aleatorios puede realizar ciertos cálculos algebraicos con matrices mucho más rápido que su versión clásica. En este tipo de computación, varias partículas recorren un camino con múltiples bifurcaciones, eligiendo en cada paso el camino derecho o el izquierdo con cierta probabilidad; variando estas probabilidades se pueden implementar algunos algoritmos de cálculo. En la versión clásica cada trayectoria es independiente, pero la superposición cuántica de todas las trayectorias posibles permite reducir el número de pasos para explorarlas en su totalidad. El secreto es utilizar como partículas bosones acoplados por fuerzas de intercambio. Spring et al., Broome et al., y Tillmann et al. utilizan fotones (partículas de luz) para implementar su algoritmo de caminos aleatorios cuánticos. Los fotones se propagan por una serie de guías ópticas que están muy cercas las unas de las otras, de tal forma que los fotones pueden saltar a las guías adyacentes. Los autores llaman a su algoritmo “muestreo de bosones.”

Dibujo20130215 Experimental scheme for boson sampling

Broome et al. han utilizado tres guías ópticas (N=3, luego calculan el permanente de una matriz de 3×3). En principio, su diseño es escalable, aunque está más allá de la tecnología actual. Los autores afirman que a partir de N=20, este ordenador cuántico analógico sería de gran utilidad práctica. Por supuesto, para dicho número de fotones, habrá que desarrollar protocolos de corrección de errores que garanticen la robustez práctica del nuevo diseño; este problema está aún abierto.

Dibujo20130215 Schematic and characterization of the photonic circuit

Spring et al. también ha implementado el algoritmo de “muestreo de bosones” con tres fotones. Incrementar el número de fotones no es fácil, pues mantener el estado de indistinguibilidad de N fotones requiere luchar contra la decoherencia durante la evolución de los fotones por las guías antes de la medida. No parece fácil lograrlo, máxime cuando las pérdidas en las guías ópticas destruyen la evolución unitaria de los fotones por el sistema. Aún así, los autores de este trabajo opinan que incrementar el número de fotones en esta tecnología podría ser más fácil que incrementar el número de cubits en un computador cuántico convencional basado en puertas lógicas.

Dibujo20130215 quantum logic gates using quantum random walks

La computación basada en caminos aleatorios cuánticos es universal, es decir, se puede diseñar un conjunto universal de puertas lógicas utilizando este tipo de computación. El problema era que el grafo necesario para simular un algoritmo con n cubits requería un número exponencial de caminos (que en una implementación óptica corresponderían a guías ópticas). Andrew M. Childs et al. demuestran cómo reducir el coste a un número polinómico de caminos (el polinomio tiene grado doce); su diseño eficiente (aunque poco práctico) de un ordenador cuántico universal mediante caminos aleatorios se basa en el modelo de Bose-Hubbard (la versión para bosones del modelo de Hubbard para fermiones). Para simular un computador cuántico con n cubits y g puertas lógicas, se necesitan O(n12g4) fotones, en una grafo de guías ópticas con O(n13g5) vértices, y un número de pasos de tiempo de O(n12g5). Obviamente, este tipo de diseños no parecen muy prometedores (como implementación práctica de un ordenador cuántico universal).

5 Comentarios

Participa Suscríbete

pimedios

¿qué implicación tiene en cuanto a la complejidad computacional del problema del cálculo de permanente?, ¿el artículo es una afirmación de que es un problema P?

emulenewsemulenews

No, pimedios, el algoritmo cuántico lo único que afirma es que el problema es BQP (salvo que P=NP, el problema no está en P). Recuerda, P está en BQP, pero no al revés; la relación entre BQP y NP no es conocida, aunque la conjetura es que BQP está en NP, pero no al revés.

william rodriguez diazwilliam rodriguez diaz

cordial saludo si alguien sabe sobre como es la matriz Z DE LA MORFINA YA QUE ESTOY TRABAJANDO SOBRE UNA INVESTIGACION SOBRE ELLA

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>