Quantum Query Complexity y Quantum Walks por Marcos Daniel Villagra

Con este post queda inaugurada la sección "posts invitados". Esperemos con el tiempo encontrar a más hispanohablantes investigando en computación cuántica que quieran participar de esta sección.

Este primer post está escrito por Marcos Daniel Villagra, un investigador paraguayo que trabaja en Japón. Aquí nos cuenta su tema de investigación. Gracias Danny!

A continuación en esta entrada voy a dar una explicación sobre dos áreas muy activas de investigación en computación cuántica: “Quantum Query Complexity” y “Quantum Walks”. Espero no haberme alargado mucho, y más importante, espero la explicación haya sido clara. Para una lectura amena, es recomendable un conocimiento básico en análisis de algoritmos.

Query Complexity” consiste en el estudio de la complejidad temporal de los algoritmos basados en oráculos. Un oráculo es como una caja negra, a la cual podemos hacer una pregunta y retorna la respuesta en una unidad de tiempo, e.g., cual es el costo de un camino en un grafo, número de cláusulas satisfechas en de una fórmula Booleana, etc. Aquí el tiempo se mide en cuantas consultas hacemos al oráculo hasta encontrar la respuesta. Considerando un problema de búsqueda general en donde se busca uno o varios elementos de un conjunto de n objetos en total, encontrar la respuesta quiere decir que obtenemos una respuesta del algoritmo con una probabilidad 1 o 1-ε donde ε > 0, i.e., el error ε esta acotado. Entonces “Quantum Query Complexity” es el estudio de la complejidad temporal de algoritmos cuánticos basados en oráculos. El ejemplo más claro de este tipo de algoritmos es el famoso algoritmo de Grover, el cual encuentra una respuesta en O(√n) consultas al oráculo con una probabilidad de por lo menos 1/2. Ni siquiera es necesario mirar todos los objetos para tener una respuesta!! Clásicamente encontramos un objeto en O(n). Fíjense que el algoritmo da una respuesta con 50% de probabilidad, pero gracias a las estadísticas podemos diseñar un experimento para que luego de varias repeticiones del algoritmo, la probabilidad sea muy cercana a 1. Es importante notar que este algoritmo es óptimo, esto quiere decir que para encontrar un objeto con error acotado tenemos que hacer por lo menos √n consultas al oráculo.

Actualmente la investigación en esta área está concentrada en mejorar los algoritmos de búsqueda por una constante, por ejemplo, digamos que hay un algoritmo A que encuentra elementos en a√n consultas al oráculo donde a es una constante dependiente del problema, entonces podemos diseñar un algoritmo B que encuentra elementos en 0.5a√n consultas por medio de mejoras que podemos hacer a A. Encontrar un algoritmo como B no es tarea sencilla, y depende mucho del tipo de problema (SAT, TSP, “Triangle Finding”, etc.) y de la estructura interna del espacio de estados de dicho problema. Por ejemplo, para el problema de encontrar triángulos en un grafo, el algoritmo requiere O(n^7/10) consultas (siempre con error acotado).

Un agregado muy importante que poseen los algoritmos clásicos son las heurísticas. Una heurística es una forma de captar información del problema y utilizarla para hacer un algoritmo más eficiente. En general, no hay forma aun de implementar heurísticas o captar información estructural en los algoritmos de busqueda cuánticos. Existen pocas propuestas, pero no son del tipo de información estructural que puede ser captada por algoritmos clásicos. En este punto es donde entran los “Quantum Walks”.

Un “Quantum Walk” es la contraparte cuántica de los “Random Walks”. Consiste en la simulación del movimiento de una partícula sobre un grafo. Cada arco del grafo posee una probabilidad de transición de un nodo a otro, y la partícula se mueve de un punto a otro teniendo en cuenta estas probabilidades. Pero tratándose de una partícula cuántica, esta se mueve en superposición, esto quiere decir, que la partícula puede estar en varios nodos al mismo tiempo. Los “Random Walks” y “Quantum Walks” se pueden usar para diseñar algoritmos, y existe en la actualidad una vasta literatura que demuestra como este paradigma puede ayudar mucho en mejorar el rendimiento de los algoritmos. Dependiendo de la conectividad, topología, y otras propiedades del grafo la complejidad del algoritmo cambia. De hecho, se puede demostrar que la búsqueda de Grover corresponde a un “Quantum Walk” sobre un grafo totalmente conectado. También depende el tipo de “Quantum Walk” que se utilice, el cual puede ser de tiempo discreto o continuo.

Mi trabajo de investigación consiste en el estudio de los “Quantum Walks”, desde sus propiedades hasta sus aplicaciones algorítmicas y la complejidad de estas soluciones. En este último punto estamos tratando de explotar información estructural de los problemas de búsqueda para crear así algoritmos eficientes.

Para una introducción a los “Quantum Walks” recomiendo http://arxiv.org/abs/quant-ph/0303081. El algoritmo de Grover lo van a poder encontrar en el siguiente enlace http://arxiv.org/abs/quant-ph/9605043.