Introducción a la computación cuántica con Qiskit

Introducción a algoritmos cuánticos

Un algoritmo cuántico no prueba todas las respuestas a la vez y elige la correcta: esa es la idea equivocada más común. Lo que hace es preparar una superposición, manipular las fases de las amplitudes y usar la interferencia para que las respuestas incorrectas se cancelen y la correcta se refuerce. En esta lección verás ese patrón en tres algoritmos clásicos del área.

El patrón común

Casi todos los algoritmos introductorios siguen cuatro pasos:

1. Superposición: aplicar Hadamard a todos los qubits para cubrir todas las entradas posibles.
2. Oráculo: una caja negra que marca las entradas que interesan, normalmente cambiando su fase.
3. Interferencia: más puertas, a menudo Hadamard, que convierten las diferencias de fase en diferencias de probabilidad.
4. Medición: leer el resultado, que ahora es la respuesta con alta probabilidad.

El oráculo es la función que se quiere estudiar, implementada como circuito. La ventaja cuántica se mide en cuántas veces hay que consultarlo.

Deutsch-Jozsa y Bernstein-Vazirani

El algoritmo de Deutsch-Jozsa (1992) decide con una sola consulta si una función es constante o balanceada; una computadora clásica determinista puede necesitar consultar más de la mitad de las entradas. Su pariente, Bernstein-Vazirani, encuentra una cadena secreta $s$ oculta en la función $f(x) = s \cdot x \bmod 2$. Clásicamente se necesitan $n$ consultas, una por bit. Con un circuito cuántico basta una:

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

secreto = "101"
n = len(secreto)
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
for i, bit in enumerate(reversed(secreto)):
    if bit == "1":
        qc.cx(i, n)
qc.h(range(n))
qc.measure(range(n), range(n))

conteos = StatevectorSampler(seed=3).run([qc], shots=100).result()[0].data.c.get_counts()
print(conteos)

Los 100 disparos devuelven 101. El qubit extra empieza en $|-\rangle$, y cada cx del oráculo devuelve una fase negativa a las entradas donde $s \cdot x$ es impar. Este truco se llama retroceso de fase (phase kickback). Las Hadamard finales convierten ese patrón de fases en la cadena secreta.

Grover: búsqueda con amplificación

El algoritmo de Grover busca un elemento marcado entre $N$ posibilidades con unas $\frac{\pi}{4}\sqrt{N}$ consultas. Cada iteración aplica el oráculo, que invierte la fase del elemento buscado, y un difusor, que refleja las amplitudes respecto a su promedio. Con dos qubits ($N = 4$), una sola iteración encuentra el elemento con certeza:

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

qc = QuantumCircuit(2)
qc.h([0, 1])
qc.cz(0, 1)          # oráculo: marca el estado 11
qc.h([0, 1])
qc.x([0, 1])
qc.cz(0, 1)          # difusor: inversión respecto al promedio
qc.x([0, 1])
qc.h([0, 1])
print(Statevector(qc).probabilities_dict(decimals=3))

El resultado es 11 con probabilidad 1.0; los otros tres estados quedan en cero. Con listas más grandes, el número de iteraciones importa: si se hacen de más, la probabilidad vuelve a bajar.

Shor: la motivación histórica

El algoritmo de Shor factoriza enteros reduciendo el problema a encontrar el período de una función. Para eso usa la transformada cuántica de Fourier, que extrae períodos con eficiencia exponencialmente mayor que los métodos clásicos conocidos. Su ejecución a escala útil requiere miles de qubits lógicos con corrección de errores, algo que todavía no existe. Por eso, en el curso trabajarás con algoritmos que sí caben en simuladores y en el hardware actual.

Trampas comunes

• "Prueba todas las respuestas en paralelo". Al medir obtienes una sola; la ventaja viene de la interferencia.
• Ignorar el costo del oráculo. Si construir el oráculo es tan caro como resolver el problema, no hay ventaja.
• Iterar Grover de más. Pasarse del número óptimo reduce la probabilidad de éxito.
• Leer la cadena al revés. En Bernstein-Vazirani, el bit 0 del secreto controla el qubit 0, que aparece a la derecha.

Cierre

Cuando leas un algoritmo nuevo, busca los cuatro pasos: superposición, oráculo, interferencia y medición. Cambia la cadena secreto del ejemplo por otra de cinco bits y comprueba que el circuito la recupera con una sola consulta.