21 de septiembre de 2010

Más novedades: Caminatas Cuánticas

Reciéntemente (la semana pasada) he tomado y pasado con éxito lo que se conoce como exámen de cualificaciones (del inglés qualifying exam), aunque aquí en Japón lo llaman simplemente "exámen de ingreso al doctorado". Tuve que hacer una pequeña presentación de lo que hice hasta este momento y lo que planeo hacer en el futuro. Ya más adelante voy a comentar sobre lo que voy a hacer (de hecho ya lo comencé), pero ahora paso a transcribir un resumen que describe lo hecho hasta ahora.
Actualmente hay un gran interés en el diseño de algoritmos cuánticos utilizando el paradigma de las caminatas cuánticas. Generalmente, la construcción de algoritmos cuánticos resulta muy difícil, y la utlización de este paradigma resulta ser un enfoque muy prometedor. Las caminatas cuánticas fueron definidas en analogía a las caminatas aleatorias y las cadenas de Markov, y se espera que tengan el mismo éxito para el diseño y análisis de algoritmos cuánticos. Varios algoritmos utilizando caminatas cuánticas ya fueron descubiertos para verificación de multiplicación de matrices, búsqueda de triángulos en grafos, conmutatividad de grupos, por nombrar algunos. Clásicamente, la principal métrica de complejidad para algoritmos basados en cadenas de Markov es el hitting time. Es comúnmente definido como el número esperado de pasos para encontrar un conjunto de vértices marcados en un grafo, y está directamente relacionado con el tiempo de ejecución de los algoritmos aleatorios. De la misma forma, se puede definir una noción similar para caminatas cuánticas, pero esto resulta muy delicado. Si observamos la posición de la caminata sobre un grafo en cada paso, el sistema cuántico colapsa (de acuerdo a los postulados de la mecánica cuántica y el efecto Zenon cuántico), y no tiene ningún sentido tratar de explotar efectos mecánico-cuánticos para aceleración algorítmica. Por lo tanto, hay que tener mucho cuidado al definir una noción adecuada de hitting time. En este trabajo se estudia tal noción llamada One-Shot Hitting Time, y nos concentramos solamente en caminatas de tiempo discreto. Esta investigación está dividida en dos partes: i) líneas, y ii) grillas de 2 dimensiones. Para la primera parte, se propone una caminata que utiliza un operador con parámetros de fase a cargo de entonar la desviación estándar de la distribución de probabilidades inducida sobre la línea. Fórmulas para la evolución en el tiempo de la caminata fueron deducidas utilizando un método de punto silla para aproximación asintótica. Para este fin, como en trabajo anteriores, fue utilizado el análisis de Fourier para simplificar el estudio. También describimos la asintótica demostrando la convergencia débil de la caminata. Estos resultados dan una descripción precisa de los one-shot hitting times sobre la línea. Para la segunda parte, el análisis mencionado arriba no puede utilizarse debido a la complejidad de la fórmulas resultantes. Por lo tanto nos concentramos en acotar el hitting time y la probabilidad de encontrar un vértice arbitrario sobre la grilla. En una grilla de 2 dimensiones de tamaño n es demostrado, utilizando los modelos de caminatas cuánticas con monedas y basadas en cadenas de Markov, un hitting time de O(√n) con una probabilidad de éxito acotada para el primero, y no acotada para el segundo. Estos resultados pueden ser utlizados para aplicaciones algorítmicas en búsqueda espacial y ruteo de redes cuánticas.

La parte de aplicaciones aún la tengo que trabajar para tener todo bien cerrado. Estoy considerando utilizar para el caso de ruteo el modelo de cadenas de espines para transferencia de estados cuánticos. Esto me fue sugerido por Joe Fitzsimons aquí. Parece muy prometedor, pero aún debo de estudiarlo bien.