Computabilidad y computación cuántica: revisión de modelos alternativos de computación

Resumen

Este es el primer ensayo, de una serie de dos, en los que se quiere presentar visiones panorámicas de la noción de computabilidad de dos nuevos paradigmas de computación. A saber, la computación cuántica y la computación basada en ADN o molecular, así como de los circuitos integrados tridimensionales que constituyen una alternativa para continuar con la miniaturización de procesadores hasta más allá del orden del nanómetro. Aquí se parte de la misma noción de computación, de sus limitaciones lógicas y se delinea el problema de decidir si acaso el determinismo y el no-determinismo coinciden en dispositivos de complejidades polinomiales en el tiempo. En cuanto a la computación cuántica, se presenta a sus elementos matemáticos básicos y a las ventajas que implican en comunicaciones y criptografía. Finalmente se menciona a algunas de las alternativas actuales para implementarlas. Esta presentación es una reseña del estado actual del área, y tan sólo es novedosa en cuanto a sus ejemplos; está escrita originalmente en lengua castellana, y está dirigida a un público extenso, conformado tanto por profesionistas como estudiantes de nivel universitario.

This is the first essay, in a series of two, devoted to review the new paradigms of Computing, namely quantum computing and molecular computing, as well as 3D integrated circuits aiming to miniaturization processes beyond nanometers. An analysis of the computability basics and its limits is realized and the essential P=NP problem is sketched. Quantum computing is introduced, and its implications in hard problems and in cryptography. Finally, some current implementation strategies are outlined. This is just a survey article, its novelty is the presentation suited to a wide audience.