Bits: De bits a vectores · Math of Quantum

En 1937 un estudiante del MIT de 21 años, Claude Shannon, demostró en su tesis de máster que los circuitos de relés de las centralitas telefónicas obedecen el álgebra que George Boole había inventado en 1854 para formalizar la lógica. Desde entonces, todo ordenador manipula bits, cantidades que valen 0 o 1, con puertas lógicas. Para entender qué tiene de nuevo la computación cuántica hay que mirar antes el bit clásico con otros ojos: como un vector.

Circuitos booleanos

Una puerta recibe bits y devuelve bits: $NOT (x) = 1 - x$ , $AND (x, y) = x y$ , $NAND (x, y) = 1 - x y$ . Un circuito conecta puertas y calcula una función $f : {0, 1}^{n} \to {0, 1}^{m}$ . Basta un único tipo de puerta para construirlas todas.

Teorema (universalidad de NAND)

Toda función booleana $f : {0, 1}^{n} \to {0, 1}$ se puede calcular con un circuito formado solo por puertas NAND.

Demostración

Escribimos $f$ en forma normal disyuntiva: un OR, sobre las entradas $a$ con $f (a) = 1$ , del AND de los literales $x_{i}$ o $\neg x_{i}$ que solo es cierto en $a$ . Bastan, pues, NOT, AND y OR. Y cada una se construye con NAND: $\neg x = NAND (x, x)$ , $x \land y = \neg NAND (x, y)$ , $x \lor y = NAND (\neg x, \neg y)$ (De Morgan).

La demostración esconde una advertencia que importará más adelante: la forma normal puede tener exponencialmente muchos términos. Poder calcular una función no dice nada sobre calcularla eficientemente. Si los ordenadores cuánticos pueden calcular eficientemente lo que los clásicos no pueden es la pregunta que recorre toda esta web.

La información es física

Una puerta AND destruye información: viendo la salida 0 no se puede saber si la entrada era 00, 01 o 10. En 1961 Rolf Landauer, en IBM, demostró que eso tiene un precio físico ineludible.

Principio (Landauer, 1961)

Borrar un bit de información en un entorno a temperatura $T$ disipa al menos

E \geq k_{B} T \ln 2

de calor, donde $k_{B}$ es la constante de Boltzmann (unos $3 \times 10^{- 21}$ julios a temperatura ambiente).

En 1973 Charles Bennett demostró que ese coste no es inevitable: todo cálculo puede hacerse de forma reversible, sin borrar nada, guardando suficientes bits extra y «descalculando» los resultados intermedios al final. En 1980 Tommaso Toffoli encontró la puerta que lo hace práctico.

Teorema (universalidad reversible; Toffoli, 1980)

La puerta de Toffoli $T (a, b, c) = (a, b, c \oplus a b)$ es reversible (es su propia inversa) y, con bits auxiliares fijados a 0 o 1, toda función booleana se puede calcular con un circuito de puertas de Toffoli.

Demostración

Aplicar $T$ dos veces da $c \oplus a b \oplus a b = c$ , así que $T$ es su propia inversa. Con $c = 1$ la tercera salida es $1 \oplus a b = NAND (a, b)$ , y con $b = 1, c = 0$ copia $a$ (duplicación de cables). Por la universalidad de NAND, cualquier circuito se puede simular.

Este detalle es crucial: como veremos, la evolución de un sistema cuántico siempre es reversible. El teorema de Toffoli garantiza que un ordenador cuántico puede hacer, como mínimo, todo lo que hace uno clásico.

Bits como vectores

Ahora, el cambio de perspectiva. Representemos el bit 0 con el vector $| 0 ⟩ = (\binom{1}{0})$ y el bit 1 con $| 1 ⟩ = (\binom{0}{1})$ (la notación $| \cdot ⟩$ , de Dirac, aparecerá constantemente). Entonces NOT es una matriz:

X = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), X | 0 ⟩ = | 1 ⟩, X | 1 ⟩ = | 0 ⟩ .

Con $n$ bits hay $2^{n}$ configuraciones posibles, y cada una es un vector de la base de un espacio de dimensión $2^{n}$ . Un circuito reversible determinista es una matriz de permutación que baraja esos vectores. Parece una forma extravagante de describir algo sencillo, hasta que añadimos el azar.

Bits probabilísticos

