1 de junio de 2010

Matematicas para Computación Cuántica

Quisiera comentar un poco sobre lo que cuesta estudiar computación cuántica y computación teórica. Entiéndase "cuesta" en términos de esfuerzo, y no en términos de dinero.

Antes de empezar a estudiar el tema, había estado realizando investigación en búsqueda local para problemas de optimización combinatoria como SAT, TSP, etc. Aquí tienen un lista de mis publicaciones. Estos temas los hacía principalmente con experimentos, y fui descubriendo de a poco que no quería hacer investigación experimental. Empece a estudiar computación cuántica con énfasis en algoritmos y complejidad computacional hace 2 años atrás. Ese fue mi plan para la escuela de post-grado. Actualmente ya me siento cómodo trabajando en esta área, tanto que ya estoy en condiciones de publicar resultados. Ahora mismo conferencias, y luego revistas.

La parte más complicada es construir una intuición. Para trabajar en computación teórica utilizamos generalmente las máquina de Turing como modelo. Acostumbrarse a ello no es fácil, y requiere mucho estudio para que se vuelva algo más natural. La mecánica cuántica es en mi opinión más difícil, porque las personas traemos instintivamente conceptos como velocidad, distancia, aceleración, etc., pero en el mundo cuántico no tenemos forma de percibir lo que ocurre. La intuición y el sentido común no sirven y tenemos que seguir los modelos que están bien probados experimentalmente. Es esa intuición la que requiere horas de estudio todos los días durante varios meses. Y no solamente leer sino también hacer investigación, e intentar resolver problemas. A continuación presento un lista de las cosas que considero necesarias para estudiar complejidad computacional y algoritmos cuánticos.

1- Algebra Lineal. Espacios vectoriales y sus propiedades, con principal énfasis en espacios de complejos.
2- Combinatorica. Contar objetos discretos por medio de permutaciones, combinaciones, etc, y otros conceptos muy importantes como series finitas e infinitas (aunque esto es más cálculo), funciones generadoras, aproximación de Stirling. Aquí también incluiría teoría de grafos combinatorica.
3- Complejidad Computacional. Las clases de complejidad básicas como BPP, P, NP, PSPACE, IP, SZK, P/poly, PH, y otros conceptos como relativización y reducciones. También agregaría otros modelos de computación como "communication complexity", árboles de decisión, PCP, y "derandomization".
4- Fundamentos de Computabilidad / Teoría Recursiva. Las definiciones de autómatas como modelos de computación, problemas decidibles, no-decidibles y semi-decidibles, la jerarquía aritmética, y más reducciones. También modelos descriptivos como cálculo-λ y funciones recursivas.
5- Probabilidades. Los conceptos básicos de espacio de probabilidades, valor esperado, varianza, distribuciones de probabilidades, momentos de una variable aleatoria y como realizar análisis probabilístico de algoritmos y análisis de algoritmos probabilísticos. Es de vital importancia también aquí la teoría de cadenas de markov y el método probabilístico en sus distintas formas.
6- Análisis Funcional. Los conceptos de espacios de Hilbert, espacios con normas, y espacios métricos.
7- Análisis Complejo. Analiticidad, ecuaciones de Cauchy-Riemann, funciones armónicas, algebra de números complejos, integrales de contorno. De aquí tuve que aprender un método para aproximaciones asíntoticas de integrales conocida como el método del punto silla.
8- Algebra Abstracta. Teoría de grupos, anillos y campos de Galois. Aquí pondría teoría de grafos algebraica e incluir "expanders" y grafos de Cayley.
9- Mecánica Cuántica. Postulados de la mecánica cuántica, el operador de densidad, estados cuánticos mezclados y puros, osciladores armonicos, dualidad partícula vs onda, el Hamiltoniano, etc.
10-Teoría de la Información. Cantidad de información y entropía, códigos, compresión.

No creo que sea una lista exhaustiva, pero es eso más o menos lo que tuve que estudiar y aprendí en las clases y fuera de ellas. Algunas ya las había aprendido durante los estudios de pre-grado, y otras en post-grado. Por ejemplo, el método probabilístico utilizando segundos momentos y el "Lovász Local Lemma" lo aprendí por mi cuenta, mientras la clase de complejidad SZK lo aprendí en un clase de post-grado sobre criptografía.

Por supuesto, es imposible acordarse de los detalles de todo, por lo que siempre hay que estar con los libros cerca. Pero por lo menos habría que recordar siempre los resultados principales.

