Computaci n cu ntica

TEORÍA CLÁSICA DE LA INFORMACIÓN (TCI)
De la misma forma que en determinadas circunstancias, aproximamos algunas leyes cuánticas a sus hermanas clásicas, es necesario conocer las bases de la computación clásica y la teoría clásica de la información, antes de definir sus análogos cuánticos.
Existen tres ideas centrales en la teoría clásica de la información que deben ser transportadas al contextocuántico:
El problema más básico en esta teoría es obtener una medida elemental de información:
La máxima cantidad de información que puede ser almacenada por una variable que puede tomar N valores diferentes es log2(N). De esta forma, una variable doble-evaluada contiene una unidad de información. Una unidad de información se llama bit. Los dos valores que puede tomar un bit son 0 y 1.
Por otrolado, debemos poder codificar secuencias enteras de información mediante fuentes idénticas e independientes, en este caso bits, de forma que cualquier secuencia de bits va a transportar un cierto tamaño de información (coherente o no, dependiendo del mensaje).

No es necesario que el codificado sea totalmente exento de error, es suficiente que la fidelidad del mensaje sea cercana a 1:
Se definefidelidad (F) como la probabilidad de que el mensaje decodificado sea idéntico al mensaje anterior a la codificación. De esta forma, la probabilidad de error será: 1-F.
Si podemos enviar a través del canal más bits de los estrictamente necesarios, la fidelidad se podrá hacer arbitrariamente cercana a 1. Si no podemos usar suficientes bits de información, la fidelidad será cercana a 0. Por ejemplo,si alguien no es capaz de escuchar lo que se le esta queriendo decir, se le repetir tantas veces sea necesario para que el mensaje sea correctamente transmitido y por lo tanto, tenga fidelidad 1. Este teorema es particularmente interesante ya que a priori podemos compensar cualquier ‘ruido’ en el canal mediante una secuencia suficientemente larga de bits.




TEORÍA CLÁSICA DE LA COMPUTACIÓN
Eneste momento, nos conciernen cuestiones como: ¿qué es computable? ¿Cuántos recursos son necesarios? La segunda pregunta la puede resolver cualquier usuario de ordenador: memoria y procesador. De forma general, la computación será difícil e inefectiva si los recursos necesarios crecen exponencialmente con el tamaño del input (cantidad de información necesaria para especificar el problema), partiendode esta máxima, se diseñan los ordenadores a partir del uso del sistema binario, descartando el sistema unitario (1 variable) o el decimal (10 variables). Esta elección simplifica mucho el diseño de un ordenador y su sistema de análisis. Para manipular los bits, se definen las puertas lógicas de forma que:
Cualquier transformación de n bits puede ser llevada a cabo mediante sucesivastransformaciones de 1 o 2 bits.

Se definen un total de 16 puertas lógicas capaces de hacer dichas transformaciones. En realidad, la acción cualquiera de estas 16 puertas lógicas puede ser reproducida mediante la combinación de 2 o más puertas lógicas idénticas o diferentes, de esta forma se puede concluir que sólo una puerta lógica es necesaria para cualquier transformación: la puerta NAND (NOT AND).
Respectoa la primera pregunta (¿qué es computable?), se define la complejidad computacional como la cantidad de pasos que una ‘máquina de Turing’ debe realizar para completar cualquier algoritmo y resolver el problema. En general, la complejidad computacional va a depender del tamaño del Input, si la dependencia es polinomial (clase P) el problema será en general tratable. Si la complejidad creceexponencialmente (clase NP) el problema se considerará difícil y a menudo será más eficiente testear posibles soluciones en lugar de encontrar una.
Un problema de clase NP es el de la factorización. El método actualmente más eficiente (Menezes et al 1997), necesita 1018 pasos para factorizar un número de 130 dígitos, que equivale a 42 días a 1012 operaciones por segundo. Si aumentamos el número de...