Apr 12, 2024 | 3 min read

\( \newcommand{\bra}[1]{\langle #1|} \) \( \newcommand{\ket}[1]{|#1\rangle} \) \( \newcommand{\braket}[2]{\langle #1|#2\rangle} \) \( \newcommand{\i}{{\color{blue} i}} \) \( \newcommand{\Hil}{{\cal H}} \) \( \newcommand{\cg}[1]{{\rm C}#1} \) \( \newcommand{\lp}{\left(} \) \( \newcommand{\rp}{\right)} \) \( \newcommand{\lc}{\left[} \) \( \newcommand{\rc}{\right]} \) \( \newcommand{\lch}{\left\{} \) \( \newcommand{\rch}{\right\}} \) \( \newcommand{\Lp}{\Bigl(} \) \( \newcommand{\Rp}{\Bigr)} \) \( \newcommand{\Lc}{\Bigl[} \) \( \newcommand{\Rc}{\Bigr]} \) \( \newcommand{\Lch}{\Bigl\{} \) \( \newcommand{\Rch}{\Bigr\}} \) \( \newcommand{\rqa}{\quad \Rightarrow \quad} \)

6. Consideraciones sobre la implementación

Creación de un difusor \(U_{\Psi_0}\).

Vamos a ver como podemos hacer para crear de forma genérica un difusor de la forma de la Ec. (31). Refrescando un poco la memoria, el difusor es un operador realiza una reflexión respecto al estado inicial \(| \Psi_0 \rangle\), es decir, le cambia el signo a las componentes perpendiculares a \(| \Psi_0 \rangle\). Lo que vamos a hacer para construir el difusor es, en realidad, construir un operador que le cambia el signo a las componentes paralelas a \(| \Psi_0 \rangle\), es decir, vamos a implementar \(-U_{\Psi_0}\).

Empecemos definiendo la familia de operadores de reflexión \(S_A\)

(63)\[\begin{split}\begin{equation} \boxed{S_A | i \rangle = \lch \begin{matrix} & | i \rangle \quad \text{si } i \not \in A \\ & - | i \rangle \quad \text{si } i \in A \end{matrix} \right.} \end{equation} \end{split}\]

Es fácil ver que podemos escribir tanto el oráculo como el difusor en función de los operadores \(S_A\)

(64)\[\begin{align} & U_\omega = S_\omega & \boxed{U_{\Psi_0} = - S_{\Psi_0}} \end{align}\]

Nosotros lo que vamos a construir y implementar es \(S_{\Psi_0}\), no \(U_{\Psi_0}\)

Caso con \(N = 2^n\).

En el caso en el que el estado inicial es una superposición uniforme de la forma la Ec. (8) podemos construir el difusor teniendo en cuenta que

(65)\[\begin{equation} |\Psi_0 \rangle = H^{\otimes n} |0 \rangle \rqa H^{\otimes n} |\Psi_0 \rangle = |0 \rangle. \end{equation}\]

Viendo esta propiedad, podemos darnos cuenta de que si aplicamos el operador de Walsh-Hadamard \(H^{\otimes n}\) a la salida del oráculo lo que obtenemos es el estado \(| 0 \rangle\) más una serie de estado que corresponderán a los cambios respecto al estado inicial que ha realizado el oráculo. Lo que tenemos que hacer para aplicar el difusor es cambiarle el signo al estado \(| 0 \rangle\) (aplicar \(S_0\)) y volver a aplicar \(H^{\otimes n}\) para deshacer los cambios introducidos por la última aplicación el mismo.

Es decir, el difusor será de la forma

(66)\[\begin{equation} U_{\Psi_0} = - S_{\Psi_0}= - H^{\otimes n} S_0 H^{\otimes n} \end{equation}\]

Podemos construir \(S_0\) a partir de la puerta multicontrolada Z (\(MCZ\))

(67)\[\begin{equation} MCZ = \lp \begin{matrix} & 1 & 0 & \dots & 0 & 0 \\ & 0 & 1 & \dots & 0 & 0 \\ & \vdots & \vdots & \ddots & \vdots & \vdots \\ & 0 & 0 & \dots & 1 & 0 \\ & 0 & 0 & \dots & 0 & -1 \\ \end{matrix} \rp \end{equation}\]

que lo que hace es cambiarle el signo al estado \(|2^n-1\rangle= | 11 \dots 1\rangle\).

Tenemos pues

(68)\[\begin{equation} S_0 = X^{\otimes n} (MCZ) X^{\otimes n} \end{equation}\]

La puerta \(X^{\otimes n}\) (que consiste en aplicar puertas \(X\) a todos los qubits) lo que hace es

\[\begin{align*} & |00 \dots 0 \rangle \rightarrow |11 \dots 1 \rangle \, \, \Lc |0 \rangle \rightarrow | 2^n-1 \rangle \Rc \\ & |11 \dots 1 \rangle \rightarrow |00 \dots 0 \rangle \, \, \Lc |2^n-1 \rangle \rightarrow | 0 \rangle \Rc \end{align*}\]

De esta forma, lo que hace \(S_{0}\) es:

• Aplicar la puerta \(X^{\otimes n}\) para cambiar el estado \(|00 \dots 0 \rangle\) por el estado \(|11 \dots 1 \rangle\). (Ver la Nota de abajo)

• Aplicar la puerta \(MCZ\) con la que cambiamos el signo a \(|11 \dots 1 \rangle\)

• Aplicar la puerta \(X^{\otimes n}\) para deshacer los cambios del primer paso. De esta forma, el único cambio real es el del signo del estado \(|0\rangle = |00 \dots 0 \rangle\).

Nota

En realidad la puerta \(X^{\otimes n}\) afecta a todos los estados (no solo a \(|00 \dots 0 \rangle \) y \(|11 \dots 1 \rangle\)). Sin embargo, como es su propia inversa (\(X^{\otimes n}X^{\otimes n} = I\)) y como entre la primera y la segunda aplicación de \(X^{\otimes n}\) lo único que hacemos es cambiarle al signo a \(|11 \dots 1 \rangle\), todos los cambios se deshacen menos este signo, que pasa a estar en el estado \(|00 \dots 0 \rangle \).

Como ya comentamos, el operador que se implementa es \(-U_{\Psi_0}\), es decir

(69)\[\begin{split}\begin{align} & \boxed{-U_{\Psi_0} = S_{\Psi_0} = H^{\otimes n} S_0 H^{\otimes n} = H^{\otimes n} X^{\otimes n} (MCZ) X^{\otimes n} H^{\otimes n}} \Rightarrow \\ & \boxed{G_{imple} = - U_{\Psi_0} U_\omega = - H^{\otimes n} S_0 H^{\otimes n} U_\omega} \end{align} \end{split}\]

Caso con \(N \neq 2^n\).

Las limitación que hemos impuesto hasta ahora diciendo que \(N\) debía ser una potencia de \(2\) viene de la transformación de Walsh-Hadammard

(70)\[\begin{equation} H^{\otimes n} |j \rangle = \frac{1}{\sqrt{N}} \sum^{N-1}_{i=0} (-1)^{i \cdot j} | i \rangle, \qquad \text{ (donde } i \cdot j \text{ denota el producto escalar binario)} \end{equation}\]

Esta transformación, que se usa para generar el estado inicial y se en el difusor, no está bien definida si no se cumple que \(N=2^n\).

Esta condición puede ser relajada si sustituimos la transformación de Walsh-Hadammard por cualquier otra transformación unitario \(F\) que cumpla

(71)\[\begin{equation} \boxed{F |0 \rangle = \frac{1}{\sqrt{N}} \sum^{N-1}_{i=0} | i \rangle} \end{equation} \]

y seguiremos teniendo interaciones de Grover válidas aplicando

(72)\[\begin{equation} F S_0 F^{-1} U_\omega \end{equation}\]

De hecho, cuando estamos en el caso \(N = 2^n\), la Walsh-Hadammard es simplemente la elección más sencilla de \(F\). Para el caso en el que \(N\) no es una potencia de dos, podemos usar la transformación de Fourier de Kitaev [5]. Puede verse también [4]

---

Autores:

David Castaño (UMA-SCBI), Raul Fuentes (BSC-CNS), Daniel Talaván (COMPUTAEX), Francisco Matanza (UNICAN)

---

License: Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

This work has been financially supported by the Ministry for Digital Transformation and of Civil Service of the Spanish Government through the QUANTUM ENIA project call - Quantum Spain project, and by the European Union through the Recovery, Transformation and Resilience Plan - NextGenerationEU within the framework of the Digital Spain 2026 Agenda.