Quantum Computing ahora tiene una poderosa herramienta de búsqueda

algoritmo de Grover

En 1996, un científico informático llamado Lov Grover de Bell Labs en Nueva Jersey dio a conocer un algoritmo inusual para buscar en una base de datos. Los algoritmos de búsqueda se encuentran entre los más importantes en informática. Hacen posibles tareas mundanas, como buscar en guías telefónicas, pero también tareas más exóticas, como descifrar códigos criptográficos. Este tipo de algoritmo es omnipresente en informática.

Así que cualquier forma de acelerar la tarea es muy importante. Una búsqueda estándar toma un período de tiempo que es aproximadamente proporcional al número de elementos en la búsqueda. Esto se debe a que, en el peor de los casos, el algoritmo tiene que buscar entre todos los elementos para encontrar solo uno.

Pero el algoritmo de Grover es diferente. El tiempo que tarda es proporcional a la raíz cuadrada del número de elementos. Los informáticos llaman a esto aceleración cuadrática. Y en un mundo donde los aumentos de velocidad de unas pocas fracciones de un porcentaje son enormemente valiosos, una aceleración cuadrática es un logro imponente.

El truco de Grover fue emplear las ideas extrañas pero poderosas detrás de la mecánica cuántica. En el mundo clásico, los bits son solo 0 y 1. Pero en el mundo cuántico, un solo bit cuántico, o qubit, puede ser un 0 y un 1 al mismo tiempo. Los físicos dicen que el qubit está en una superposición de estados.

La superposición es la clave. En este estado, un algoritmo puede buscar tanto el 0 como el 1 en el mismo instante. Debido a que puede buscar más de un elemento al mismo tiempo, un algoritmo cuántico puede buscar en una lista mucho más rápido que un algoritmo limitado por el ritmo lento de la física clásica.

Los algoritmos cuánticos deben ser implementados por una computadora cuántica, y en 1996, cuando Grover hizo su trabajo, estos eran poco más que un sueño lejano. Pero el avance llegó rápidamente. Los físicos demostraron la primera computadora cuántica primitiva en 1998 y mostraron cómo podría ejecutar el algoritmo de Grover en el mismo año.

Pero esta forma particular de computación cuántica era extremadamente limitada. Funcionó en algunos qubits pero no más e, incluso en principio, nunca podría ampliarse a cálculos más grandes. Este problema de construir y demostrar computadoras cuánticas escalables ha plagado la disciplina desde entonces.

Ahora, unos 20 años después, los físicos están comenzando a construir computadoras cuánticas que tienen el potencial de escalar y, por lo tanto, son capaces de realizar cálculos más potentes. Y hoy, Caroline Figgatt y sus amigos de la Universidad de Maryland dicen que ejecutaron el algoritmo de Grover en una computadora cuántica escalable por primera vez.

El trabajo demuestra la rápida aceleración de los cálculos cuánticos y allana el camino para un trabajo más ambicioso con el algoritmo que podría comenzar a descifrar desafíos del mundo real, como el descifrado de códigos.

La computadora cuántica con la que trabajan Figgatt y sus compañeros consiste en una cadena de cinco iones de iterbio suspendidos en un campo electromagnético. Cada ion es como un pequeño imán que puede orientarse hacia arriba o hacia abajo y pasar de un estado a otro con un láser. De esta forma, cada ion puede almacenar información: un 1 para girar hacia arriba y un 0 para girar hacia abajo, por ejemplo. Y debido a que son objetos cuánticos, los iones pueden existir en una superposición de estos estados.

Los iones también interactúan entre sí a través de las fuerzas de repulsión asociadas con su carga positiva. Esta interacción permite que un qubit interactúe con otro qubit para procesar información. Esta es la esencia de la computación cuántica. El orden de los pasos en este cálculo es el algoritmo cuántico, en este caso el algoritmo de Grover.

Figgatt y compañía usan su sistema para crear una computadora cuántica de tres qubits que puede almacenar hasta ocho elementos en una base de datos. Luego realizan el algoritmo de Grover para mostrar que es posible encontrar un elemento significativamente más rápido, en promedio, que una computadora clásica que requeriría al menos ocho bits. Informamos los resultados de un algoritmo de búsqueda Grover completo de tres qubits que utiliza la tecnología de computación cuántica escalable de iones atómicos atrapados, con un rendimiento mejor que el clásico, dicen Figgatt y compañía.

Es un trabajo interesante con un potencial significativo. Esto allana el camino para un uso más extenso del algoritmo de búsqueda de Grover para resolver problemas más grandes en computadoras cuánticas, incluido el uso del circuito como subrutina para otros algoritmos cuánticos, dice el equipo.

Pero el trabajo también proporciona una visión interesante de la carrera para construir poderosas computadoras cuánticas. Es probable que el ganador de esta carrera obtenga grandes recompensas financieras, pero nadie está seguro de qué tecnología es la mejor.

Este mundo ha sido confundido por una startup canadiense llamada D-Wave Systems que ha vendido computadoras cuánticas aparentemente poderosas a compañías como Google y Lockheed Martin. Estas computadoras funcionan con 1000 qubits, mucho más que cualquier otra tecnología.

Pero muchos teóricos dicen que las afirmaciones de D-Wave son exageradas y que sus máquinas no pueden producir ni cerca del tipo de potencia computacional que otras computadoras cuánticas deberían ser capaces de producir.

Es por eso que muchos grupos están tratando de comercializar otras tecnologías cuánticas que difieren drásticamente en la forma en que almacenan y procesan la información cuántica. Estos dependen de diversas formas de fotones, electrones, átomos, iones y moléculas para cumplir sus órdenes cuánticas.

De estas técnicas, una de las más antiguas y mejor desarrolladas es la computación cuántica con trampa de iones, y el grupo de la Universidad de Maryland es líder mundial en esta área. De hecho, el líder del grupo, Chris Monroe, tiene una startup llamada IonQ que tiene como objetivo comercializar esta tecnología.

Entonces, la demostración de una computadora cuántica escalable que puede implementar el algoritmo de Grover, aunque con solo tres qubits, puede verse como una declaración de intenciones.

En 1998, después de la primera implementación del algoritmo de Grover, hubo una variedad de opiniones sobre cuánto tiempo les tomaría a los físicos hacer que el próximo paso fuera escalable en computadoras. Varias empresas emergentes se formaron y colapsaron debido a pronósticos optimistas. Pero, en ese momento, 20 años estaba en el extremo pesimista del espectro de predicciones. El hecho de que haya llevado tanto tiempo pone en perspectiva la dificultad de la tarea.

Controlar el universo en la escala cuántica es difícil. Una pregunta interesante ahora para los tecnólogos y los capitalistas de riesgo es si la tasa de progreso tecnológico puede acelerarse significativamente.

Ref: arxiv.org/abs/1703.10535 : Complete la búsqueda Grover de 3 Qubit en una computadora cuántica programable

esconder