Introducción a la computación cuántica y la tecnologia blockchain 3

El algoritmo de Grover’s

Lov Grover publicó un artículo en 1996 que describe el algoritmo de Grover. La aplicación del algoritmo de Grover a búsquedas no estructuradas proporciona una mejora en los tiempos proporcionados por la medida de la complejidad O(n) . Si desea buscar un elemento en una base de datos y si los datos no están ordenados, el uso del algoritmo de Grover implementado en computadoras cuánticas puede proporcionar un mejor rendimiento que las computadoras clásicas.
Cuando un item de una base de datos no estructurada tiene que ser identificado a partir de N nombres dentro de una base de datos, y si los nombres han sido ordenados, una computadora clásica podría realizar una búsqueda binaria para encontrar el item en tiempo logarítmico.

O(n) = log(n)

Si los items no estuvieran ordenados, la búsqueda implica buscar hasta el item N-1 para encontrar el correcto.

Si Sa es el item que estamos tratando de encontrar en la base de datos de N elementos, usando el algoritmo de Grover podemos ayudar a resolver el problema con √𝑁 intentos. Los qubits son preparados para que todos los números estén en superposición uniforme utilizando una puerta Hadamard. Medir los qubits en esta etapa mostraría que todos los resultados eran igualmente probables:

Logrando amplitudes uniformes

La siguiente ecuación representa la magnitud uniforme de todas las cadenas:

Ahora, se aplica a un oraculo cuantico (funcion oracle) para invertir la amplitud de Sa y dejar el resto sin alterar:

El gráfico ahora se puede representar como:

Invirtiendo la amplitud de la cadena que coincide con la busqueda

Ahora la amplitud del elemento deseado Sa se ha invertido (a negativo). Por lo tanto, la media de las amplitudes 𝜇 se habría reducido. Aquí es donde el operador de difusión de Grover es introduido para aumentar absolutamente la amplitud de Sa.

Todo lo que hace este operador es cambiar las amplitudes al promedio. Esto resulta en que la amplitud de Sa aumenta a aproximadamente 3 / √𝑁 en magnitud. Las amplitudes se parecen como se muestra en el siguiente diagrama:

Invirtiendo amplitudes al promedio

Este proceso de aplicar el oraculo cuantico y la puerta de difusión de Grover se repite
hasta que la amplitud sea lo suficientemente significativa. También se debe tener cuidado de que la amplitud de Sa no es demasiado grande para que la amplitud media se vuelva negativa, lo que a su vez comenzará reduciendo la amplitud de Sa. En el punto en que la amplitud es casi uno, la medición de los qubits proporcionará la respuesta correcta. Se puede demostrar que este proceso, cuando se repite durante aproximadamente √𝑁, proporciona resultados precisos.

Conclusión: los algoritmos de Shor y Grover sentaron las bases de la computacion cuántica para casos de uso prácticos identificados por lo que estos algoritmos pueden ayudar a resolver.
Ahora pasaremos al recocido cuántico, que es una técnica utilizada para abordar
problemas de optimización.

temple cuantico

Hemos visto cómo la superposición de qubits lograda mediante operaciones que utilizan puertas puede resolver problemas del mundo real. Hay otros métodos para llegar a una solucion de optimización. El temple cuántico es el proceso de llegar a mínimos globales utilizando fluctuaciones cuánticas. El efecto túnel puede ayudar con la transición
entre estados en un temple cuántico.
Durante el proceso de temple cuántico, la información necesaria para la optimización
se modela en un sistema físico. Este proceso implica codificar un problema de optimización de varias variables correlacionadas en un sistema físico (representado por
qubits en superposición).

La solución al problema está representada por el estado de energía mínima del sistema,
y la función más simple utilizada para lograr esto se llama hamiltoniano. El temple Cuántico impulsado por el efecto túnel puede abordar problemas en logística por ejemplo.

el efecto tunel

El túnel cuántico es una propiedad cuántica donde las partículas pasan a través sistemas energéticos. En la física clásica, cuando un electrón encuentra un campo eléctrico, se repele si el campo eléctrico es más fuerte que el del electrón. Problemas que se resuelven mediante el temple cuántico se basan en la propiedad de túnel cuántico de partículas.

Electrón acercándose a un campo eléctrico
Electron repelido por un campo electrico
Onda del electron moviendose a traves de un campo electrico

