Soberba Quantum Excellence Perguntas e Respostas

De um blog de Scott Joel Aronson, especialista em ciência da computação e sistemas, professor do Departamento de Ciência da Computação da Universidade do Texas em Austin

Você lê essas histórias - no Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [ no Habr / aprox. transl.] ou em outro lugar - que um grupo de pesquisadores do Google alcançou superioridade da computação quântica com seu dispositivo supercondutor de 53 qubit. Eles são fáceis de encontrar, mas eu não darei links para eles - simplesmente porque eles ainda não deveriam existir.

O mundo sabe que o Google está realmente preparando um grande anúncio de excelência quântica, que deve sair simultaneamente com a publicação de trabalhos de pesquisa em uma das revistas científicas respeitadas. E é provável que isso aconteça dentro de um mês.

Enquanto isso, a NASA, que participou desse desenvolvimento, publicou acidentalmente uma versão antiga do Google em um site público. Ela passou pouco tempo lá, mas o suficiente para chegar ao Financial Times, minha caixa de entrada e milhões de outros lugares. Argumentos sobre esse trabalho, desprovidos de fatos, estão previsivelmente espalhados por toda parte.

Aparentemente, nosso mundo foi privado da oportunidade de anunciar claramente um novo momento de "entrada do homem no espaço", no qual a forte tese de Church-Turing será refutada experimentalmente em uma conferência de imprensa. Será mais como o vôo dos irmãos Wright, rumores fragmentados sobre os quais surgiram de 1903 a 1908, nos quais Wilbur e Orville finalmente concordaram em voos de demonstração (apenas no nosso caso, felizmente, isso esclarecerá a questão. quanto menos tempo!)

Estou atualizado há alguns meses; foi extremamente difícil para mim não escrever sobre isso no meu blog. Prometi ficar em silêncio, mas não pude resistir ao desejo de deixar dicas diferentes aqui e ali - por exemplo, durante minha palestra no último evento dedicado a Paul Bernays , construí especialmente o curso de minhas palestras para que elas cheguem a esse ponto.

Esta entrada é o anúncio oficial que confirma esses fatos. E se um raio já estiver visível para nós, o direito de expressar o trovão pertence a um grupo de pesquisadores do Google, bem como a hora e o local para isso.

Em vez disso, decidi esclarecer essa questão, esclarecer as desinformações que circulam na Internet em meu papel de blogueiro e "intelectual social" e apresentar a você "Um excelente conjunto de perguntas e respostas sobre a superioridade quântica de Scott". Apenas para o caso de você se interessar de repente pela superioridade quântica ou desejar saber o que aconteceria se alguma empresa de mecanismos de pesquisa de Mountain View ou outro local anunciasse hipoteticamente a conquista da superioridade quântica .

Bem, não vamos puxar o gato pela cauda:

Pergunta 1: O que é excelência computacional quântica?

Este termo é frequentemente abreviado simplesmente para superioridade quântica (KP). Denota o uso de um computador quântico (CQ) para resolver um certo conjunto bem definido de problemas, cuja solução, usando os algoritmos conhecidos de hoje nos computadores clássicos de hoje, levará ordens de magnitude mais tempo - e não apenas assim, mas por causa da complexidade quântica assintótica. A ênfase aqui está em ter 100% de certeza de que a tarefa está sendo resolvida no CQ, e ela realmente não pode ser abordada com a ajuda de computadores clássicos; Idealmente, a tarefa deve ser tal que já possa ser resolvida em um futuro próximo (com a ajuda de CQs ruidosos e não universais que já existem ou aparecerão em breve). E se essa tarefa ainda for útil, melhor - mas isso não é necessário. O avião dos Irmãos Wright ou o Woodpile de Chicago não eram úteis em si mesmos.

P2: Se os pesquisadores do Google realmente alcançaram HF, isso significa que "qualquer código pode ser invadido", como twittou recentemente o candidato à presidência do Partido Democrata dos EUA, Andrew Young?



Não é verdade (embora como candidato, Young seja bonito para mim).

