4 de febrero de 2013

Computación cuántica, lambda-cálculo, lógica... y todo eso

Este año estoy trabajando en un centro INRIA y dando clases en la Universidad Paris-Ouest, integrando un grupo de matemáticos. Yo soy informático teórico, no matemático, y es por eso que la investigación la hago en el INRIA.

La semana pasada, dí una charla para el grupo de la universidad. La idea era dar un panorama general de qué es lo que investigo. Dado que el público no conocía computación cuántica, lambda-cálculo, ni nada de los temas que yo trabajo en general, la charla se trató de hacer una introducción a todos esos temas y luego contar un poco, de forma bastante genérica, dónde entrarían mis temas de investigación actuales.

Este post es simplemente para dejarles los slides por si a alguno le interesa. Claro que arriba de los post también hablé, por lo que faltarán detalles. Pero si alguno de los lectores de este blog está interesado en saber un poco de qué se trata todo eso de cuántica, lambda-cálculo y lógica, pues aquí va.


Aquí les dejo también el link directo al PDF

5 comentarios:

  1. Hola,

    Buen trabajo :)

    Tengo algunas preguntas:

    La computación cuántica seguirá también la ley de moore (no se si lo he escrito bien). Es decir, se duplicará su velocidad cada 18 meses (sabiendo que la computación cuántica es extremadamente rápida en mostrar resultados)

    Y cuál es tu opinión respecto al soporte de comunicaciones que llamamos Internet. Se dice que Japón está estudiando una nueva tecnología que reemplazará a la Internet. Esto tendría que ver con la computación cuántica también??

    Y finalmente, si logramos aislar a la perfección el átomo... podemos también controlar la forma de vibración del mismo?. Y así poderlo enviar en medio de otros átomos (léase atravesar las paredes)??? jeje

    Espero tus comentarios
    diego

    ResponderBorrar
    Respuestas
    1. Hola Diego,

      La computación cuántica seguirá también la ley de moore (no se si lo he escrito bien). Es decir, se duplicará su velocidad cada 18 meses (sabiendo que la computación cuántica es extremadamente rápida en mostrar resultados)

      La ley de Moore (creo que se escribe así), no es realmente una ley, es más bien una predicción que se viene cumpliendo bastante bien. En general tenía que ver con la velocidad de los procesadores (en MHz),y últimamente parece que se ha estancado un poco y se empezaron a duplicar los cores en lugar de los MHz.

      Esa "ley" es extremadamente dependiente de la implementación, no es una cuestión de velocidad teórica de los algoritmos. Teóricamente se habla de "complejidad" y eso se mantiene estable hasta que se descubre una mejor forma de resolver el mismo problema con un algoritmo más rápido, es decir con una complejidad menor.

      La computación cuántica se dice que es "más rápida" que la clásica porque algunos problemas se pueden resolver con menor complejidad, o sea, no tiene que ver con la implementación física de la misma, sino que es fundamentalmente mas rápida (su complejidad es menor), y por lo tanto, es demasiado pronto para saber si se regirá por la misma "ley de Moore". (Las implementaciones actuales de la computación cuántica se hacen con manipulaciones en laboratorios... hablar de "velocidad" es muy difícil en ese contexto, nos conformamos con esa manera más fundamental de medir que llamamos complejidad computacional)


      Y cuál es tu opinión respecto al soporte de comunicaciones que llamamos Internet. Se dice que Japón está estudiando una nueva tecnología que reemplazará a la Internet. Esto tendría que ver con la computación cuántica también??

      No estoy al tanto de esos estudios de los que hablás, ni de si tiene algo que ver con computación cuántica. De todas maneras las implementaciones que involucran computación cuántica están lejos de llegar al público general aún (a excepción de algunos mecanismos de criptografía que ya se comercializan).

      Y finalmente, si logramos aislar a la perfección el átomo... podemos también controlar la forma de vibración del mismo?. Y así poderlo enviar en medio de otros átomos (léase atravesar las paredes)??? jeje

      Lo siento, no tengo idea. Soy informático teórico, mis conocimientos de física son muy limitados.

      Saludos,
      Alejandro

      Borrar
  2. Buen día!

    Me presento. Soy Eduardo Islas y estudio matemáticas en la UNAM (México). Pues bien, le comento que mis interéses de investigación científica están orientados principalmente a la teoría de la información. La verdad es que me guía más mi curiosidad que mis conocimientos, puedo decirle que ignoro demasiadas cosas sobre teoría informática, pero me cautivaron esos escritos de Turing, Shannon, Sipser, Vazirani, Scott A., etc. que aún leo para aprenderlos más. Mi entusiasmo y pasión están en esta área y aunque estudio matemáticas (sin duda pienso que son una herramienta determinativa) no pienso que sean la única herramienta necesaria para responder aquellas mis preguntas planteadas sobre el tema (¿Son las actuales bases teorícas de la información a nivel cuántico, realmente "eficientes"? y si no es así, ¿existen tales bases? ¿de qué manera están relacionadas una teoría cuántica de la información con el problema P vs NP? ¿la concepción de dichas bases depende de nuestro lenguaje matemático para entender siquiera el problema? y más aún, su solución?)es por ello que todos los días hago un esfuerzo por estudiar por mi cuenta algunos papers que veo publicados en la red, así como textos relevantes del tema. Le envío un saludo reiterando mi interés en este Blog que sin duda seguiré muy de cerca para también aprender de ustedes. En horabuena!!

    ResponderBorrar
    Respuestas
    1. Hola Marcos,

      Desde mi punto de vista (el cual es sólo mi vista del punto), las ciencias de la computación teórica, son un área de la matemática (en definitiva, Turing (y tantos otros) era matemático!). Creo que es completamente factible pasar de matemática a estudiar teoría de la información. Así que, adelante que vas por buen camino!

      Saludos,
      Alejandro

      Borrar
  3. Hola Marcos, sí existen fundamentos de teoría de información cuántica. Te recomiendo las notas de John Watrous https://cs.uwaterloo.ca/~watrous/CS766/

    Para ver la relación entre teoría de la información y teoría de complejidad computacional hay muchas fuentes. Te recomiendo para comenzar las notas de Lance Fortnow sobre complejidad de Kolmogorov y las referencias en ellas. Es muy buen texto introductorio a la incompresibilidad de cadenas y aleatoriedad computacional http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf

    Ahora, continuando con la respuesta de Alejandro, si quieres estudiar estos temas, matemáticas es el mejor camino. Solo complementa tus estudios con teoría de la computación y física.

    ResponderBorrar