El efecto tunel es una propiedad que fue observada por Friedrich Hund en 1927. Si un electrón que viaja como una onda se encuentra con un campo eléctrico que la repele, todavía hay una probabilidad de que pase a través del campo eléctrico y se encuentre en el otro lado del campo. Las partículas subatómicas muestran propiedades de efecto túnel durante una desintegración radiactiva, cuando las partículas escapan de un núcleo inestable. El temple cuántico es un proceso que depende de las propiedades del efecto tunel. Veamos un ejemplo práctico en el que se puede utilizar el temple cuántico.

el problema del viajante

El problema del viajante es una aplicación bien documentada del efecto tunel cuantico. Digamos que tenemos un vendedor que vende productos en todo el país. La ruta optima para que viaje por el país dependerá de la cantidad de ciudades en el país. Si el país tiene tres ciudades (A, B y C), la ruta óptima podría ser A -> B -> C o A -> C -> B o B -> A -> C o B -> C -> A o C -> A-> B o C -> B -> A. El número de rutas posibles (6) depende del número de ciudades aquí (3). El número de rutas posibles puede estar dado por el factorial del número de ciudades:

3! = 3 * 2 * 1 = 6

Cuando el número de ciudades se duplica a 6, el número de rutas posibles sería 6! = 720, que es un aumento drástico. Aparte del aumento del número de ciudades, podría haber otros problemas, como atascos de tráfico en un momento determinado o una carretera particularmente mala. Por lo tanto, la ruta óptima puede no ser necesariamente la ruta más corta. Primero necesitamos configurar el sistema para identificar la solución óptima.
Preparemos el sistema en una superposición cuántica para el problema de muchas soluciones posibles. El sistema ahora puede verse como un paisaje de picos y valles.
Los picos son estados de alta energía y son costosos energeticamente hablando. Los valles, por otro lado, representan estados de baja energía. A medida que hacemos la transición entre un valle y otro, la probabilidad de cada solución evoluciona. Las opciones de menor energía se convierten en la solución más probable, hasta que la solución de mayor probabilidad se identifique como la solución óptima.

En el temple simulado, el calor se utiliza para pasar por los picos y la transición entre valles. Con los temples cuánticos, el efecto túnel nos permite pasar los picos de alta energía a través de túneles en lugar de subirlos, como en el temple simulado. El temple cuántico es impulsado por un campo magnético externo que desempeña el papel de
la temperatura en el temple simulado: el temple cuántico comienza con un gran campo magnético (alta temperatura) y termina con un campo magnético bajo (baja temperatura).
El temple cuántico es el proceso de alimentar la información necesaria para la optimización en un sistema físico. Se definirá la solución al problema por el estado fundamental (estado de energía más bajo) del sistema. La función utilizada para este proceso se llama hamiltoniano, que gestiona la información sobre los niveles de energía del sistema.
Podemos utilizar el hamiltoniano para gestionar los niveles de energía del sistema en función de un marco de restricciones. En el problema del viajante, podemos tener mayores niveles de energía asignados a distancias más largas, carreteras en mal estado, atascos y cierres de carreteras. La ruta óptima sería la de menor nivel de energía. Considerando esto, ¿Cómo identificamos la solución de energía más baja?
El hamiltoniano y los términos que le agregamos para aumentar los niveles de energía,
crearía picos y valles en el espacio energético. Necesitamos encontrar los tuneles sin tener que subir los niveles máximos de energía. Esto se puede lograr mediante la tunelización, como se describe anteriormente. Si bien esto nos permite pasar de un canal a otro, ¿cómo podemos identificar la depresión más baja? Una técnica cuántica llamada computación cuántica adiabatica se puede utilizar para este propósito.
El término adiabático proviene de la teoría de la termodinámica y significa sin cambio en la cantidad de calor. En este proceso, el sistema se inicializa con el estado de base, y luego evoluciona lentamente hacia hamiltonianos más complejos cuyos estados de base codifican la solución.
Cada hamiltoniano codifica la asignación correcta de variables asignando una penalización de energía a todas las configuraciones incorrectas. Los picos del paisaje tienen una penalizacion más alta y los valles tienen una pena más baja. La solucion optima con el nivel de energía más bajo generalmente tiene un valor propio de 0. Podemos evolucionar el sistema en el tiempo para que:

H(s) = (1 − s) H 0 + sH 1

En el tiempo s = 1, el hamiltoniano es H (1) = Hs, y el sistema estará en su estado fundamental si la evolución ha sido lenta. Los valores propios y los vectores propios se utilizan en varios algoritmos del mundo real. Se utilizan para modelar la física de cuerpos en rotación, oscilaciones de sistemas vibrantes y en modelización de riesgos en bancos de inversión.

Los valores propios (Eigenvalues) se definen a continuación por Hoffman y Kunze (1971):

Los valores propios son un conjunto especial de escalares asociados con un sistema lineal de ecuaciones. (en otras palabras, una ecuación matricial) que a veces también se conocen como raices características, valores característicos (Hoffman y Kunze 1971), valores propios o raices de valores latentes (Marcus y Minc 1988, p. 144)

Reference: http://mathworld.wolfram.com/Eigenvalue.html

El temple cuántico se puede utilizar para resolver problemas de optimización. Sin embargo, podemos no tener que esperar a que las computadoras cuánticas utilicen los principios del temple cuántico y túneles cuánticos para lograr resultados. Fujitsu ya ha creado un “Quantum annealer” digital inspirado para resolver desafiantes problemas de optimización en gestion de riesgo financiero y reequilibrio de la cartera financiera.


Conclusión: el recocido cuántico se puede utilizar para optimizar problemas en varias industrias. Finanzas, logística, salud y ciudades inteligentes son áreas donde estas técnicas se pueden utilizar para optimizar problemas complejos. A pesar de todas estas increíbles posibilidades con las técnicas cuánticas, la decoherencia es un gran reto. Veamos eso a continuación:

decoherencia

Discutimos el experimento de la doble rendija anteriormente, donde vimos que los fotones se movían a través de las rendijas y se comportaron como ondas (interfiriendo con ellos mismos), a pesar de que se enviaron una a la vez. Cuando una partícula exhibe las propiedades de una onda, donde interfiere consigo misma, se dice que es coherente. La decoherencia es la pérdida o la supresión de coherencia en un sistema. La función de onda que explica el comportamiento de la partícula colapsa cuando se observa el estado de la partícula. Este proceso de decoherencia, en el que la partícula que estaba en una superposición de estados colapsa a uno de los dos estados clásicos cuando se observa, se considera el puente entre la física cuántica y la clásica.
El experimento podría realizarse en un electrón en superposición, y si el observador esta midiendo el componente z del giro, el experimento producirá un valor resultado definido por el componente z del giro. El componente x aún podría permanecer en superposición. Esto se alinea con la interpretación de Bohr de que las propiedades en el mundo cuántico llegan a existir cuando se observan. Sabemos que los objetos macroscópicos, como los seres humanos, no exhiben esta propiedad: no adoptamos un estado determinado solo cuando nos observan (medicion o interactuacion). Pero ¿cómo pueden existir cosas en el mundo cuántico en múltiples estados en el mismo tiempo hasta que se observan?
Erwin Schrodinger ideó un experimento mental para ilustrar la naturaleza contraintuitiva, y aparente absurdo de este concepto:

Gato de Schrodinger


Se colocaron un gato, material radiactivo y gas venenoso en una caja. Si la radiactividad es
detectada, el frasco que contiene el gas venenoso se rompería y el gato muere. El material radiactivo es lo suficientemente pequeño como para que la radiactividad no pueda sea detectada durante algún tiempo. Por lo tanto, en cualquier momento dado, los que están fuera de la caja seran incapaces de determinar si el gato estaba vivo o muerto. Así, por lógica cuántica, ¡el gato podría considerarse vivo y muerto!
Schrodinger se preguntó cómo podría ser éste el caso dentro del mundo de la tecnología cuántica, cuando claramente no es el caso en el mundo macroscópico. Todos los experimentos cuánticos hasta ahora, sin embargo, han afirmado la teoría de que los objetos cuánticos de hecho parecen capaces de existir en dos estados hasta que se observan.

Quantum Error Correction (qec)

