Puertas y circuitos: Programar con matrices unitarias

En 1985 David Deutsch, en Oxford, definió el ordenador cuántico universal: una máquina de Turing cuyos estados pueden estar en superposición. El modelo que se impuso, sin embargo, fue el que él mismo desarrolló en 1989: los circuitos cuánticos, cables que transportan qubits y puertas que los transforman. Es el lenguaje en el que hoy se escriben todos los algoritmos cuánticos.

Las puertas son matrices unitarias

Teorema (caracterización de los unitarios)

Para una matriz $U \in ℂ^{d \times d}$ son equivalentes: (1) $U^{†} U = I$ ; (2) $U$ conserva los productos interiores, $⟨ U ϕ | U ψ ⟩ = ⟨ ϕ | ψ ⟩$ ; (3) $U$ conserva las normas, $‖ U ψ ‖ = ‖ ψ ‖$ ; (4) las columnas de $U$ forman una base ortonormal.

Demostración

(1)⇒(2): $⟨ U ϕ | U ψ ⟩ = ⟨ ϕ | U^{†} U | ψ ⟩ = ⟨ ϕ | ψ ⟩$ . (2)⇒(3) es el caso $ϕ = ψ$ . (3)⇒(2) usa la identidad de polarización, que recupera el producto interior a partir de normas: $⟨ ϕ | ψ ⟩ = \frac{1}{4} \sum_{k = 0}^{3} i^{- k} ‖ ϕ + i^{k} ψ ‖^{2}$ . (2)⇔(4): las entradas de $U^{†} U$ son los productos interiores de las columnas. (4)⇒(1) por el mismo motivo.

Las puertas de un qubit más habituales son las matrices de Pauli, la puerta de Hadamard y las puertas de fase:

X, Y, Z, H = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}), S = (\begin{matrix} 1 & 0 \\ 0 & i \end{matrix}), T = (\begin{matrix} 1 & 0 \\ 0 & e^{i π / 4} \end{matrix}) .

En la esfera de Bloch, toda puerta de un qubit es una rotación. $X$ , $Y$ y $Z$ son medias vueltas alrededor de cada eje; $H$ es media vuelta alrededor del eje situado entre $x$ y $z$ ; $S$ y $T$ son un cuarto y un octavo de vuelta alrededor de $z$ .

Teorema (descomposición de Euler)

Todo unitario $U \in ℂ^{2 \times 2}$ se puede escribir como

U = e^{i α} R_{z} (β) R_{y} (γ) R_{z} (δ), R_{z} (θ) = e^{- i θ Z / 2}, R_{y} (θ) = e^{- i θ Y / 2},

para ciertos reales $α, β, γ, δ$ : cualquier rotación de la esfera es una composición de rotaciones alrededor de $z$ , $y$ y $z$ .

Dos qubits: CNOT

La puerta NOT controlada invierte el segundo qubit (el objetivo) solo si el primero (el control) vale 1. En la base $| 00 ⟩, | 01 ⟩, | 10 ⟩, | 11 ⟩$ :

CNOT = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}), CNOT (H \otimes I) | 00 ⟩ = \frac{| 00 ⟩ + | 11 ⟩}{\sqrt{2}} = | Φ^{+} ⟩ .

Una Hadamard seguida de una CNOT crea entrelazamiento desde cero. Pruébalo en el simulador.

Un simulador de circuitos de tres qubits. Haz clic en una celda para recorrer las puertas; un ● en una columna convierte las demás puertas de esa columna en puertas controladas (● más ⊕ es una CNOT; ●●⊕ es una Toffoli). Las barras muestran las

2^{3} = 8

amplitudes del estado final: la altura es la probabilidad y el color, la fase. Los ejemplos incluyen un par de Bell, un estado GHZ y el algoritmo de Deutsch-Jozsa.

Universalidad

En el mundo clásico, NAND basta para construirlo todo. ¿Hay un conjunto cuántico finito que también baste? La respuesta llega en dos pasos.

Teorema (universalidad exacta; Barenco et al., 1995)

Todo unitario sobre $n$ qubits se puede escribir exactamente como producto de puertas CNOT y puertas de un qubit.

Pero hay infinitas puertas de un qubit, y un dispositivo real solo puede implementar unas pocas con alta precisión. Por suerte, aproximar basta, y sale barato:

Teorema (Solovay-Kitaev, 1995–1997)