Una moneda en el aire es un bit que no conocemos. La describimos con un vector de probabilidades $𝐩 = (p_{0}, p_{1})$ , con $p_{i} \geq 0$ y $p_{0} + p_{1} = 1$ . Es decir, un vector de componentes no negativas y norma 1 igual a 1: $‖ 𝐩 ‖_{1} = | p_{0} | + | p_{1} | = 1$ . Las operaciones aleatorias también son matrices.

Proposición (matrices estocásticas)

Una matriz $S$ transforma todo vector de probabilidades en otro vector de probabilidades si y solo si es estocástica: entradas no negativas y cada columna sumando 1.

Demostración

Aplicar $S$ al vector de la base $𝐞_{j}$ da la columna $j$ , que tiene que ser un vector de probabilidades. Recíprocamente, $S 𝐩$ es una combinación convexa de las columnas, que son vectores de probabilidades, y el conjunto de vectores de probabilidades es convexo.

Una matriz estocástica solo puede mezclar: lleva los puntos del segmento $p_{0} + p_{1} = 1$ hacia su interior y, salvo que sea una permutación, no se puede deshacer sin perder la garantía de no negatividad. La incertidumbre crece; nunca disminuye. ¿Existe algo más suave, que permita ir de 0 a 1 de forma continua y reversible? Aquí llega la primera sorpresa.

Proposición (NOT no tiene raíz cuadrada estocástica)

No existe ninguna matriz estocástica $S$ de $2 \times 2$ tal que $S^{2} = X$ .

Demostración

Escribamos $S = (\begin{matrix} a & b \\ 1 - a & 1 - b \end{matrix})$ con $a, b \in [0, 1]$ . La entrada superior izquierda de $S^{2}$ es $a^{2} + b (1 - a)$ , que debe ser 0. Los dos términos son no negativos, así que $a = 0$ y $b = 0$ . Pero entonces $S = (\begin{matrix} 0 & 0 \\ 1 & 1 \end{matrix})$ y $S^{2} = S \neq X$ .

Con la norma 2 la historia es distinta. Si en lugar de probabilidades usamos vectores $(α, β)$ con $α^{2} + β^{2} = 1$ , una rotación de 45° aplicada dos veces es una rotación de 90°, que lleva $| 0 ⟩$ a $| 1 ⟩$ . No es casualidad: de todas las maneras de medir longitudes, solo una permite transformaciones reversibles continuas.

Teorema (isometrías de

ℓ_{p}

)

Sean $n \geq 2$ y $p \geq 1$ con $p \neq 2$ . Toda aplicación lineal $A : ℝ^{n} \to ℝ^{n}$ que conserva la norma $‖ 𝐱 ‖_{p} = {(\sum_{i} | x_{i} |^{p})}^{1 / p}$ es una matriz de permutación con signos. Para $p = 2$ , en cambio, las isometrías son todas las matrices ortogonales (todas las rotaciones y reflexiones), una familia continua.

El mismo control, dos mundos. Izquierda: un bit probabilístico (norma 1) al que aplicamos dos veces una matriz estocástica de «volteo parcial». Derecha: un vector de norma 2 igual a 1 al que aplicamos dos veces una rotación. Con

t = 0, 5

el bit clásico acaba al 50 %, y esa información se pierde para siempre; el vector acaba exactamente en

| 1 ⟩

: es una raíz cuadrada de NOT. Las líneas discontinuas son la «circunferencia» unidad de cada norma.

La mecánica cuántica es, en su núcleo matemático, lo que se obtiene al dar ese paso: describir el estado de un bit con un vector de norma 2 igual a 1, cuyas componentes pueden ser negativas e incluso complejas. Esas componentes no son probabilidades, sino amplitudes, y las probabilidades son los cuadrados de sus módulos. Eso es el qubit.

Referencias

C. E. Shannon (1938). «A Symbolic Analysis of Relay and Switching Circuits». Transactions of the AIEE, 57(12).
R. Landauer (1961). «Irreversibility and Heat Generation in the Computing Process». IBM Journal of Research and Development, 5(3).
C. H. Bennett (1973). «Logical Reversibility of Computation». IBM Journal of Research and Development, 17(6).
T. Toffoli (1980). «Reversible Computing». ICALP, LNCS 85.
S. Aaronson (2013). Quantum Computing Since Democritus. Cambridge University Press.

§Circuitos booleanos

§La información es física

§Bits como vectores

§Bits probabilísticos

§Referencias

Circuitos booleanos

La información es física

Bits como vectores

Bits probabilísticos

Referencias