Me imagino que en el área de lógica (donde trabaja Alejandro) debería de haber más cosas. No me imagino cuáles. Las comunidades de complejidad y computabilidad están un poco separadas. Comenzaron unidas pero luego fueron separandose debido a que las técnicas utilizadas eran muy diferentes unas de otras.

Aún habrán más cosas por aprender sin duda.

14 comentarios:

  1. Puf, muy buena lista. Para mi área agregaría también teoría de tipos, lógica lineal, el lambda-cube, isomorfismo de Curry-Howard y de Curry-Howard-Lambek, teoría de categorías con especial énfasis en las compact closed categories, lógica categórica de alto orden, quantum logic, etc.

    ResponderBorrar
  2. Disculpa, yo estoy estudiando matemáticas y me interesan todo este tipo de temas. Me parece que tengo algo de conocimiento de todos menos de cuántica (creo que es muy importante esta). Pero voy al grano: ¿En qué universidad puedo estudiar esto? ¿Se puede estudiar en México o en qué pais? Y ¿Es maestría, doctorado o ambos? De antemano gracias y saludos.

    ResponderBorrar
  3. Depende de que tipo de perfil quieres: Fisica o Ciencias de la Computacion.

    Hay muchas becas por la que puedes obtar. Una de ellas es la de Monbukagakusho ofrecida por el gobierno de Japon. Debes de informarte en la embajada de Japon en tu pais.

    Tambien las becas fullbright. La Northeastern university mantiene un muy buen grupo de ciencias de la computacion.

    Las universidades europeas tiene muy buenos grupos de investigacion. En Asia tambien, principalmente China (Tsinhua University), Korea y Japon.

    En Mexico, creo que el tecmon tiene un grupo de cuantica.

    ResponderBorrar
  4. «¿Es maestría, doctorado o ambos?»

    Pues depende lo que quieras. Si querés dedicarte a la investigación, seguro deberás hacer un doctorado. Si sólo te interesa tener conocimientos sobre el área por algún motivo, pues quizá puedas optar por una maestría.

    «¿Se puede estudiar en México o en qué pais?»

    Para hacer un doctorado, tenés que buscar alguien que esté trabajando en el tema de tu interés y que te pueda dirigir. Poco importa en qué país esté. Quizá haya gente en México.

    Para hacer un doctorado hay dos caminos: 1) Buscar una oferta de doctorado, y solicitar ser aceptado en ella o 2) Buscar gente trabajando en el tema de tu interés, contactarte con ellos y ver si podés hacer el doctorado con ellos. Por este camino es probable que algunos te pidan a vos que propongas el tema de la tesis (aunque habrá otros que ya tengan algún tema en mente), por el otro camino es más probable conseguir ofertas con tesis propuestas.

    Espero te sea útil la info.

    Saludos,
    Alejandro

    ResponderBorrar
  5. Se que la pregunta esta fuera de contexto, pero existe algun prototipo de sistema operativo para computadores cuanticos, cuestiones como administracion de procesos, memoria e interrupciones...?
    Me interesa el tema.... Saludos

    ResponderBorrar
  6. Hola Jonathan.
    Aún no tiene mucho sentido un SO cuántico, ya que no hay máquina cuántica la cual administrar. Lo que si hay, aunque aún no haya máquina cuántica, son compiladores... en general "compilan" desde algún lenguage cuántico a circuitos cuánticos (incluso algunos te devuelven el gráfico del circuito).

    Hay dos reviews importantes sobre el estado del arte en cuanto a lenguages de programación cuánticos: uno por Simon Gay y otro por Peter Selinger.

    Ambos son un poco viejos, pero sirven para tener un pantallazo del tema.

    Saludos.

    ResponderBorrar
  7. hola, me gustaría saber que se necesita para estudiar computación cuántica y si en España se ofrecen este tipo de estudios, actualmente estoy cursando grado medio de informática, tengo 18 años y me encantaría seguir estudiando después de conseguir tanto el ciclo medio como el superior, ya sea una ingeniería de sistemas o informática, o si se puede, computación cuántica, cosa que me parece interesante, muchas gracias :)

    ResponderBorrar
  8. Hola Sergio,

    Al menos en Argentina, las carreras de ingeniería en sistemas son orientadas más hacia la empresa, y no hacia la investigación teórica (como la computación cuántica). A lo que en inglés se le llama Theoretical Computer Science, en Argentina se lo traduce como Ciencias de la Computación.

    La verdad que no estoy seguro cómo lo llamarán en España.

    Si te interesa la carrera científica, tendrías que ver qué carrera de informática tiene un perfil hacia la investigación teórica. En general las carreras universitarias suelen publicar en algún sitio de la universidad, cuál es el perfil del graduado. Si elijes una carrera con un perfil hacia la investigación científica, seguramente te servirá como base para luego comenzar un doctorado en el área que elijas, como computación cuántica. Posiblemente luego de unos años en la carrera, tengas la posibilidad de realizar un master donde te especialices en algún área en particular. Recién a esa altura, podrías buscar algún master europeo en computación cuántica.

    Como base, te aconsejo buscar una carrera de informática (ciencias de la computación), que tenga mucha matemática.

    Espero haberte sido de alguna ayuda. Si tenés alguna carrera en mente, pasame algún link y puedo decirte si se orienta hacia la investigación o hacia el desarrollo.

    Saludos,
    Alejandro

    ResponderBorrar
  9. Hola, primero de todo agradecer tu respuesta.
    He encontrado unos links por wikipedia sobre la investigación teórica en la rama informática.
    http://es.wikipedia.org/wiki/Inform%C3%A1tico_te%C3%B3rico que habla sobre el informático teórico diciendo en un punto "bien un ingeniero informático, enfocado en la parte más conceptual de la informática, a menudo acercándose más al trabajo de un matemático que al de un ingeniero" así que puedo entender que dentro de la ingeniería informática o de la de software se podría llegar más fácilmente a la computación cuántica, crees que podría ser así?
    También tengo este link - http://es.wikipedia.org/wiki/Ingenier%C3%ADa_inform%C3%A1tica
    Luego no se que universidad ofrece estos estudios la verdad... si me puedes afirmar que voy por buen camino busco que universidades lo ofrecen y te paso los links con el perfil del graduado.
    Muchísimas gracias por todos.

    ResponderBorrar
    Respuestas
    1. ¿De qué parte de España eres? Si eres de Madrid, definitivamente una buena opción es la complutense. Por ejemplo, este grupo

      http://www.mat.ucm.es/imi/QI/

      Pero estos son matemáticos, y en realidad no hay diferencias entre un matemático y un científico de la computación. Al último podrías verlo como una especialización del matemático. Algunas partes se solapan con matemáticas puras y otra parte con la aplicada.

      Borrar
    2. Otra cosa, aunque ya Alejandro lo explica muy bien. Tal vez es muy temprano para decidir que hacer. Yo por ejemplo estudié ciencias de la computación (año 2002) por que me interesaba la inteligencia artificial. Una vez que entre a la universidad descubrí los algoritmos y las estructuras de datos, y después la complejidad computacional. Hasta que un día fuí a una conferencia de la IFIP en Chile (allá por el 2006) y atendí a una presentación de Josef Gruzka. Desde ese momento quedé prendido por la computación cuántica, y hasta hoy en día sigo así.

      Borrar
  10. Hola,

    Fijate que en el segundo link que pusiste, dice "La ingeniería informática es la rama de la ingeniería que aplica los fundamentos de la ciencia de la computación,..." Justamente, ciencia(s) de la computación, es la ciencia que estudia dichos fundamentos.

    Viendo los artículos a los que corresponden en la wikipedia en Inglés, diría que "http://es.wikipedia.org/wiki/Ciencias_de_la_computaci%C3%B3n" es la ciencia en sí, y "http://es.wikipedia.org/wiki/Inform%C3%A1tico_te%C3%B3rico" es el científico que estudia esa ciencia.

    Así que si, vas por buen camino :)

    Claro que, desde el inicio, estoy suponiendo que te interesa dedicarte a la informática. Hay otras posibilidades, como la física experimental, donde estarías más cerca de la implementación de la computación cuántica.

    Mi consejo es que veas de qué se tratan esas carreras, y luego decidas, ya que tomar la decisión de investigar un área (como la computación cuántica), antes de comenzar la carrera, es un poco temprano.

    Saludos.

    ResponderBorrar
  11. Muchas gracias de nuevo por responder Alejandro y también a tu interés Marcos.
    Se que es pronto para escoger al 100% que haré, pero me gusta estar organizado es por eso que preguntaba.
    Marcos soy de barcelona.

    ResponderBorrar
  12. Quizas, este sea el complemento, (Sistema o Codigo de Valores Infinitesimales), para que surja el (software cuantico), que debe de surjir para complementar el hardware, de la informatica cuantica o computacion cuantica: http://opensourceecology.org/wiki/Tabla_del_Sistema_o_Codigo_de_Valores_Infinitesimales

    ResponderBorrar