Get best of the week

Cómo combina los bloques colisionantes y un algoritmo de búsqueda cuántica

Un físico curioso ha descubierto una conexión inesperada entre la teoría de los bloques de colisión y el famoso algoritmo de búsqueda cuántica.




¿Qué tienen en común los dígitos de π, bloques en colisión y algoritmos de búsqueda cuántica? Más de lo que puedas pensar. Esta conexión es proporcionada por dos trabajos científicos humorísticos: uno de 2003 y el segundo de diciembre de 2019. Juntos combinan los mundos de la dinámica, la geometría y la computación cuántica, mostrando cómo incluso los acertijos matemáticos más abstractos pueden revelar sorprendentemente una conexión con la física.

Bloquear


Para comenzar a comprender estas conexiones, imagine dos bloques de metal, cada uno de los cuales pesa 1 kg. Están en la superficie sin fricción, a la derecha de la pared fija. El bloque más cercano a la pared está inmóvil, el segundo se desliza hacia él y se acerca a la derecha. Una serie de enfrentamientos debe ocurrir inevitablemente; Supongamos que la energía cinética no desaparece en colisiones. Bajo tales condiciones ideales, este proceso procederá así:


El bloque derecho golpea el izquierdo, dándole todo el impulso. El bloque izquierdo rebota en la pared, vuelve a la derecha para otra colisión y otra transmisión completa de impulsos.

Sin embargo, si aumenta la masa del bloque correcto, la situación se volverá más interesante. Si pesa 100 kg, con cada colisión transmitirá solo una pequeña parte de su impulso al bloque más pequeño, y en lugar del número de colisiones, aumentará de 3 a 31.


Con una relación de masa de 10,000 a 1, la situación se resolverá después de 314 colisiones.


Aumente la diferencia multiplicando la masa por 100, y podrá observar una tendencia impactante: el número de colisiones comenzará a acercarse al número π cada vez más cerca.


Gregory Galperin, matemático de la Universidad de East Illinois, fue el primero en notar este fenómeno [en 1993]. En 2003, lo explicó visualizando los movimientos de los bloques a través de un punto en movimiento, cuyas coordenadas x indican la ubicación de un bloque y las coordenadas y del segundo. La trayectoria de un punto en el plano está conectada con un semicírculo, de donde aparece π.

Un resultado notable, incluso si estas condiciones ideales lo hacen aparentemente inútil. Sin embargo, si descuidas el descuido del mundo real en matemáticas, puedes encontrar una regularidad pura que revela conexiones inesperadas con otras áreas de la ciencia.

En 2019, publiqué un conjunto de tres videosexplicando los resultados de Halperin, y entre quienes los miraron estaban Adam Brown, investigador de Google y físico de la Universidad de Stanford. Después de unos meses en la conferencia, me llevó a un lado para compartir su observación. Para su deleite, descubrió que las matemáticas que describen la dinámica de estos bloques, desde cierto punto de vista, se vuelven idénticas a las matemáticas que describen uno de los algoritmos cuánticos más famosos.

Enfoque cuántico


Esto nos lleva a la segunda parte del rompecabezas: cómo funciona la búsqueda cuántica.

Suponga que tiene una larga lista de nombres sin ordenar, digamos un millón, y necesita encontrar un nombre específico. No tiene más opciones que verificar un nombre tras otro hasta que encuentre el correcto. En promedio, le llevará medio millón de iteraciones. A veces más, a veces menos, pero en cualquier caso te llevará algo de tiempo.

Una computadora podría hacer esta búsqueda por usted, pero el problema con las listas grandes es que la cantidad de tiempo que lleva procesarlas crecerá en proporción a su tamaño. Al menos cuando se usa una computadora clásica. Pero en 1996, Love Grover, que trabajaba en los laboratorios de Bell, describiócómo una computadora cuántica puede realizar dicha búsqueda mucho más rápido y en no más de 1000 pasos. En el caso general, una computadora cuántica hará frente a una lista de longitud N en pasos π / 4 √N. Tenga en cuenta que a medida que aumenta el número N, el número de pasos que una computadora cuántica crece más lentamente que una clásica.

Tal eficiencia de búsqueda es posible porque una computadora cuántica procesa todos los elementos de la lista al mismo tiempo. Sin embargo, no solo hace lo mismo que haría una computadora clásica, sino al mismo tiempo.

Una computadora clásica responde la pregunta: "¿Es el elemento 21 de la lista el nombre que necesito?" Y lo repite para cada posición de la lista, de 0 a 999,999. Directamente, pero no muy efectivo.

Pero el algoritmo de Grover funciona con un método de lista, que al principio parece extraño, pero al final es más útil. Una computadora clásica puede simplemente leer bits de la memoria. Las incertidumbres presentes en la computación cuántica conducen al hecho de que no puede extraer directamente los componentes del vector con el que está trabajando. Cada posición en la lista tiene una estructura probabilística adicional. No mira qué nombre está en esta posición, mide la lista completa, obteniendo una posición aleatoria, el índice, de acuerdo con las probabilidades. Debido a la mecánica cuántica subyacente, en lugar de trabajar directamente con valores probabilísticos, trabajamos con números cuyo cuadrado corresponde a la probabilidad de obtener un índice correspondiente al nombre que está buscando.