Existem dois problemas. Em primeiro lugar, os dispositivos que o Google, IBM e outros estão criando hoje consistem em 50 a 100 qubits e não possuem um sistema de correção de erros. Para executar o algoritmo Shore para quebrar a criptografia RSA, são necessários vários milhares de qubits lógicos. E com os métodos de correção de erros conhecidos hoje em dia, isso pode exigir milhões de qubits físicos e a qualidade é melhor que os existentes. Acho que ninguém se aproximou disso e não sabemos quanto tempo levará.

Em segundo lugar, mesmo em um futuro hipotético, QCs escaláveis ​​com correção de erros, como nos parece hoje, serão capazes de decifrar alguns códigos, mas não todos. Coincidentemente, as chaves públicas que eles podem quebrar incluem a maioria das chaves que usamos hoje para segurança na Internet: RSA, o protocolo Diffie-Hellman, curvas elípticas, etc. A criptografia de chave privada terá um impacto mínimo. E também há candidatos a sistemas de chave pública (por exemplo, com base em gratings), cujo método de hacking não é conhecido por ninguém há 20 anos de tentativas de controle de qualidade; além disso, já estão sendo feitas tentativas de mudar para esses sistemas. Os detalhes estão na minha carta a Rebecca Goldstein .

T3: que cálculos, considerados classicamente complexos, o Google planeja realizar ou já fez?

Eu posso dizer, embora eu tenha vergonha. Os cálculos são os seguintes: o "testador" gera um circuito quântico aleatório C (uma sequência aleatória de portas de 1 qubit e o segundo qubit mais próximo a ela, profundidade de cerca de 20, em uma rede bidimensional de 50-60 qubits). Em seguida, o testador envia C ao computador quântico e o instrui a aplicar o circuito no estado inicial de 0, medir o resultado com a base {0,1}, enviar a sequência observada de n bits e repetir isso vários milhares ou milhões de vezes. Finalmente, usando seu conhecimento de C, o testador clássico aplica um teste estatístico para verificar se a saída confirma que o CQ executou os cálculos.

Ou seja, não é uma tarefa como fatorar, ter uma resposta correta. O circuito C produz uma distribuição de probabilidade, vamos chamá-lo de D _C , sobre cadeias de n bits, e a tarefa é produzir amostras dessa distribuição. De fato, 2 ⁿ linhas falarão em apoio a D _C - e haverá tantas que, se o CQ funcionar como deveria, nunca veremos a mesma saída. Importante, a distribuição de D _C não _é uniforme. Algumas linhas sofrerão interferência construtiva de amplitudes, e suas probabilidades serão maiores, enquanto outras sofrerão interferência destrutiva, e suas probabilidades serão menores. E embora vejamos apenas algumas amostras, cujo número será pequeno em comparação com 2 ⁿ , podemos verificar se elas gravitam nas linhas, o que consideramos mais prováveis, e no final isso aumentará nossa confiança de que algo classicamente inatingível está acontecendo .

Simplificando, o KK será solicitado a executar uma sequência aleatória (mas conhecida) de operações - não porque precisamos de um resultado específico, mas porque estamos tentando provar que ele pode se antecipar a um computador clássico em alguma tarefa claramente definida.

Q4: Mas se o KK existe apenas para distribuir lixo aleatório, o único significado é que é difícil simular em um computador clássico, quem se importa? Não é um sanduíche enlatado sem nada?

Não. Como já escrevi, este não é um sanduíche com tudo de uma só vez, mas definitivamente um sanduíche com alguma coisa!

Respeite a imensidão do tópico em discussão e as realizações de engenharia terrivelmente complexas necessárias para sua implementação. Antes do início do PC, os céticos podem se divertir ao mesmo tempo que, depois de todos os bilhões gastos em mais de 20 anos, nenhum CQ foi usado para resolver uma tarefa que seria mais rápida do que o seu laptop, ou pelo menos o problema não poderia ser resolvido de uma maneira que depende da natureza quântica deste computador. Mas no mundo do próximo KP, isso já está errado. Uma superposição de 2 ⁵⁰ ou 2 ⁶⁰ números complexos foi dominada computacionalmente, usando tempo e recursos mínimos em comparação com 2 ⁵⁰ ou 2 ⁶⁰ .