La corrección cuántica de errores (QEC) es un proceso crítico que hace que los resultados del sistema cuántico sean confiables. En los primeros días de la computación cuántica, la correccion de errores de una computadora cuántica de manera eficiente sin desencadenar la decoherencia de la computación se consideraba una tarea bastante compleja. La falta de corrección de errores confiable en un sistema cuantico era un obstáculo importante porque los algoritmos cuánticos utilizan interferencia, que es frágil a la interaccion u observacion. Esta interferencia hizo que los algoritmos cuánticos fueran sensibles a la imprecisión en el sistema y al acoplamiento entre el sistema y el resto del mundo.
Algunas de las razones comunes de los errores incluyen:

  1. Preparación del estado inicial del sistema
  2. La decoherencia de los qubits puede ocurrir debido a interacciones con el medio ambiente.
  3. Inexactitudes en las puertas
  4. Imperfecciones en el proceso de medición

Peter Shor y Andrew Steane desarrollaron el primer conjunto de codigos de corrección de errores cuánticos. Mientras que Peter Shor identificó que 9 qubits se pueden juntar para realizar corrección de errores en un qubit, Steane descubrió una metodologia de corrección de errores de 7 qubit. La pérdida de información cuántica debido a la interferencia con el medio ambiente puede ser abordada mediante la distribución de información. Si la información se distribuye en varios qubits en lugar de uno, la información es más segura. En lacomputación clasica , la corrección de errores mediante código de repetición utiliza tres bits para almacenar copias de información de un bit. Entonces, a menos que dos de las copias sean propensas a errores, la información estária intacta. Si bien este es un proceso simple en las computadoras clásicas, con las computadoras cuánticas, copiar información de un qubit a otro es más complicado

Fue Shor quien propuso un método para generalizar el método del código de repetición para las computadoras cuánticas. La solución que propuso fue codificar un qubit con el código de repetición en los estados base. La computación cuántica post-seleccionada fue desarrollada por Emanuel Knill, y demostró que la computación cuántica a escala se puede lograr a través de la deteccion de errores en lugar de corrección de errores. La computadora cuántica tendría un error al detectar circuitos y si se detecta que los errores (ruido) han traspasado un umbral, la subrutina relevante del algoritmo se reinicia y se vuelve a ejecutar.

Otro método útil para tratar los errores cuánticos es utilizar los códigos de deteccion de errores cuánticos llamados estabilizadores. Estas son herramientas bastante útiles para los desarrolladores de sistemas cuánticos. La especificación del código del estabilizador tiene numerosas aplicaciones, incluyendo el diseño de circuitos de preparación, circuitos de corrección y tolerancia a fallas de puertas lógicas. El uso de estabilizadores para definir códigos de corrección de errores cuánticos ayuda a aplicar operaciones lógicas sobre datos codificados mediante circuitos de corrección. El método de los 7 qubit desarrollado por Andrew Steane, que construye un qubit lógico utilizando siete qubits, tiene la capacidad de corregir errores X o Z únicos.

Conclusión: La conclusión clave es que la corrección de errores en la computación cuántica es un ejercicio no trivial. Las complejidades de QEC y las diversas opciones disponibles para abordarlos son dignos de todo un libro. Es un aspecto crítico de la computacion cuántica que ha ayudado a transformar la teoria de la computación cuántica a una posibilidad práctica.

referencias

  1. https://www2.physics.ox.ac.uk/sites/default/files/
    ErrorCorrectionSteane06.pdf
  2. https://journals.jps.jp/doi/full/10.7566/JPSJ.88.061009
  3. https://arxiv.org/pdf/quant-ph/9508027.pdf
  4. http://science.sciencemag.org/content/356/6343/1140
  5. https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf
  6. https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.
    Winter2006/05.pdf
  7. https://grove-docs.readthedocs.io/en/latest/vqe.html
  8. https://quantumexperience.ng.bluemix.net/qx/
    tutorial?sectionId=beginners-guide&page=004-The_Weird_and_
    Wonderful_World_of_the_Qubit~2F001-The_Weird_and_Wonderful_
    World_of_the_Qubit
  9. https://medium.com/@jonathan_hui/qc-cracking-rsa-with-shors-
    algorithm-bc22cb7b7767
  10. https://www.scottaaronson.com/blog/?p=208
  11. https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-
    user-guide/004-Quantum_Algorithms/070-Grover’s_Algorithm.html
  12. https://www.cs.cmu.edu/~odonnell/quantum15/lecture04.pdf
  13. https://medium.com/@quantum_wa/quantum-annealing-cdb129e96601

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s