Fundamento teórico Deutsch–Jozsa
Algoritmo de Deutsch-Jozsa: consulta cuántica única al oráculo y discriminación por interferencia
El algoritmo de Deutsch-Jozsa, formulado por David Deutsch y Richard Jozsa en 1992, fue históricamente el primer algoritmo cuántico en demostrar una ventaja exponencial sobre cualquier algoritmo clásico determinista para un problema bien definido. Su importancia radica no solo en el resultado práctico, sino en que introdujo el paradigma de computación asistida por oráculo que subyace a algoritmos más poderosos como el de Grover y el de Shor.
Matemáticamente, el problema es una promesa sobre una función booleana \(f: \{0,1\}^n \to \{0,1\}\): o bien es constante, o bien equilibrada en el sentido combinatorio habitual. La solución cuántica explota la interferencia inducida por \(H^{\otimes n}\) antes y después de un oráculo de fase obtenido mediante ancilla en \(|{-}\rangle\). En simuladores HarmoniQ, la lectura del bit de salida tras ruido de puerta exige distinguir la probabilidad residual en el estado «incorrecto» de fluctuaciones de muestreo finito.
Fundamento teórico
El problema de promesa
Se considera una función booleana \(f: \{0,1\}^n \to \{0,1\}\) sobre la que se garantiza (promesa) que pertenece a exactamente una de dos clases:
- Constante: \(f(x) = c\) para todo \(x \in \{0,1\}^n\), con \(c \in \{0,1\}\).
- Balanceada: \(f\) retorna \(0\) exactamente en la mitad de las entradas y \(1\) en la otra mitad.
El objetivo es determinar a cuál de las dos clases pertenece \(f\) consultando al oráculo \(\mathcal{O}_f\) el menor número posible de veces. Un algoritmo clásico determinista necesita, en el peor caso, \(2^{n-1} + 1\) consultas para distinguir ambas clases. El algoritmo cuántico de Deutsch-Jozsa lo resuelve con exactamente una consulta, independientemente de \(n\).
El oráculo cuántico de fase
El oráculo cuántico implementa la función \(f\) como una operación unitaria sobre dos registros: el registro de entrada \(|x\rangle\) y un cúbit ancilla \(|a\rangle\): \[ \mathcal{O}_f : |x\rangle|a\rangle \mapsto |x\rangle|a \oplus f(x)\rangle, \] donde \(\oplus\) denota la suma módulo 2. Inicializando la ancilla en \(|{-}\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}\), el oráculo produce la transformación de phase kickback: \[ \mathcal{O}_f |x\rangle|{-}\rangle = (-1)^{f(x)}|x\rangle|{-}\rangle. \] El estado de la ancilla no cambia; solo adquiere una fase global relativa al valor de \(f(x)\), que queda codificada en la amplitud del registro de entrada.
Ventaja cuántica y transformada de Hadamard
La clave es aplicar la transformada de Hadamard \(H^{\otimes n}\) al registro de entrada antes y después del oráculo. La transformada de Hadamard sobre \(n\) cúbits mapea cada estado de la base a la superposición: \[ H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} (-1)^{x \cdot y}|y\rangle, \] donde \(x \cdot y\) es el producto interior bit a bit. La composición \(H^{\otimes n} \circ \mathcal{O}_f \circ H^{\otimes n}\) produce una interferencia constructiva en \(|0\rangle^{\otimes n}\) si \(f\) es constante y destructiva si \(f\) es balanceada:
\[ \text{Estado final del registro de entrada} = \frac{1}{2^n}\sum_{y}\left(\sum_x (-1)^{f(x)+x\cdot y}\right)|y\rangle. \] Si \(f\) es constante, la amplitud de \(|0\rangle^{\otimes n}\) es \(\pm 1\) y la probabilidad de medirlo es 1. Si \(f\) es balanceada, la amplitud de \(|0\rangle^{\otimes n}\) es 0 y la probabilidad de medirlo es 0. Una única medición basta para discriminar ambos casos.
Complejidad de consulta y comparación con algoritmos clásicos
En el modelo de consulta al oráculo, el coste se mide únicamente por el número de llamadas a \(\mathcal{O}_f\). Cualquier algoritmo clásico determinista que distinga funciones constantes de balanceadas requiere, en el peor caso, \(2^{n-1}+1\) consultas: hasta \(2^{n-1}\) respuestas idénticas no descartan la clase balanceada. El algoritmo cuántico exhibido usa una sola consulta cuántica al oráculo en el registro adecuadamente preparado.
Un algoritmo clásico aleatorio puede resolver el problema en \(\mathcal{O}(1)\) consultas esperadas muestreando entradas al azar hasta hallar dos valores distintos de \(f\) o agotar un criterio de parada; por ello la separación cuántico–clásico más honesta se formula en el régimen determinista o contra oráculos adversos. La lección pedagógica permanece: la interferencia cuántica global puede condensar en una medición la información que clásicamente exige exploración extensiva del dominio.
Si \(f\) es constante, la suma es \(\pm 2^n\) y la amplitud de \(|0\rangle^{\otimes n}\) tiene módulo unidad. Si \(f\) es balanceada, los términos se cancelan par a par y dicha amplitud es nula. Esta dicotomía es puramente algebraica y no depende de la representación interna del oráculo, siempre que implemente la fase \((-1)^{f(x)}\) sobre la superposición uniforme.
Implementación en \(n\) cúbits y robustez frente a ruido
La extensión a \(n > 1\) mantiene la estructura: preparación de ancilla en \(|{-}\rangle\), superposición uniforme en el registro de datos, oráculo de fase, segunda capa Hadamard y medición en la base computacional. La profundidad del circuito crece con la descomposición del oráculo \(U_f\) en puertas nativas; en la práctica, la ventaja asintótica puede verse erosionada por tasas de error por puerta y por decoherencia antes de que \(n\) alcance valores interesantes en hardware ruidoso.
En HarmoniQ, los backends Hopper y Hermann modelan ruido phenomenológico en puertas; la fidelidad compuesta de la secuencia de cinco puertas del ejemplo de dos cúbits permite cuantificar la probabilidad residual en el estado no deseado y compararla con la varianza estadística \(\mathcal{O}(1/\sqrt{N_{\text{shots}}})\) del estimador de frecuencias.
Circuito cuántico (2 cúbits, función balanceada \(f(x)=x\))
En la implementación de 2 cúbits, \(q_0\) es el registro de entrada (\(n=1\) bit) y \(q_1\) es la ancilla. El oráculo para la función balanceada \(f(x) = x\) se implementa con una puerta CNOT con control en \(q_0\) y objetivo en \(q_1\).
Paso 1 — Preparación de la ancilla: \(q_1\) se lleva a \(|1\rangle\) con la puerta X y luego a \(|{-}\rangle\) con Hadamard. Esto activa el mecanismo de phase kickback.
Paso 2 — Superposición del registro de entrada: \(q_0\) se lleva a \(|{+}\rangle\) con Hadamard, creando el estado global \(|{+}\rangle|{-}\rangle = \frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)\).
Paso 3 — Oráculo (CNOT): implementa \(f(x)=x\) (función balanceada). El phase kickback transforma \(|{+}\rangle\) en \(|{-}\rangle\) en el registro de entrada.
Paso 4 — Hadamard de inversión: transforma \(|{-}\rangle\) de nuevo a
\(|1\rangle\), por lo que la medición de \(q_0\) siempre produce 1 → función
balanceada. Si se usara un oráculo constante, el resultado sería siempre 0.
Implementación en HarmoniQ
La secuencia de puertas es: x en \(q_1\), h en \(q_0\),
h en \(q_1\), cnot (control \(q_0\), objetivo \(q_1\)) y
finalmente h en \(q_0\). Solo \(q_0\) se mide. La ancilla \(q_1\) no se
incluye en el resultado de interés.
Swift
DeutschJozsa.swift
import HarmoniQ
// Oráculo para función balanceada f(x) = x
let gates: [Gate] = [
Gate(name: "x", targets: [1]), // ancilla → |1⟩
Gate(name: "h", targets: [0]), // entrada en superposición
Gate(name: "h", targets: [1]), // ancilla → |−⟩
Gate(name: "cnot", targets: [1], controls: [0]), // oráculo
Gate(name: "h", targets: [0]), // inversión
]
do {
let result = try await HarmoniQ.quantum.executeCircuit(
provider: "hopper",
shots: 1024,
qubits: 2,
bits: 2,
gates: gates,
basis: "Z"
)
// Balanceada → q₀ = 1 → estado "10" dominante
// Constante → q₀ = 0 → estado "00" dominante
let dominant = result.mostFrequent
let tipo = dominant.hasPrefix("0") ? "Constante" : "Balanceada"
print("Función: \(tipo)")
} catch {
print("Error:", error)
}
Kotlin
DeutschJozsa.kt
import com.planq.harmoniq.HarmoniQ
import com.planq.harmoniq.model.Gate
val gates = listOf(
Gate(name = "x", targets = listOf(1)),
Gate(name = "h", targets = listOf(0)),
Gate(name = "h", targets = listOf(1)),
Gate(name = "cnot", targets = listOf(1), controls = listOf(0)),
Gate(name = "h", targets = listOf(0)),
)
viewModelScope.launch {
val result = HarmoniQ.quantum.executeCircuit(
provider = "hopper",
shots = 1024,
qubits = 2,
bits = 2,
gates = gates,
basis = "Z"
)
val tipo = if (result.mostFrequent.startsWith("0")) "Constante" else "Balanceada"
Log.d("DJ", "Función: $tipo | Distribución: ${result.counts}")
}
React / TypeScript
deutschJozsa.ts
import { HarmoniQ } from './lib/quantum'
import type { Gate } from '@planq/harmoniq'
const gates: Gate[] = [
{ name: 'x', targets: [1] },
{ name: 'h', targets: [0] },
{ name: 'h', targets: [1] },
{ name: 'cnot', targets: [1], controls: [0] },
{ name: 'h', targets: [0] },
]
const result = await HarmoniQ.quantum.executeCircuit({
provider: 'hopper',
shots: 1024,
qubits: 2,
bits: 2,
gates,
basis: 'Z',
})
const tipo = result.mostFrequent.startsWith('0') ? 'Constante' : 'Balanceada'
console.log(`Función: ${tipo}`, result.counts)
Python
deutsch_jozsa.py
from harmoniq import HarmoniQ, Gate
gates = [
Gate(name="x", targets=[1]),
Gate(name="h", targets=[0]),
Gate(name="h", targets=[1]),
Gate(name="cnot", targets=[1], controls=[0]),
Gate(name="h", targets=[0]),
]
result = HarmoniQ.quantum.execute_circuit(
provider="hopper",
shots=1024,
qubits=2,
bits=2,
gates=gates,
basis="Z",
)
tipo = "Constante" if result.most_frequent.startswith("0") else "Balanceada"
print(f"Función: {tipo}")
print("Distribución:", result.counts)Análisis de resultados
Dado que este ejemplo implementa la función balanceada \(f(x) = x\), el estado final de \(q_0\) es \(|1\rangle\) con probabilidad teórica 1. Los resultados esperados tras 1024 shots son:
| Estado | Función | Probabilidad ideal | Conteo típico |
|---|---|---|---|
|10⟩ | Balanceada | 1.000 | 990 – 1024 |
|00⟩ | Constante | 0.000 | 0 – 34 |
Los conteos en |00⟩ con función balanceada son únicamente debidos al ruido
del simulador. Para evaluar la fidelidad del algoritmo se puede calcular la
tasa de éxito:
\[\text{Fidelidad} = \frac{\text{conteo}(|10\rangle)}{N_{\text{shots}}}.\]
Con el backend Hopper, la fidelidad típica supera el 97%, coherente con la composición de
errores de las cinco puertas empleadas.
Para cambiar al oráculo constante (\(f(x) = 0\)) basta con eliminar la puerta CNOT de la
lista de puertas. En ese caso, el estado dominante será |00⟩.
Referencias y lecturas recomendadas
La selección siguiente orienta al lector hacia monografías y recursos cuya rigurosidad ha sido contrastada por la comunidad científica; complementa la bibliografía citada al pie de esta guía.
- IBM Quantum Plataforma experimental y documentación orientada a circuitos y calibración. Abrir
- Qiskit Textbook Texto abierto con derivaciones paso a paso y ejercicios numéricos. Abrir
- Microsoft Learn · Azure Quantum Fundamentos y modelos de programación cuántica en entornos administrados. Abrir
- arXiv · quant-ph Prepublicaciones recientes en información cuántica y computación cuántica. Abrir
- NIST · Quantum information Marcos metrológicos y estándares en ciencia cuántica aplicada. Abrir
-
Nielsen & Chuang Quantum Computation and Quantum Information (Cambridge University Press). Obra de referencia para demostraciones formales, complejidad cuántica y códigos correctores.
Bibliografía citada
-
[1]
Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A, 439(1907), 553–558.
-
[2]
Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 400(1818), 97–117.
-
[3]
Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press. Sección 1.4.3.
-
[4]
Cleve, R., Ekert, A., Macchiavello, C., & Mosca, M. (1998). Quantum algorithms revisited. Proceedings of the Royal Society of London A, 454(1969), 339–354.