¿Cómo puede ser útil leer un índice aleatorio? El arte de la computación cuántica es manipular una lista de probabilidades que crea probabilidades a su favor. En nuestro ejemplo, esto significa inventar una forma (que es lo que hace el algoritmo de Grover) para obtener el número asociado con el índice del nombre que está buscando, cerca de la unidad, para que todos los demás números estén cerca de cero. Luego, al leer esta lista y recibir un índice en respuesta, es probable que sepa que corresponde al nombre que está buscando.

Las herramientas de computación cuántica consisten en operaciones que un investigador puede aplicar a esta lista de probabilidades. En matemáticas, dicha lista se llama vector. A menudo es conveniente imaginar un vector como un punto en un sistema de coordenadas, o como una flecha dibujada desde el origen hasta este punto.



Un vector de dos componentes se puede representar como una flecha en un espacio bidimensional. Un vector con 1,000,000 de componentes vive en un impresionante espacio de 1,000,000 de dimensiones. Las operaciones realizadas por una computadora cuántica parecen giros y vueltas de esta flecha. Numéricamente, cada operación se indica mediante una matriz.



Los cálculos cuánticos son especialmente rápidos porque cada operación se realiza con todo el vector de probabilidad y no pasa por componentes. Grover descubrió una forma complicada de manipular un vector dado con un par de operaciones intermitentes, lo que resulta en un vector con las probabilidades que necesitamos. Es importante que el número total de operaciones requeridas sea mucho menor que el tamaño de la lista.

Si te resulta difícil imaginar cómo puede funcionar esto, no eres el único. Por lo tanto, Adam Brown estaba tan feliz de descubrir una manera de imaginar estas manipulaciones abstractas de vectores en términos de un rompecabezas más comprensible.

Enlaces ocultos


Resultó que cuando vi mis videos sobre el cálculo del número π usando bloques en colisión, Brown solo tenía en mente el algoritmo de Grover, por lo que inmediatamente notó su conexión. "Si pasas todo el día pensando en la búsqueda cuántica, entonces todo comienza a parecer una búsqueda cuántica", dijo Brown, "y coincidió casualmente que este caso realmente estuvo relacionado con la búsqueda cuántica".

Y si el trabajo de Galperin en colisiones de bloques utilizó el espacio que codificó la ubicación de cada bloque, entonces la conexión con la búsqueda cuántica de Grover comienza con un vector cuyos componentes x e y codifican la velocidad de cada bloque. Cada colisión de bloques se traduce en una operación específica en este vector, cambiando sus componentes. Por ejemplo, cuando el bloque izquierdo colisiona con la pared, cambiando la dirección al opuesto, esto significa que la componente de nuestro vector se multiplica por -1, y la componente x permanece sin cambios. Desde un punto de vista geométrico, esto parece un reflejo de un vector sobre el eje x.

De manera similar, cuando dos bloques chocan, un cambio en sus velocidades es similar a otro giro de este vector, solo desplazado desde el centro. Cuando la simulación continúa, el bloque izquierdo volverá a chocar con la pared, lo que conducirá a otro giro en el eje x. Otra colisión de bloques significa otra revolución. Como resultado, con un número suficiente de colisiones, el vector llenará la curva familiar: el círculo.


Brown señaló que si esta situación se describe correctamente, entonces estas dos operaciones, que cambian en una dirección u otra, son idénticas a las dos operaciones que Grover utilizó en su algoritmo de búsqueda cuántica.

Para entender cómo sucede esto, imagine un gran bloque derecho en forma de muchos kilogramos pegados. Luego, en lugar de un vector bidimensional que describe cada velocidad, obtenemos un vector N-dimensional, donde N es el número total de bloques pequeños, incluido el bloque aislado de la izquierda. Cada uno de los bloques pequeños corresponde a un nombre en una lista sin clasificar, y un bloque separado a la izquierda corresponde al nombre del objetivo.

En su trabajo, Brown demostró que la forma en que estas colisiones de bloques cambian el vector que los describe es absolutamente idéntica a la forma en que el algoritmo de Grover cambia el vector cuántico que denota una lista sin clasificar de nombres. El momento en el sistema de bloques en colisión, cuando un bloque grande está a punto de darse vuelta, y casi toda la energía en el sistema está en un bloque pequeño, corresponde al momento en el algoritmo de Grover, cuando casi toda la probabilidad está en el nombre que necesita encontrar.

El hecho de que el número π aparece al contar las colisiones se refleja en el algoritmo de Grover: π / 4 √N pasos. La raíz cuadrada en la expresión también refleja qué tan lejos llega el conteo de los dígitos de π (en grados 10) después de multiplicar la masa de un bloque grande por 10.

"Hasta ahora, es solo un truco", dijo Brown. "Pero en física, hemos aprendido que cuantas más formas podamos reflexionar sobre un problema, más ideas podemos ver, así que espero que este hecho sea útil algún día". Tenemos algunas buenas formas alternativas de visualizar el algoritmo de Grover.

Estas conexiones enfatizan las capacidades del lenguaje universal de las matemáticas. El uso de vectores para codificar el estado de un sistema físico funciona tanto en colisiones a gran escala de bloques como en microescalas de estados cuánticos. Muchas ideas fundamentales en matemáticas, que a primera vista parecen desagradablemente divorciadas de la realidad, resultan ser herramientas poderosas, porque si omites los detalles físicos en una de las áreas, puedes descubrir sus conexiones ocultas con la otra.

More articles:


All Articles