Há alguns dias, um artigo preliminar do Google sobre a conquista da superioridade quântica em um computador quântico supercondutor vazou para a rede. O texto em si foi rapidamente removido e rumores e suposições, incluindo erros, se multiplicaram em torno dele. O autor do post é o
professor Scott Aaronson , um dos principais especialistas em algoritmos quânticos, e possui um excelente blog. No último post, ele responde às principais perguntas sobre superioridade quântica.
Do tradutor. Não sou especialista em complexidade algorítmica e em algoritmos quânticos em particular. Mas o post me pareceu interessante demais para não discuti-lo em Habré e, por qualquer erro de termos ou uso incomum, por favor, me mande um comentário.
Você já viu histórias - no
Financial Times , na
Technology Review , na
CNET , no Facebook, no Reddit, no Twitter ou em outros lugares - que falam de um grupo do Google que alcançou superioridade quântica com um computador supercondutor de 53 qubit. É fácil encontrar essas histórias, não vou anexá-las aqui, pois nenhuma delas deveria existir ainda.
Como o mundo inteiro sabe agora, o Google está realmente preparando uma grande declaração sobre superioridade quântica, planejada em conjunto com um artigo científico de uma revista legal (qual? A escolha é pequena - uma de duas). Espero que isso aconteça dentro de um mês.
Enquanto isso, a NASA, onde alguns dos autores do artigo trabalham, publicou acidentalmente uma versão antiga do artigo em um site público. Ela ficou lá por pouco tempo, mas tempo suficiente para estar no
Financial Times, na minha correspondência e em um milhão de outros lugares. Espera-se que a especulação sem fatos sobre seu significado se multiplique.
Parece que o mundo foi privado do momento puro do “pouso na lua”, onde a extensa tese Igreja-Turíngia é destruída por evidências experimentais durante uma conferência de imprensa. Será mais como o vôo dos irmãos Wright - sobre o qual rumores e meias-verdades se infiltraram no espaço público entre 1903 e 1908, quando Will e Orville finalmente decidiram demonstrar seu voo. (Desta vez, felizmente, tudo será esclarecido muito mais rápido!)
Este post não é uma declaração oficial ou confirmação de nada. Embora os raios já estejam visíveis, o trovão pertence a um grupo do Google, na hora e no local de sua escolha.
Em vez disso, quero interromper o fluxo de informações erradas e oferecer aqui, como blogueiro e "intelectual público", as perguntas frequentes da Supremacia Quântica Suprema de Scott. Você sabe, caso de repente você esteja curioso sobre a superioridade quântica ou sempre quis saber o que acontecerá se, de repente, alguma empresa de pesquisa de Mountain View ou de outro lugar declarar hipoteticamente que a superioridade quântica foi alcançada.
Sem mais delongas, aqui está:
B1 O que é excelência computacional quântica?Freqüentemente reduzido a simplesmente "superioridade quântica", o termo refere-se ao uso de um computador quântico para resolver um conjunto especial de problemas, cuja solução em um computador clássico, usando qualquer algoritmo conhecido, levaria ordens de magnitude mais longas - e não por alguns motivos aleatórios, mas a partir de devido à complexidade quântica assintótica. A ênfase aqui está em ter a maior certeza possível de que o problema foi realmente resolvido de uma maneira quântica e realmente classicamente inatingível, e idealmente nos permitirá alcançar a aceleração da computação em um futuro próximo (com computadores quânticos barulhentos e não universais que já temos lá ou será em breve). Se a tarefa também é útil para algo, tanto melhor, mas não é necessário. O avião Wright e a pilha de lenha Fermi não foram úteis por si só.
B2 Se o Google realmente alcançou superioridade quântica, isso significa que agora não há código de crack , como Andrew Young, candidato à presidência dos EUA, fechou recentemente?Não, não (embora eu ainda goste da candidatura de Young).
Existem dois problemas. Em primeiro lugar, os dispositivos criados pelo Google, IBM e outros têm de 50 a 100 qubits e nenhuma correção de erros. Hackear o RSA usando o algoritmo Shore exigirá vários milhares de qubits lógicos. Com métodos conhecidos de correção de erros, milhões de qubits físicos e melhor qualidade do que temos agora, podem ser facilmente necessários para isso. Não me parece que alguém esteja perto disso, e não temos idéia de quanto tempo eles poderão chegar perto disso.
E o segundo problema é que, mesmo no futuro hipotético do CQ com correção de erros, seremos capazes de quebrar apenas alguns códigos, mas não todos, pelo menos até onde sabemos agora. Coincidentemente, as chaves públicas que podem ser quebradas incluem a maioria dos algoritmos que usamos para proteger a Internet: RSA, Diffie-Hellman, criptografia elíptica, etc. Mas a criptografia baseada em chaves privadas não deve ser afetada. E também existem sistemas de criptografia para chaves públicas (por exemplo, com base em grades) que ninguém sabe como quebrar usando o CQ, mesmo após mais de 20 anos de tentativas, e há tentativas de mudar para esses sistemas. Por exemplo, veja minha
carta a Rebecca Goldstein .
B3 Que tipo de cálculo o Google planeja fazer (ou já fez), que são considerados classicamente complexos.Claro, posso lhe dizer, mas me sinto idiota ao mesmo tempo. O cálculo é o seguinte: o experimentador gera um circuito quântico aleatório C (ou seja, uma sequência aleatória de 1 qubit e 2 qubit - entre os vizinhos mais próximos - portas, com profundidade de 20, por exemplo, atuando em uma rede 2D n = 50-60 qubits). Depois disso, o pesquisador envia C ao computador quântico e pede que ele aplique C ao estado inicial de 0, meça o resultado na base {0,1}, envie de volta a sequência observável de n bits (sequência) e repita vários milhares ou milhões de vezes. Finalmente, usando seu conhecimento de C, o pesquisador realiza uma verificação estatística da conformidade do resultado com a saída esperada do computador quântico.
Esta tarefa não é uma das tarefas com a única resposta correta, ao contrário da fatoração de números. O resultado da operação do esquema C acaba sendo uma distribuição estatística (vamos chamá-lo de D
C ) sobre cadeias de n bits, das quais precisamos selecionar amostras. De fato, geralmente D
C pode corresponder a 2
n linhas - tantas que, se o CQ funcionar como esperado, nunca produzirá a mesma linha na saída duas vezes. É importante que a distribuição de D
C não
seja uniforme. Algumas linhas surgiram como resultado de interferência construtiva de amplitudes e, portanto, têm maior probabilidade, e outras como resultado de destrutivas, e têm menor probabilidade. E, embora obtenhamos apenas uma pequena fração de todas as amostras possíveis de 2
n , podemos verificar estatisticamente a distribuição dessas amostras quanto à distribuição desigual esperada e garantir que obtemos algo difícil de reproduzir classicamente.
TL; DR, um computador quântico é solicitado a aplicar uma sequência aleatória (mas conhecida) de operações quânticas - não porque estamos interessados no resultado, mas porque estamos tentando provar que o CQ pode executar essa tarefa claramente definida melhor do que um computador clássico.
B4 Mas se um computador quântico apenas executa algum código indesejado, cujo único objetivo é difícil para a simulação clássica, quem se importa? Isso não é uma grande torta com ... nada?Não. Isso, é claro, não é uma torta com tudo saboroso, mas pelo menos uma torta com alguma coisa.
Tenha pelo menos um pouco de respeito pela imensidão do que estamos falando aqui e que tipo de gênio da engenharia foi necessário para traduzir isso em realidade. Antes da superioridade quântica (KP), os céticos da KP simplesmente riam que, mesmo depois de bilhões de dólares e mais de 20 anos de trabalho, um computador quântico ainda não pode fazer algo mais rápido que o seu laptop. Pelo menos não usando quantumness. Depois de alcançar a supremacia quântica no mundo, eles não riem mais. A superposição de 2
50 ou 2
60 números complexos foi calculada usando um recurso significativamente menor de tempo e volume de dados que 2
50 ou 2
60Estou falando do avião Wright apenas porque a diferença entre o que estamos falando e a negação, algo que vejo em diferentes partes da Internet, é completamente incompreensível. É como se você acreditasse que era impossível voar em princípio e depois visse um avião de madeira frágil - ele pode não abalar sua fé, mas certamente não deve fortalecê-lo.
Eu estava certo,
preocupando-me há muitos anos que o hype constante sobre as conquistas muito menores do KK cansará as pessoas e elas se importarão quando algo realmente interessante finalmente acontecer?
B5 Muitos anos atrás, você culpou as massas pelo entusiasmo pelo D-Wave e pelas reivindicações de uma impressionante vantagem quântica nos problemas de otimização usando o recozimento quântico. Agora você os repreende por sua falta de entusiasmo pela superioridade quântica. Por que você é tão inconstante?Porque meu objetivo não é mudar o nível de entusiasmo em uma direção claramente escolhida, mas estar certo. Em retrospectiva, eu não estava certa sobre o D-Wave, mesmo quando minhas declarações me deixaram impopular em alguns círculos? Bem, agora estou tentando estar certo sobre a superioridade quântica também.
B6 Se os cálculos de superioridade quântica são simplesmente baseados em amostras de uma distribuição de probabilidade, como verificar se eles são feitos corretamente?Obrigado por perguntar! Este é precisamente o tópico sobre o qual eu e outros desenvolvemos muitos fundamentos teóricos nos últimos dez anos. Eu já contei a versão curta na minha resposta B3: você testa isso executando testes estatísticos nas amostras que o computador quântico distribui para verificar se elas estão concentradas em torno dos picos da distribuição de probabilidade aleatória D
C. Uma maneira conveniente de fazer isso, que o Google chama de "teste de entropia linear linear", é simplesmente somar todos os Pr [C rendimentos s
i ] para todas as amostras s
1 , ...,
sk que KK retornou e depois declarar o teste com êxito se e somente se a soma exceder um certo nível - digamos, bk / 2
n , onde b é uma constante entre 1 e 2.
Honestamente, para aplicar esse teste, você precisa calcular todas as probabilidades que Pr [C fornece] em um computador clássico - e a única maneira conhecida de fazer isso é iterar em um tempo de ~ 2
n . Mas isso incomoda alguém? Não, se n = 50, e você pesquise no Google e poderá contar números como 2
50 (embora não receba 2
1000 , o que é superior ao
google , khe-khe). Tendo expulsado um grande conjunto de núcleos clássicos por, digamos, um mês, você terá o resultado que o CC produziu em alguns segundos - ao mesmo tempo, verifique se o CC é um par de pedidos mais rápido. No entanto, isso significa que experimentos baseados em amostragem são quase especialmente projetados para dispositivos com ~ 50 qubits. Mesmo com 100 qubits, não temos idéia de como garantir o resultado, mesmo usando toda a capacidade de computação disponível na Terra.
(Observo separadamente que esse problema é específico apenas para experimentos de amostragem, semelhante ao que está sendo realizado agora. Se você usou o algoritmo Shor para fatorar um número de 2000 dígitos, pode verificar facilmente o resultado simplesmente multiplicando todos os fatores e verificando sua simplicidade. se KK for usado para simular uma biomolécula complexa, você poderá verificar o resultado experimentando a molécula.)
B7 Espere um momento. Se os computadores clássicos podem apenas verificar os resultados de um experimento de superioridade quântica apenas em um modo em que os computadores clássicos ainda podem simular um experimento (embora muito lentamente), como se pode falar em "superioridade quântica"?Bem, então você. Com um chip de 53 qubit, você vê a aceleração vários milhões de vezes e ainda pode verificar o resultado e também verificar se a aceleração cresce exponencialmente com o número de qubits, exatamente como prevê a análise assintótica. Isso não é insignificante.
B8 Existe alguma evidência matemática de que nenhum computador clássico rápido possa vencer os resultados de um experimento de KP baseado em amostragem?Não no momento. Mas isso não é culpa dos pesquisadores da superioridade quântica! Enquanto os teóricos não puderem provar hipóteses básicas, como P ≠ NP ou P ≠ PSPACE, e sem isso, não podemos excluir incondicionalmente a possibilidade de uma simulação clássica rápida. O melhor que podemos esperar é a complexidade condicional. E temos alguns resultados sobre isso, por exemplo, um artigo sobre
amostragem de bósons ou
um artigo de Bouldand et al. sobre a complexidade média # P do cálculo das amplitudes de circuitos aleatórios, ou meu
artigo com Lijie Chen ("Fundamentos teóricos da complexidade de experimentos de supremacia quântica"). A questão aberta mais importante nessa área, na minha opinião, é a prova das melhores dificuldades condicionais.
B9 Existe algum uso para amostrar superioridade quântica?Até recentemente, a resposta era obviamente não! (E eu sei, porque eu próprio era uma dessas pessoas). Recentemente, no entanto, a situação mudou - por exemplo, graças ao meu protocolo de
aleatoriedade certificado , que mostra como o KP com base em amostragem pode ser usado independentemente para gerar bits que podem ser provados aleatórios mesmo para terceiros céticos (sob premissas sobre cálculos). Por sua vez, isso tem um aplicativo em criptomoeda e outros protocolos criptográficos. Espero que mais dessas aplicações cheguem em breve.
B10 Se experimentos de superioridade quântica os bits aleatórios geram tudo, por que isso é interessante? Não é possível converter trivialmente qubits em bits aleatórios simplesmente medindo-os?A conclusão é que o QC gera bits aleatórios não uniformemente distribuídos. Em vez disso, cria uma seleção de uma distribuição de probabilidade complexa e correlacionada em cadeias de 50 a 60 bits. No meu protocolo, os desvios da uniformidade desempenham um papel central na maneira como o CQ convence o cético de que ele realmente selecionou bits aleatórios, em vez de usar algum tipo de gerador pseudo-aleatório em segredo.
B11 Décadas de experimentos em mecânica quântica, por exemplo, com violação da desigualdade de Bell, não demonstraram superioridade quântica?Esta é uma pergunta puramente lexical. Esses experimentos demonstraram outros tipos de superioridade quântica: por exemplo, no caso da desigualdade de Bell, eles podem ser chamados de "superioridade da correlação quântica". Eles não mostraram superioridade computacional quântica, ou seja, a capacidade de encontrar algo inacessível a um computador clássico (onde a simulação clássica não tem restrições espaciais localmente, etc.). Atualmente, quando as pessoas usam a frase "superioridade quântica", elas significam superioridade computacional quântica.
B12 Mesmo assim, não existem inúmeros exemplos de materiais e reações químicas que são difíceis de simular classicamente e simuladores quânticos especialmente construídos (como os do grupo Lukin em Harvard). Por que eles não são considerados superioridade da computação quântica?Nas definições de algumas pessoas, elas são consideradas! A principal diferença com um computador do Google é que eles têm um computador totalmente programável - você pode inserir qualquer sequência arbitrária de portas de 2 qubit (para qubits vizinhos) simplesmente digitando comandos de um computador clássico.
Em outras palavras, os céticos da KP não conseguem mais perceber zombeteiramente que, é claro, os sistemas quânticos são difíceis de simular classicamente, mas isso é simplesmente porque a natureza geralmente é difícil de simular, e você não pode reprogramar a molécula aleatória encontrada no campo em um computador para simular a si mesma. você mesmo. Por qualquer definição razoável, os dispositivos supercondutores criados pelo Google, IBM e outros são computadores no sentido pleno da palavra.
B13 Você (Scott Aaronson) inventou o conceito de excelência quântica?Não. Eu desempenhei um papel no seu desenvolvimento e, portanto, por exemplo, Sabina Hosenfelder, entre outros,
atribuiu erroneamente a autoria de toda a ideia a
mim . O termo "superioridade quântica" foi proposto por John Preskill em 2012, embora, em certo sentido, a idéia básica tenha surgido no início das contribuições quânticas no início dos anos 80. Em 1994, o uso do algoritmo Shore para fatorar um grande número tornou-se o principal experimento para testar a superioridade quântica, embora no momento isso ainda seja muito difícil de produzir.
A idéia principal de que a amostragem pode ser usada foi, até onde eu sei, proposta pela primeira vez por Barbara Terhal e David DiVincenzo em
um artigo de 2002. O esforço atual em um PC amostrado começou por volta de 2011, quando Alex Arkhipov e eu publicamos nosso artigo sobre
amostragem bosônica , e Bremner, Jozsa e Shepherd publicaram independentemente
um artigo sobre modelos de deslocamento de Hamiltonianos . Esses artigos mostraram não apenas sistemas quânticos “simples”, não universais que podem resolver problemas de amostragem obviamente complexos, mas também que a existência de um algoritmo clássico eficaz significaria uma queda na
hierarquia polinomial . Arkhipov e eu também lançamos as bases para o argumento de que mesmo versões aproximadas da amostragem quântica podem ser classicamente complexas.
Até onde eu sei, a idéia de “circuitos de amostragem aleatória” - isto é, gerando um problema complexo de amostragem selecionando aleatoriamente uma sequência de portas de 2 qubit em, digamos, uma arquitetura supercondutora - surgiu sua correspondência, iniciada em dezembro de 2015, que incluía John Martinis, Hartmut Neven , Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg e outros. O tópico foi intitulado "Desafiando problemas de amostragem com 40 Qubits" e a carta começou com "Desculpe por spam".
Nele, discuti as várias vantagens e desvantagens de três opções para demonstrar uma vantagem quântica usando amostragem: (1) circuitos aleatórios, (2) pendulares Hamiltonianos, (3) amostragem de bósons. Depois que Greg Cooperberg defendeu a opção (1), rapidamente se formou um consenso de que (1) seria realmente a melhor opção do ponto de vista da engenharia e que, se ainda não temos uma justificativa teórica satisfatória para (1), podemos de alguma forma contornar isso.Depois disso, a equipe do Google fez um ótimo trabalho ao analisar esquemas de amostragem aleatória, tanto teórica quanto numericamente, enquanto Lijie Chen e eu e Bouland et al. forneceu evidências diferentes da complexidade clássica desse problema do ponto de vista da teoria da complexidade.B14 Se a superioridade quântica é alcançada, o que isso significa para os céticos?Uau, eu não gostaria de estar no lugar deles agora! Eles podem voltar à posição de que, bem, é claro, a superioridade quântica é possível (e quem disse o contrário? Bem, é claro que não são!) E toda a dificuldade sempre esteve na correção de erros quânticos. E, de fato, alguns disseram isso desde o início. Outros, meu bom amigo Gil Kalai, entre eles, escrevendo neste blog, previram que a superioridade quântica nunca seria alcançada por razões fundamentais. Agora eles não serão ferrados.B15 Então, o que vem a seguir?Se isso for realmente alcançado superioridade quântica, acho que o grupo do Google tem todo o hardware para demonstrar meu protocolo para geração aleatória certificada de bits. E essa é realmente uma das seguintes coisas em seu plano.Além disso, o próximo passo óbvio é usar um CQ programável, com 50 a 100 qubits, para algumas simulações quânticas úteis (por exemplo, um sistema com um estado condensado da matéria) muito mais rápido do que qualquer método clássico. E o segundo passo óbvio é demonstrar o uso da correção de erros para manter o qubit lógico ativo por mais tempo que o tempo de vida dos qubits físicos nos quais se baseia. Não há dúvida de que a IBM, o Google e o resto dos jogadores se perseguirão pela primazia nessas etapas.