Lembro-me constantemente do avião dos irmãos Wright porque estou impressionado com o abismo entre o que estamos falando e a negligência na Internet de todos os lados neste tópico. Isso é semelhante à reação de uma pessoa que acreditava firmemente que era impossível fazer uma viagem útil pelo ar e, em seguida, ele viu um avião de hélice de madeira simples pairando no ar - esse espetáculo não refutaria suas opiniões, mas também não o apoiaria.

Fiquei realmente preocupado durante todos esses anos à toa que o constante hype sobre os marcos muito menos significativos alcançados pelo CC esgotará a paciência das pessoas e elas não se importarão quando algo realmente interessante acontecer?

Q5: Muitos anos atrás, você envergonhou as massas por elogiar o D-Wave e suas declarações sobre a enorme aceleração quântica de resolver problemas de otimização através do recozimento quântico. Agora você tem vergonha das massas de não estarem suficientemente entusiasmadas com o Partido Comunista. Por que você não decide?

Porque meu objetivo não é liderar o "nível de entusiasmo" em nenhuma direção específica, mas garantir que esteja correto! Você não pode dizer, olhando para trás, que geralmente eu estava certo sobre o D-Wave, mesmo quando minhas críticas a esse tópico me deixaram impopular em alguns círculos? Então, sobre o KP, eu também tento estar certo.

P6: Se os cálculos relacionados ao KP levam em consideração apenas amostras da distribuição de probabilidade, como posso verificar se os cálculos estão corretos?

Que bom que você pediu! Essa é uma questão da teoria que nós e outros cientistas desenvolvemos na última década. Eu já expliquei brevemente em B3: os cálculos podem ser verificados estatisticamente a partir das amostras retornadas pelo CQ, e certifique-se de que eles preferem adicionar aos "picos" da distribuição de probabilidade D _C. Uma das maneiras convenientes de fazer isso é o que o Google chama de "verificação de entropia linear linear": é somar Pr [C output s _i ] para todas as amostras s ₁ , .., _k que o QC produz e depois declarar a verificação bem-sucedida se esse valor sair além de um certo limite - por exemplo, bk / 2 ⁿ para uma constante 1 <b <2.

Obviamente, para realizar esse teste, é necessário calcular as probabilidades Pr [C output si] em um computador clássico - e a única maneira de fazer isso é levar 2 ⁿ tempo exaustivamente. Existe algum problema com isso? Não, se n = 50, e você é o Google e pode processar números como 2 ⁵⁰ (embora não possa lidar com 2 ¹⁰⁰⁰ , um número que excede o googol - ha, ha). Ao iniciar um cluster de kernels clássicos em algum lugar por um mês, você poderá confirmar a saída correta do seu QC, que foi emitida em alguns segundos - e ao mesmo tempo em que o QC trabalha muitas ordens de magnitude mais rapidamente. No entanto, isso também significa que experimentos de CP baseados em amostragem são projetados para os dispositivos de 50 qubit que eles criam hoje. E mesmo com cem qubits, não poderíamos confirmar os resultados do CQ, mesmo usando todo o poder computacional do planeta.

Enfatizo que esse problema é típico para experimentos com amostras semelhantes à que estamos conduzindo agora. Se o algoritmo Shore fatorasse um número de 2.000 dígitos, verificaríamos isso facilmente, multiplicando os fatores resultantes e verificando se eles pertencem a números primos. Ou, se o CC fosse usado para simular uma biomolécula complexa, poderíamos testar sua operação em um experimento.

Q7: Espere um minuto. Se os computadores clássicos podem verificar os resultados de um experimento no KP apenas no modo de simulação do experimento (embora lento), como isso pode ser uma "superioridade quântica"?

