É difícil encontrar coincidência pura e verificável. Duas novas frases mostram como criar fábricas de números aleatórios a partir de computadores quânticos.
Diga "excelência quântica" em qualquer reunião de cientistas da computação e você provavelmente os verá revirar os olhos. Essa frase refere-se à idéia de que os computadores quânticos logo cruzarão a linha além da qual eles serão capazes de executar tarefas extremamente difíceis para computadores clássicos com relativa facilidade. E até recentemente, essas tarefas eram consideradas de pouca utilidade para aplicações reais - daí o rolar dos olhos.
Mas agora que se diz que o processador do Google está próximo desse objetivo, a superioridade quântica iminente pode ter um uso importante: gerar pura aleatoriedade.
A aleatoriedade é importante para quase tudo o que acontece na infraestrutura de computação e comunicação. Em particular, é usado para criptografar dados que protegem tudo, desde conversas comuns a transações financeiras e segredos de estado.
A aleatoriedade real e confirmada - imagine-a como uma propriedade que existe em uma sequência de números e torna impossível prever o próximo número em uma sequência - é extremamente difícil de encontrar.
Mas essa situação pode mudar quando os computadores quânticos demonstram sua superioridade. Essas primeiras tarefas, que desde o início simplesmente demonstravam a superioridade da tecnologia, também podem fornecer uma verdadeira coincidência certificada. "Estamos felizes em receber isso", disse
John Martinis , físico da Universidade da Califórnia, Santa Barbara, que dirige o projeto de computação quântica no Google. "Esperamos que este seja o primeiro uso de um computador quântico".
Aleatoriedade e entropia
A aleatoriedade e a teoria quântica andam de mãos dadas como trovões e raios. Nos dois casos, o primeiro é uma conseqüência inevitável do segundo. No mundo quântico, os sistemas costumam estar em uma combinação de vários estados - os chamados "Superposição". Quando você mede um sistema, ele entra em colapso em um desses estados. E enquanto a teoria quântica permite calcular as probabilidades do que você descobrirá em uma medição, o resultado exato sempre será fundamentalmente aleatório.
Os físicos estudaram essa conexão para criar geradores de números aleatórios. Todos eles dependem de medidas de algum tipo de superposição quântica. E, embora para a maioria dos métodos de geração de números aleatórios necessários para as pessoas, esses sistemas sejam suficientes, pode ser difícil trabalhar com eles. Além disso, é muito difícil provar ao cético a verdadeira aleatoriedade desses geradores de números aleatórios. Finalmente, alguns dos métodos mais eficazes para gerar aleatoriedade confirmada requerem designs sofisticados de vários dispositivos separados por grandes distâncias.
Google AI Lab apresenta o processador quântico Bristlecone 72-Qubit em 2018Uma proposta recente para extrair a aleatoriedade de apenas um dispositivo - um computador quântico - usa o chamado. a tarefa de amostragem, que será um dos primeiros testes de superioridade quântica. Para entender, imagine que você recebeu uma caixa de azulejos. Em cada bloco há várias unidades e vários zeros - 000, 010, 101 e assim por diante.
Se houver apenas três bits, existem oito opções possíveis. No entanto, pode haver várias cópias de cada bloco na caixa. Pode haver 50 blocos rotulados 010 e 25 blocos rotulados 001. A distribuição dos blocos determina a probabilidade de você puxar acidentalmente um bloco específico. No nosso caso, você pode extrair o bloco 010 com uma probabilidade duas vezes maior que o bloco 001.
A tarefa de amostragem inclui um algoritmo de computador equivalente a puxar aleatoriamente blocos da caixa com uma distribuição específica. Quanto maior a probabilidade definida para qualquer bloco na distribuição, maior a probabilidade do algoritmo puxar esse bloco.
Obviamente, o algoritmo não extrai blocos reais de uma caixa real. Apenas produz aleatoriamente um número binário de 50 bits de comprimento, tendo recebido uma distribuição que determina a probabilidade desejada para cada uma das linhas possíveis de 50 bits de comprimento.
Para um computador clássico, a complexidade dessa tarefa aumenta exponencialmente com um aumento no número de bits em uma string. Mas para um computador quântico, espera-se que a tarefa permaneça aproximadamente a mesma para 5 bits e 50.
Um computador quântico começa dizendo que todos os seus bits quânticos - qubits - estão em um determinado estado. Suponha que todos eles comecem com 0. Como computadores clássicos podem trabalhar com bits clássicos usando o chamado. portas lógicas e computadores quânticos manipulam qubits usando seus equivalentes quânticos, portas quânticas.
No entanto, portões quânticos podem colocar qubits em estados estranhos. Por exemplo, um tipo de porta pode colocar um qubit que começa com um valor de 0 em uma superposição de 0 e 1. Se você medir o estado de um qubit, ele entrará aleatoriamente em 0 ou 1 com igual probabilidade.
Mesmo portões quânticos mais estranhos, que podem trabalhar com dois ou mais qubits ao mesmo tempo, podem fazer com que os qubits se enredem entre si. Nesse caso, os estados dos qubits são entrelaçados, de modo que agora todos esses qubits podem ser descritos usando apenas um estado quântico.
Se você trouxer um monte de portas quânticas para um lugar e depois fazê-las trabalhar com um conjunto de qubits em uma determinada sequência, este será um circuito quântico. No nosso caso, para derivar uma sequência aleatória de 50 bits, você pode construir um circuito quântico que coloque 50 qubits em uma superposição de estados que descreve a distribuição que você precisa.
Ao medir qubits, toda a superposição é recolhida aleatoriamente em uma única sequência de 50 bits. A probabilidade de colapso em uma determinada linha é determinada pela distribuição determinada pelo contorno quântico. A medição de qubits é semelhante à maneira como um homem com os olhos vendados estende a mão para dentro de uma bolsa e acidentalmente puxa uma linha com a distribuição.
Scott Aaronson, Especialista em Ciência da Computação, Universidade do Texas em AustinE como tudo isso está relacionado a números aleatórios? É importante que a string de 50 bits selecionada pelo computador quântico contenha muita entropia, uma medida de desordem ou imprevisibilidade e, portanto, aleatoriedade. "E isso, de fato, pode ter consequências muito sérias", disse
Scott Aaronson , especialista em TI da Universidade do Texas em Austin, que criou um novo protocolo. "Não porque é o uso mais importante de computadores quânticos - acho que está longe disso - mas porque parece ser talvez o primeiro uso de computadores quânticos que pode ser colocado em prática".
O protocolo de Aaronson para gerar números aleatórios é bastante simples. Um computador clássico primeiro coleta alguns bits aleatórios de alguma fonte confiável e depois usa essa "semente da aleatoriedade" para gerar uma descrição do contorno quântico. Os bits aleatórios determinam o tipo de portas quânticas e a sequência na qual eles devem agir em qubits. Um computador clássico envia uma descrição para um computador quântico que implementa um circuito quântico, mede qubits e envia uma string de 50 bits. Assim, acaba sendo selecionado aleatoriamente na distribuição definida pelo contorno.
Em seguida, repita esse processo várias vezes - por exemplo, 10 vezes para cada circuito quântico. Um computador clássico usa testes estatísticos para garantir que as linhas de saída contenham uma quantidade razoável de entropia. Aaronson mostrou (em parte em um
trabalho publicado escrito em colaboração com Lijie Chen e em parte em um
trabalho ainda a ser publicado) que, sob certas suposições razoáveis de que tais tarefas são computacionalmente complexas, nenhum computador clássico pode gerar tal entropia. tempo comparável ao tempo durante o qual um computador quântico cria uma seleção tão aleatória a partir da distribuição. Após as verificações, o computador clássico coleta todas as seqüências de 50 bits e as alimenta com o conhecido algoritmo clássico. "Produz uma corda longa, quase perfeitamente aleatória", disse Aaronson.
Armadilha quântica
O protocolo Aaronson é mais adequado para computadores quânticos com um número de qubits de 50 a 100. Quando o número de qubits ultrapassa esses limites, a complexidade computacional não permite o uso desse protocolo, mesmo para supercomputadores clássicos. Nesse caso,
outro esquema para gerar números aleatórios verificáveis usando computadores quânticos entra em cena. Ele usa uma técnica matemática existente com a função complexa livre de garras do alçapão. "Isso parece pior do que a realidade", disse
Umesh Wazirani , especialista em TI da Universidade da Califórnia em Berkeley, que desenvolveu uma nova estratégia que foi ajudada por
Zvika Brackerski ,
Paul Cristiano ,
Urmila Mahadev e
Thomas Vidik .
Introduzir nossa caixa. Em vez de entrar nela e extrair uma string, jogamos uma string de n bits nela, chamamos de x e removemos outra string de n bits. De alguma forma, a caixa corresponde à linha de entrada e à linha de saída. Mas tem uma propriedade especial: para cada x existe outra linha de entrada y, que produz exatamente a mesma linha de saída.
Em outras palavras, existem duas linhas de entrada exclusivas - xey - para as quais a caixa retorna a mesma linha de saída z. Esse triplo, x, ye z, é chamado de garra. Caixa na linguagem da ciência da computação - uma função. Essa função é fácil de calcular, ou seja, para qualquer x e y é fácil calcular z. Mas se você pegar apenas x e z, encontrar y - e toda a garra - é impossível mesmo para um computador quântico.
Urmila Mahadev, Umesh Vazirani e Thomas VidikA única maneira de obter toda a garra é encontrar algumas informações adicionais, as chamadas uma armadilha.
Vazirani e seus colegas querem usar essas funções para forçar não apenas os computadores quânticos a gerar números aleatórios, mas também para verificar se os computadores quânticos realmente funcionam de acordo com as leis quânticas - o que é necessário para criar confiança nas seqüências aleatórias.
O protocolo começa com um computador quântico colocando n qubits em uma superposição de todas as seqüências de n bits. Em seguida, o computador clássico envia uma descrição do contorno quântico, determinando a função a ser aplicada à superposição - a função de armadilha sem garras. Um computador quântico implementa um circuito sem saber nada sobre a armadilha.
Nesse estágio, o computador quântico entra em um estado no qual um conjunto de seus qubits está em uma superposição de todas as seqüências de n bits, e o outro contém o resultado da aplicação da função a essa superposição. Dois conjuntos de qubits são entrelaçados um com o outro.
Um computador quântico medindo um segundo conjunto de qubits colapsa aleatoriamente uma superposição em um determinado resultado z. O primeiro conjunto de qubits entra em colapso em uma superposição semelhante de duas seqüências de n bits, xey, uma vez que qualquer uma delas pode servir como entrada para uma função que emite z.
Um computador clássico recebe um valor de saída z e executa uma de duas coisas. Na maioria dos casos, ele pede ao computador quântico para medir os qubits restantes. Isso reduz a superposição em x ou em y, com 50% de chance. Isso é equivalente a obter aleatoriamente 0 ou 1.
Às vezes, para testar um computador quântico quanto ao quantum, um computador clássico pede uma medida especial. A medição e seu resultado são projetados para que um computador clássico, com a ajuda de uma armadilha à qual apenas ele tenha acesso, possa garantir que o dispositivo que responde às suas solicitações seja realmente quântico. Vazirani e colegas mostraram que, se o dispositivo der a resposta correta para uma dimensão específica sem o colapso dos qubits, será equivalente a encontrar uma garra sem uma armadilha. E isso é impossível. Portanto, pelo menos um qubit (dando 0 ou 1 aleatoriamente) deve entrar em colapso no dispositivo. "O protocolo cria um qubit testado dentro de um computador quântico no qual não confiamos", disse Vazirani.
Esse qubit testado fornece uma informação verdadeiramente aleatória para cada pesquisa; uma sequência dessas consultas pode ser usada para criar longas seqüências aleatórias.
Esse esquema pode funcionar mais rápido que o protocolo Aaronson, mas possui uma falha clara. "Com uma contagem de qubit de 50 ou 70, não será prático", disse Aaronson.
Aaronson ainda aguarda o surgimento de um sistema do Google. "Se a qualidade do que eles nos mostram é suficiente para realmente alcançar a superioridade quântica é uma grande questão", disse ele.
Se a empresa for bem-sucedida, a aleatoriedade quântica garantida já estará à nossa porta. "Acreditamos que será um mercado útil e promissor, e é isso que gostaríamos de oferecer às pessoas", afirmou Martinis.