Get best of the week

Como π combina blocos de colisão e um algoritmo de pesquisa quântica

Um físico curioso descobriu uma conexão inesperada entre a teoria dos blocos de colisão e o famoso algoritmo de busca quântica




O que os dígitos de π, os blocos de colisão e os algoritmos de pesquisa quântica têm em comum? Mais do que você possa imaginar. Essa conexão é fornecida por dois trabalhos científicos bem-humorados - um de 2003 e o segundo de dezembro de 2019. Juntos, eles combinam os mundos da dinâmica, geometria e computação quântica, mostrando como até os quebra-cabeças matemáticos mais abstratos podem surpreendentemente revelar uma conexão com a física.

Bloquear


Para começar a entender essas conexões, imagine dois blocos de metal, cada um pesando 1 kg. Eles estão na superfície sem atrito, à direita da parede fixa. O bloco mais próximo da parede está imóvel, o segundo desliza em sua direção, aproximando-se à direita. Uma série de confrontos deve ocorrer inevitavelmente; Suponha que a energia cinética não desapareça em colisões. Sob tais condições ideais, esse processo continuará assim:


O bloco da direita atinge a esquerda, dando todo o impulso. O bloco esquerdo quica na parede, retorna à direita para outra colisão e outra transmissão completa de impulso.

No entanto, se você aumentar a massa do bloco certo, a situação se tornará mais interessante. Se pesar 100 kg, com cada colisão transmitirá apenas uma pequena parte de seu momento ao bloco menor e, em vez do número de colisões, aumentará de 3 para 31.


Com uma taxa de massa de 10.000 para 1, a situação será resolvida após 314 colisões.


Aumente a diferença multiplicando a massa por 100, e você poderá observar uma tendência chocante: o número de colisões começará a se aproximar do número π cada vez mais próximo.


Gregory Galperin, matemático da Universidade de East Illinois, foi o primeiro a perceber esse fenômeno [em 1993]. Em 2003, ele explicou isso visualizando os movimentos dos blocos através de um ponto móvel, cujas coordenadas x indicam a localização de um bloco e as coordenadas y do segundo. A trajetória de um ponto no plano está conectada com um semicírculo, de onde π aparece.

Um resultado notável, mesmo que essas condições ideais o tornem aparentemente inútil. No entanto, se você negligenciar a negligência do mundo real na matemática, poderá encontrar uma regularidade pura que revela conexões inesperadas com outras áreas da ciência.

Em 2019, publiquei um conjunto de três vídeosexplicando os resultados de Halperin, e entre os que os observaram estavam Adam Brown, pesquisador do Google e físico da Universidade de Stanford. Depois de alguns meses na conferência, ele me levou para compartilhar sua observação. Para sua satisfação, ele descobriu que a matemática que descreve a dinâmica desses blocos, de um certo ponto de vista, se torna idêntica à matemática que descreve um dos algoritmos quânticos mais famosos.

Abordagem quântica


Isso nos leva à segunda parte do quebra-cabeça: como a pesquisa quântica funciona.

Suponha que você tenha uma longa lista de nomes sem classificar - digamos, um milhão - e precise encontrar um nome específico. Você não tem outras opções além de verificar um nome após o outro até encontrar o correto. Em média, serão necessários meio milhão de iterações. Às vezes mais, às vezes menos, mas, em qualquer caso, levará algum tempo.

Um computador pode fazer essa pesquisa por você, mas o problema com listas grandes é que o tempo necessário para processá-las aumentará proporcionalmente ao tamanho. Pelo menos ao usar um computador clássico. Mas em 1996, Love Grover, que trabalhou nos laboratórios de Bell, descreveucomo um computador quântico pode realizar essa pesquisa muito mais rapidamente e em não mais que 1000 etapas. No caso geral, um computador quântico lidará com uma lista de comprimento N em etapas π / 4 √N. Observe que, à medida que o número N aumenta, o número de etapas que um computador quântico cresce mais lentamente que o clássico.

Essa eficiência de pesquisa é possível porque um computador quântico processa todos os elementos da lista ao mesmo tempo. No entanto, ele não faz apenas a mesma coisa que um computador clássico faria, apenas ao mesmo tempo.

Um computador clássico responde à pergunta: "O 21º elemento da lista é o nome que eu preciso?" E o repete para cada posição da lista, de 0 a 999.999. Diretamente, mas não muito eficaz.

Mas o algoritmo de Grover funciona com um método de lista, que no começo parece estranho, mas no final é mais útil. Um computador clássico pode simplesmente ler bits da memória. As incertezas presentes na computação quântica levam ao fato de que você não pode extrair diretamente os componentes do vetor com o qual está trabalhando. Cada posição na lista possui uma estrutura probabilística adicional. Você não olha para qual nome está nessa posição, mede a lista inteira, obtendo uma posição aleatória - índice - de acordo com as probabilidades. Devido à mecânica quântica subjacente, em vez de trabalhar diretamente com valores probabilísticos, trabalhamos com números cujo quadrado corresponde à probabilidade de obter um índice correspondente ao nome que você está procurando.