Sea $𝒢$ un conjunto finito de puertas de un qubit, cerrado por inversos, que genera un subgrupo denso de $S U (2)$ (por ejemplo ${H, T, T^{†}}$ ). Entonces toda puerta de un qubit se puede aproximar con precisión $ε$ mediante un producto de $O (\log^{c} (1 / ε))$ puertas de $𝒢$ , con $c \approx 4$ (versiones mejoradas llegan a $c < 2$ ).

Juntas, ${H, T, CNOT}$ forman un conjunto universal: cualquier cálculo cuántico se puede aproximar con un sobrecoste polilogarítmico.

No todo circuito cuántico es potente

La superposición y el entrelazamiento son necesarios para una ventaja cuántica, pero no suficientes. Los circuitos construidos con $H$ , $S$ y CNOT (el grupo de Clifford) pueden generar estados muy entrelazados y, aun así:

Teorema (Gottesman-Knill, 1998)

Un circuito que parte de $| 0 \dots 0 ⟩$ , usa solo puertas de Clifford y mide en la base computacional se puede simular con un ordenador clásico en tiempo polinómico en el número de qubits y de puertas.

El truco es describir el estado no por sus $2^{n}$ amplitudes, sino por los $n$ operadores de Pauli que lo dejan invariante (sus estabilizadores), que las puertas de Clifford transforman unos en otros. La potencia de un ordenador cuántico viene de añadir puertas no Clifford como $T$ , que además son las más caras de proteger frente a errores.

Deutsch-Jozsa: la primera separación exponencial

Supongamos que nos prometen que una función $f : {0, 1}^{n} \to {0, 1}$ es constante o equilibrada (vale 0 en exactamente la mitad de las entradas). Un algoritmo clásico determinista puede necesitar $2^{n - 1} + 1$ consultas para estar seguro. El algoritmo de Deutsch y Jozsa (1992) necesita una sola:

{| 0 ⟩}^{\otimes n} \overset{H^{\otimes n}}{⟶} \frac{1}{\sqrt{2^{n}}} \sum_{x} | x ⟩ \overset{U_{f}}{⟶} \frac{1}{\sqrt{2^{n}}} \sum_{x} (- 1)^{f (x)} | x ⟩ \overset{H^{\otimes n}}{⟶} \dots

La amplitud de $| 0 \dots 0 ⟩$ al final es $\frac{1}{2^{n}} \sum_{x} (- 1)^{f (x)}$ : vale $\pm 1$ si $f$ es constante y exactamente 0 si es equilibrada. Medir todo ceros o no responde la pregunta con certeza. Un algoritmo clásico aleatorio puede responder con alta probabilidad usando unas pocas consultas, así que la separación es frente a algoritmos deterministas; pero la idea (poner la información en las fases y hacerla interferir) es la plantilla de todo lo que sigue.

Complejidad cuántica

En 1993 Ethan Bernstein y Umesh Vazirani definieron BQP, la clase de problemas que un ordenador cuántico resuelve en tiempo polinómico con probabilidad de error como mucho $1 / 3$ . También demostraron que

BPP \subseteq BQP \subseteq PSPACE .

La primera inclusión dice que los ordenadores cuánticos pueden hacer todo lo que hacen los clásicos aleatorios (gracias a Toffoli); la segunda, que se pueden simular con memoria polinómica, sumando sobre caminos. No se sabe si alguna de las inclusiones es estricta: demostrar $BPP \neq BQP$ implicaría $P \neq PSPACE$ , un gran problema abierto. La evidencia del poder cuántico son, por ahora, algoritmos como el de Shor para problemas que creemos difíciles para los ordenadores clásicos.

Referencias

D. Deutsch (1985). «Quantum theory, the Church–Turing principle and the universal quantum computer». Proceedings of the Royal Society A, 400.
D. Deutsch y R. Jozsa (1992). «Rapid solution of problems by quantum computation». Proceedings of the Royal Society A, 439.
E. Bernstein y U. Vazirani (1993). «Quantum complexity theory». STOC (versión de revista: SIAM J. Computing, 1997).
A. Barenco et al. (1995). «Elementary gates for quantum computation». Physical Review A, 52(5).
D. Gottesman (1998). «The Heisenberg Representation of Quantum Computers». arXiv:quant-ph/9807006.
C. M. Dawson y M. A. Nielsen (2006). «The Solovay-Kitaev algorithm». Quantum Information and Computation, 6(1).

§Las puertas son matrices unitarias

§Dos qubits: CNOT

§Universalidad

§No todo circuito cuántico es potente

§Deutsch-Jozsa: la primera separación exponencial

§Complejidad cuántica

§Referencias