Apr 12, 2024 | 2 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} \)
7. Distribuci贸n de probabilidad inicial aleatoria#
En esta secci贸n vamos a ver una generalizaci贸n del algoritmo de Grover para el caso en el que partimos de una distribuci贸n de probabilidad aleatoria (no uniforme). Veremos como este algoritmo generalizado sigue requiriendo un n煤mero de iteraciones \(\mathcal{O}(\sqrt{N/M})\), aunque veremos tambi茅n que hay ciertos casos particularmente desfavorables donde no podemos encontrar ninguna soluci贸n.
Este caso es de especial inter茅s si tenemos en cuenta que muchas veces hay errores al aplicar las puertas. De esta forma, podemos tener errores en el paso de inicializaci贸n de la distribuci贸n uniforme y acabar con una distribuci贸n que se distancia un poco de esta. Como veremos a continuaci贸n, el algoritmo de Grover sigue funcionando en presencia de estos errores modestos.
En la siguientes subsecciones presentaremos el algoritmo y derivaremos las ecuaciones diferenciales que rigen la evoluci贸n de las amplitudes. Usaremos la soluci贸n (exacta) de las mismas para calcular la probabilidad de 茅xito y analizaremos la diferente casu铆stica. Como el c谩lculo, aunque simple, puede hacerse pesado, se incluye al final un resumen de con las conclusiones importantes (secci贸n sec_FTA_grover_prop-no-uni_resumen).
Uno de los puntos importantes del an谩lisis de esta secci贸n es el hecho de demostrar que el algoritmo de Grover funciona incluso en el caso en el que tenemos peque帽os errores a la hora de generar la distribuci贸n de probabilidad inicial. En realidad, en esta secci贸n no se presenta ning煤n algoritmo nuevo. Simplemente se analiza que pasa si usamos el algoritmo de Grover donde en el primer paso sustituimos la inicializaci贸n de la distribuci贸n uniforme por una distribuci贸n no uniforme.
Algoritmo#
En realidad, el algoritmo no tiene ning煤n misterio. Consiste simplemente en saltarse al paso de la inicializaci贸n con las puertas de Hadammard y partir del estado con una distribuci贸n aleatoria:
Utilizar cualquier distribuci贸n inicial, por ejemplo, el estado final de cualquier otro algoritmo cu谩ntico (no inicializar el sistema con la distribuci贸n uniforme).
Aplicar el operador de Grover \(T\) veces (calcularemos \(T\)). El operador de Grover al que nos referimos aqu铆 es el mismo de las anteriores secciones (con la Walsh-Hadammard o con una trasformaci贸n de la forma de la Ec. (71)). No cambia nada en ese sentido.
Medir el resultado
Para conocer m谩s detalles, puede verse [1]
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.
