12 de abril de 2010

Papers de ICALP 2010

Ultimamente estoy con mucho trabajo, y espero dentro de poco poder presentar en este blog los avances de mi investigación.

Se acaba de publicar la lista de papers aceptados en ICALP 2010 en este link. Hay solo 3 papers en computación cuántica:

1- Hari Krovi, Frederic Magniez, Maris Ozols, and Jérémie Roland. Finding is as easy as detecting for quantum walks. [arXiv:1002.2419]
2- Bob Coecke and Aleks Kissinger. The compositional structure of multipartite quantum entanglement.
3- Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow.

Solo pude encontrar la versión online del primer paper. Por suerte es un paper que está muy relacionado con lo que hago y ya lo imprimí para darle una leída.

El problema que resuelve es un pequeño problema abierto que había en algoritmos de búsqueda basados en quantum walks sobre un arreglo 2-dimensional. Algoritmos anteriores solo resolvían el caso de 1 y 2 vértices marcados sobre este arreglo 2-dimensional. Si se quería encontrar más de 2 soluciones, el número de consultas al oráculo cuántico empeoraba. En este paper se presenta un algoritmo que encuentra un número arbitrario de vértices marcados sobre la grilla casi empatando con la cota inferior (solo difiere en un término logarítmico). Esto lo hace utilizando como base quantum walks basados en producto de reflexiones [Magniez et al. 2007] que extienden las cadenas de Markov y una técnica muy interesante de interpolación entre estas cadenas de Markov clásicas.

Definitivamente un paper que tengo que leerlo bien.