Como a leitura de um índice aleatório pode ser útil? A arte da computação quântica é manipular uma lista de probabilidades que cria probabilidades a seu favor. Em nosso exemplo, isso significa inventar uma maneira (que é o que o algoritmo de Grover faz) de obter o número associado ao índice do nome que você está procurando, próximo à unidade, para que todos os outros números fiquem próximos de zero. Em seguida, lendo esta lista e recebendo um índice em resposta, é provável que você saiba que corresponde ao nome que está procurando.

As ferramentas de computação quântica consistem em operações que um pesquisador pode aplicar a esta lista de probabilidades. Em matemática, essa lista é chamada de vetor. Muitas vezes, é conveniente imaginar um vetor como um ponto em um sistema de coordenadas ou como uma seta desenhada da origem até esse ponto.



Um vetor de dois componentes pode ser representado como uma seta no espaço bidimensional. Um vetor com 1.000.000 de componentes vive em um espaço impressionante de 1.000.000 de dimensões. As operações executadas por um computador quântico se assemelham a curvas e giros dessa seta. Numericamente, cada operação é indicada por uma matriz.



Os cálculos quânticos são especialmente rápidos porque cada operação é executada com todo o vetor de probabilidade e não passa componente a componente. Grover descobriu uma maneira complicada de manipular um determinado vetor com um par de operações intermitentes, resultando em um vetor com as probabilidades de que precisamos. É importante que o número total de operações necessárias seja muito menor que o tamanho da lista.

Se é difícil imaginar como isso pode funcionar, você não é o único. Portanto, Adam Brown ficou muito feliz ao descobrir uma maneira de imaginar essas manipulações abstratas de vetores em termos de um quebra-cabeça mais compreensível.

Links ocultos


Aconteceu que, quando assisti aos meus vídeos sobre o cálculo do número π usando blocos colididos, Brown tinha apenas o algoritmo de Grover em mente, então ele imediatamente percebeu a conexão deles. "Se você passa o dia todo pensando em pesquisa quântica, tudo começa a parecer pesquisa quântica", disse Brown, "e aconteceu por acaso que esse caso realmente estava relacionado à pesquisa quântica".

E se o trabalho de Galperin em colisões de blocos usasse o espaço que codifica a localização de cada bloco, a conexão com a pesquisa quântica de Grover começa com um vetor cujos componentes xey codificam a velocidade de cada bloco. Cada colisão de blocos se traduz em uma operação específica nesse vetor, alterando seus componentes. Por exemplo, quando o bloco esquerdo colide com a parede, mudando a direção para o oposto, isso significa que o componente do nosso vetor é multiplicado por -1 e o componente x permanece inalterado. Do ponto de vista geométrico, isso parece um reflexo de um vetor sobre o eixo x.

Da mesma forma, quando dois blocos colidem, uma mudança em suas velocidades é semelhante a outro giro desse vetor, apenas deslocado do centro. Quando a simulação continuar, o bloco esquerdo colidirá novamente com a parede, o que levará a outra curva no eixo x. Outra colisão de blocos significa outra revolução. Como resultado, com um número suficiente de colisões, o vetor preencherá a curva familiar: o círculo.


Brown observou que, se essa situação for descrita corretamente, essas duas operações, mudando em uma direção ou outra, serão idênticas às duas operações que Grover usou em seu algoritmo de busca quântica.

Para entender como isso acontece, imagine um grande bloco à direita na forma de muitos quilogramas colados. Então, em vez de um vetor bidimensional que descreve cada velocidade, obtemos um vetor N-dimensional, onde N é o número total de pequenos blocos, incluindo o bloco isolado à esquerda. Cada um dos pequenos blocos corresponde a um nome em uma lista não classificada, e um bloco separado à esquerda corresponde ao nome do destino.

Em seu trabalho, Brown provou que a maneira como essas colisões de blocos alteram o vetor que os descreve é ​​absolutamente idêntica à maneira como o algoritmo de Grover altera o vetor quântico, denotando uma lista não classificada de nomes. O momento no sistema de blocos em colisão, quando um bloco grande está prestes a girar, e quase toda a energia do sistema está em um bloco pequeno, corresponde ao momento no algoritmo de Grover, quando quase toda a probabilidade está no nome que você precisa encontrar.

O fato de o número π aparecer ao contar colisões é refletido no algoritmo de Grover: π / 4 √N etapas. A raiz quadrada da expressão também reflete o quanto a contagem dos dígitos de π (em graus 10) vai depois de multiplicar a massa de um bloco grande por 10.

"Até agora, é apenas um truque", disse Brown. "Mas, na física, aprendemos que, quanto mais maneiras de refletir sobre um problema, mais idéias podemos ver - então espero que esse fato seja útil algum dia." Temos poucas maneiras alternativas de visualizar o algoritmo de Grover.

Essas conexões enfatizam as capacidades da linguagem universal da matemática. O uso de vetores para codificar o estado de um sistema físico funciona tanto em colisões de blocos em larga escala quanto em microescalas de estados quânticos. Muitas idéias fundamentais da matemática, que à primeira vista parecem desagradavelmente desassociadas da realidade, acabam sendo ferramentas poderosas, porque se você omitir os detalhes físicos em uma das áreas, poderá descobrir suas conexões ocultas com a outra.

More articles:


All Articles