Venha você. Com um chip de 53 qubits, é bastante lógico esperar vários milhões de vezes a aceleração em um modo em que você ainda possa verificar diretamente o resultado do trabalho e também ver que a aceleração aumenta exponencialmente com um aumento no número de qubits - exatamente como a análise assintótica previu.

Q8: Existe alguma prova matemática de que não existe um algoritmo clássico rápido que ultrapassaria o experimento KP com amostragem?

Hoje não. Mas isso não é culpa dos pesquisadores da KP! Os especialistas em informática teórica são incapazes de provar as hipóteses mais simples, como P ≠ NP ou P ≠ PSPACE, portanto, você não deve esperar que seja possível excluir inequivocamente a presença de uma simulação clássica rápida. Só podemos esperar a complexidade condicional. E nós realmente provamos alguns desses resultados . O maior problema teórico nessa área é a prova dos melhores resultados da complexidade condicional.

Q9: O próprio quadro de amostragem tem algum uso útil?

Ao pensar neste tópico pela primeira vez, as pessoas geralmente acreditavam que a resposta óbvia a essa pergunta era "não" (e eu era uma delas). Mas ultimamente, a situação mudou - por exemplo, graças ao meu protocolo de aleatoriedade confirmada, que demonstra como um experimento com um CP com uma amostra pode ser transformado muito rapidamente em um gerador de bits, cuja aleatoriedade pode ser comprovada para um observador terceirizado cético (sob algumas suposições computacionais). E isso pode ser potencialmente aplicado à criação de criptomoedas PoS e outros protocolos criptográficos. Espero que em um futuro próximo mais dessas aplicações sejam descobertas.

Q10: Se os experimentos com KP gerarem bits aleatórios, isso é interessante? Não é uma tarefa trivial transformar qubits em bits aleatórios simplesmente medindo-os?

A conclusão é que o experimento com o KP não gera bits aleatórios uniformes. Ele faz uma seleção de uma distribuição de probabilidade correlacionada complexa em linhas de 50 ou 60 bits. No meu protocolo de aleatoriedade confirmada, os desvios da homogeneidade desempenham um papel central em como o PC pode convencer um cético clássico de que os bits são realmente aleatórios e não têm um sistema secreto (como um gerador de números pseudo-aleatórios).

P11: Mas há décadas de experimentos em mecânica quântica - por exemplo, aqueles que violam as desigualdades de Bell - ainda não demonstraram KP?

Isso é apenas uma confusão em termos. Esses experimentos mostraram outros tipos de "superioridade quântica". Por exemplo, no caso de violação das desigualdades de Bell, era "superioridade da correlação quântica". Não mostrou superioridade computacional, isto é, algo que não pode ser simulado em um computador clássico (apesar do fato de que a simulação clássica não teria restrições à localidade espacial ou algo assim). Hoje, as pessoas geralmente querem dizer superioridade da computação quântica por KP.

Q12: Bem, mas existem inúmeros exemplos de materiais e reações químicas que são difíceis de simular classicamente, bem como simuladores quânticos especiais (por exemplo, o grupo Lukin de Harvard). Por que eles não são considerados exemplos de KP?

Por algumas definições, eles podem ser considerados exemplos de KP! A principal diferença entre o trabalho dos pesquisadores do Google é que o dispositivo é totalmente programável - ele pode ser programado em uma sequência arbitrária de portas de 2 qubit com o vizinho mais próximo, simplesmente enviando os sinais necessários de um computador quântico.

Em outras palavras, os KP-céticos não podem mais reclamar que, dizem eles, se existem sistemas quânticos difíceis de simular classicamente, é apenas porque a natureza é difícil de simular e não podemos mudar arbitrariamente qual composto químico aleatório encontrado em natureza, portanto, esses sistemas não podem ser considerados "computadores que se simulam". Por qualquer definição razoável, os dispositivos supercondutores que o Google, a IBM e outras empresas estão construindo hoje são computadores reais.

Q13: Você inventou o conceito de superioridade quântica?

Não. Eu desempenhei um papel em sua definição, razão pela qual Sabina Hossenfelder e outros atribuíram a mim um papel muito grande nessa idéia. O termo "superioridade quântica" foi cunhado por John Preskill em 2012, embora, de certa forma, o conceito-chave remonte ao início da própria computação quântica no início dos anos 80. Em 1994, o uso do algoritmo Shore para fatorar grandes números tornou-se um experimento real no campo do KP - embora esse problema seja muito difícil de resolver hoje.

A essência da idéia, que era demonstrar o PC usando o problema de amostragem, tanto quanto eu sei, foi proposta pela primeira vez por Barbara Theral e David Divincenzo em um trabalho visionário de 2002. As tentativas "modernas" de organizar experimentos começaram em 2011, quando Alex Arkhipov e eu publicamos nosso trabalho na BosonSampling, e Bremner, Josa e Shepherd publicaram nosso trabalho sobre Hamiltonianos alternados. Esses trabalhos mostraram não apenas que sistemas quânticos “simples” e não universais podem resolver problemas aparentemente complexos com a amostragem, mas também que um algoritmo clássico eficaz para esses problemas levará ao colapso da hierarquia polinomial . Arkhipov e eu também demos os primeiros passos para provar que mesmo versões aproximadas de problemas de amostragem quântica podem ser classicamente complexas.

Até onde eu sei, a idéia de “amostragem aleatória de circuitos” - isto é, gerando um problema complexo de amostragem por meio da seleção de sequências aleatórias de válvulas de 2 qubit em uma arquitetura supercondutora - apareceu na correspondência por e-mail que eu comecei em dezembro de 2015, na qual John também participou Martinis, Hartmut Niven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Josa, Aram Harrow, Greg Cooperberg e outros.A correspondência foi chamada de "um problema difícil de amostragem de 40 qubit", e minha carta começou com as palavras "desculpe spam". Discuti algumas das vantagens e desvantagens de três opções para demonstrar o KP com amostragem: (1) contornos aleatórios, (2) hamiltonianos comutados, (3) BosonSampling. Depois que Cooperberg defendeu a primeira opção, um consenso rapidamente se formou entre os participantes,que a primeira opção foi realmente a melhor do ponto de vista da engenharia - e que, se a análise teórica existente para (1) não for suficiente, poderemos criar alguma coisa.

Depois disso, um grupo do Google conduziu um grande número de análises de amostras de contornos aleatórios, tanto teóricas quanto numéricas, e Lijie Chen e Buland e meus colegas apresentaram evidências de vários tipos para a complexidade clássica do problema.

Q14: Se o KP for alcançado, o que isso significa para os céticos?

Eu não gostaria de estar no lugar deles! Eles podem mudar para uma posição em que o KP é possível (e quem disse que é impossível? Certamente não são!) E essa correção quântica de erros sempre foi um problema real. E muitos deles realmente apoiaram essa posição específica. Mas outros, incluindo meu amigo Gil Kalay, bem aqui em um post no blog, argumentaram que o KP não poderia ser alcançado por razões fundamentais. E eu não vou deixar eles sairem.

Q15: O que vem depois?

Atingir o KP significa que o grupo do Google já possui o equipamento necessário para demonstrar meu protocolo para gerar bits aleatórios confirmados. E essa é realmente uma das primeiras coisas que planejamos fazer.

O próximo marco óbvio será o uso de um CQ programável com 50 a 100 qubits para simulações quânticas úteis (por exemplo, sistemas de estado condensado) mais rápidas do que qualquer método clássico conhecido. O segundo marco óbvio será a demonstração do uso da correção de erros quânticos, para que o qubit codificado viva mais do que os qubits físicos subjacentes. Não há dúvida de que o Google, a IBM e outros players competirão para lutar por esses dois marcos.

Depois de publicar o artigo, Steve Girwin me lembrou que o grupo de Yale já havia alcançadocorreção de erro quântico, embora no sistema bosônico, e não no sistema de qubits supercondutores. Portanto, talvez, o próximo marco seja melhor formulado da seguinte forma: alcançar superioridade computacional quântica e correção de erro quântico útil em um sistema.