Esta página traz resumos em linguagem simples de artigos de física. Não fazemos ligação com Dost nem com outro texto; ler lado a lado é tarefa do próprio leitor.
Experimento: medido. Teoria: calculada ou demonstrada. Interpretação: seu significado é disputado. Os rótulos são nossa própria classificação; um artigo pode ter mais de uma natureza.
Pergunta principal: Como se define um computador quântico e em que ele difere de um computador clássico?
O modelo matemático do computador clássico é a máquina de Turing. Em 1985, Deutsch perguntou: se a física funciona segundo a mecânica quântica, o modelo mais geral de computação não deveria também se basear na mecânica quântica? O artigo reformula a hipótese de Church-Turing como um princípio físico e define uma máquina de calcular quântica universal.
Nesta página16. O Computador Quântico Universal · Deutsch 1985 — Quantum theory, the Churc · 17. O Algoritmo de Shor …
Proceedings of the Royal Society A 400, 97–117 teoria
Artigo que formula a hipótese de Church-Turing como um princípio físico e introduz os conceitos de máquina de Turing quântica e de computador quântico universal.
O ponto de partida do artigo é este: a hipótese de Church-Turing diz que tudo o que é "computável" pode ser computado por uma máquina de Turing. Deutsch sustenta que há, implícita sob essa hipótese, uma afirmação física, e a escreve abertamente como um princípio: "todo sistema físico finitamente realizável pode ser perfeitamente simulado por uma máquina de calcular modelo universal que opere por meios finitos."
O autor observa que a física clássica e a máquina de Turing universal não satisfazem esse princípio, pois a primeira é contínua e a segunda é discreta. Em contraste, ele define uma classe de máquinas de calcular que é uma generalização quântica das máquinas de Turing, e mostra que a teoria quântica e o "computador quântico universal" são compatíveis com esse princípio.
Diz-se que essas máquinas têm propriedades que nenhuma máquina de Turing pode ter. Entre elas não está o cálculo de funções não recursivas; mas há o "paralelismo quântico": certas tarefas probabilísticas podem ser realizadas mais rapidamente por um computador quântico universal do que por uma restrição clássica dele. O autor argumenta que a explicação intuitiva desse paralelismo impõe um fardo pesado às interpretações que não sejam a de Everett; essa é uma alegação de interpretação e é discutível, e o artigo não apresenta resultado experimental sobre o assunto.
Por fim, o artigo examina os laços da teoria da computação quântica com o resto da física; sugere-se que a teoria da complexidade quântica dá uma definição mais razoável da "complexidade" ou da "informação" de um sistema físico do que a teoria da complexidade clássica.
As duas alegações distintas do artigo são avaliadas separadamente: a definição do modelo de computação quântica e os cálculos que esse modelo faz de modo diferente do clássico são um resultado matemático; a interpretação ligada à interpretação de Everett, por sua vez, é um ponto de vista e é discutível.
Depois: Em 1993, Bernstein e Vazirani retomaram esse modelo do ponto de vista da teoria da complexidade (tema 19 neste arquivo).
17. O Algoritmo de Shor
Pergunta principal: Números grandes podem ser fatorados rapidamente?
Decompor um número em seus fatores primos leva muito tempo, para números grandes, pelos métodos clássicos conhecidos; criptografias difundidas como o RSA se apoiam nessa dificuldade. Em 1994, Shor mostrou que, em um computador quântico hipotético, a mesma tarefa pode ser feita em tempo polinomial no número de dígitos do número. Isso se tornou uma das razões mais fortes para o interesse na computação quântica.
Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), 124–134; tam sürüm: SIAM J. Comput. 26 (1997) 1484–1509, arXiv:quant-ph/9508027 teoria
Artigo que dá algoritmos de tempo polinomial, em um computador quântico, para fatorar inteiros e calcular logaritmos discretos.
A pergunta inicial do artigo é se o computador é um dispositivo de cálculo universal: um computador clássico pode simular qualquer dispositivo físico de cálculo com, no máximo, uma perda polinomial de tempo? Levando em conta a mecânica quântica, isso é incerto. O artigo trata de dois problemas: a fatoração de inteiros e a obtenção do logaritmo discreto. Ambos são considerados difíceis em um computador clássico e são a base de muitas propostas criptográficas.
Para os dois problemas, o autor dá algoritmos aleatorizados em um computador quântico hipotético que executam um número de passos polinomial no tamanho da entrada, isto é, no número de dígitos do número. O artigo de 1994 os apresenta como algoritmos "Las Vegas" e observa que são os primeiros exemplos de quebra de cifras quântica.
O núcleo do método pode ser resumido assim: a fatoração é reduzida a encontrar o período de uma certa função. O computador quântico calcula a função sobre muitas entradas em superposição; depois, a transformada de Fourier quântica torna legível o padrão de interferência que revela o período. Encontrado o período, o resto é cálculo clássico comum. Este resumo descreve a estrutura conhecida do algoritmo, e não o texto do artigo.
O artigo não apresenta uma realização em hardware. Também não mostra que a fatoração em um computador clássico é realmente difícil; essa dificuldade é geralmente presumida. O que o artigo mostra é que esses problemas podem ser resolvidos em tempo polinomial em um computador quântico.
A importância do resultado é dupla: ele mostra que o cálculo quântico pode ser exponencialmente mais rápido que o clássico em um problema de dificuldade amplamente presumida; por outro lado, essa velocidade só pode ser obtida com um computador quântico suficientemente grande e com correção de erros. O próprio artigo não é uma proposta de construir tal máquina.
Depois: A versão completa do artigo foi publicada em 1997 no SIAM Journal on Computing. A correção de erros necessária para executar esse algoritmo em tamanhos reais é o campo do tema 15 deste arquivo.
18. O Algoritmo de Grover
Pergunta principal: Os problemas de busca podem ser acelerados?
Para encontrar o item procurado em uma lista não ordenada, não há um bom caminho clássico além de verificar os itens um a um. Em 1996, Grover mostrou que um computador quântico consegue fazer isso em um número de passos igual à raiz quadrada do número de itens. O ganho de velocidade não é exponencial, como no algoritmo de Shor, mas da ordem da raiz quadrada; vale, porém, para um problema de busca geral.
Proc. 28th Annual ACM Symposium on Theory of Computing (STOC '96), 212–219 teoria
Artigo que dá um algoritmo quântico de O(√N) passos para busca em um banco de dados não ordenado.
O autor explica o problema com o exemplo de uma lista telefônica: N nomes estão dispostos ao acaso e deseja-se encontrar o número de uma determinada pessoa. Para uma probabilidade de sucesso de cinquenta por cento, um algoritmo clássico (determinístico ou probabilístico) precisa verificar pelo menos N/2 nomes.
Como os sistemas quânticos podem estar em superposição, eles podem "verificar" muitos nomes ao mesmo tempo. No algoritmo proposto no artigo, as fases de várias operações são cuidadosamente ajustadas: os cálculos bem-sucedidos se reforçam mutuamente, enquanto os demais se anulam de modo aleatório. Como resultado, o número procurado pode ser obtido em apenas O(√N) passos. Ou seja, em vez do N/2 clássico, são necessários passos da ordem da raiz quadrada. A estrutura conhecida do algoritmo é a repetição das mesmas duas operações: inverter a fase do item procurado e refletir as amplitudes em relação à média de todos os itens; a cada rodada a amplitude do item procurado aumenta um pouco.
O artigo diz ainda que esse algoritmo está a um pequeno fator constante do algoritmo quântico mais rápido possível. Ou seja, não se espera uma aceleração quântica maior para uma busca geral (sem estrutura); o ganho fica limitado a uma raiz quadrada.
O ganho de velocidade é da ordem da raiz quadrada; por isso seu sentido prático depende do tamanho do problema e do custo das operações quânticas. O resumo do artigo fala apenas do número de passos; não dá projeto de dispositivo.
A diferença deste artigo em relação ao algoritmo de Shor é que a aceleração não se apoia em uma estrutura matemática especial (a periodicidade), mas, em compensação, é de apenas uma raiz quadrada. Lidos em conjunto, os dois mostram que a resposta à pergunta de quanto ganho um computador quântico pode proporcionar, e em quais problemas, muda conforme o problema. O sentido da aceleração por raiz quadrada também pode ser lido assim: em uma lista de um milhão de itens, a busca clássica leva algo como meio milhão de passos, enquanto a busca quântica leva algo como mil passos; este é um exemplo que mostra ordens de grandeza, e não um número do artigo.
Depois: O algoritmo tornou-se um bloco de construção amplamente usado em trabalhos posteriores, como ferramenta para problemas gerais de busca e contagem.
19. BQP: A Classe de Complexidade Quântica
Pergunta principal: Exatamente quão poderosos são os computadores quânticos?
A teoria da complexidade classifica os problemas em classes segundo o recurso necessário para resolvê-los. BQP é a classe dos problemas que um computador quântico consegue resolver de modo eficiente (em tempo polinomial) com uma pequena margem de erro. Bernstein e Vazirani definiram essa classe e examinaram sua relação com as classes clássicas.
Proc. 25th Annual ACM Symposium on Theory of Computing (STOC '93), 11–20; tam sürüm: SIAM J. Comput. 26 (1997) 1411–1473 teoria
Artigo que fundou a teoria da complexidade das máquinas de Turing quânticas e relacionou a classe BQP às classes clássicas.
O artigo examina a computação quântica do ponto de vista da teoria da complexidade. O primeiro resultado é que, no modelo de máquina de Turing quântica de Deutsch, existe uma máquina de Turing quântica universal eficiente. Os autores observam que essa construção é muito mais complicada que a contraparte clássica; mostram que até princípios simples como laço, ramificação e composição são trabalhosos no contexto quântico.
O segundo resultado diz respeito à precisão. Com que exatidão precisam ser especificadas as amplitudes de transição? Mostra-se que, para um cálculo de T passos, bastam O(log T) bits de precisão; assim, sustenta-se que a máquina de Turing quântica pode ser considerada um modelo de computação discreto, e não analógico.
O terceiro resultado é a separação em relação ao modelo clássico. Supondo um oráculo, encontra-se um problema que a máquina de Turing quântica resolve em tempo polinomial, mas que a máquina de Turing clássica probabilística com erro limitado (BPP) não resolve em tempo polinomial. Isso é apresentado como a primeira prova formal, no sentido da teoria moderna da complexidade, de que o modelo quântico vai além da tese de Church-Turing; trata-se de uma separação relativa a um oráculo, e não sem oráculo.
Por fim, define-se a BQP e mostra-se a relação BPP ⊆ BQP ⊆ P^#P. O que isso significa é que mostrar matematicamente, sem oráculo, que as máquinas de Turing quânticas são mais poderosas que as máquinas probabilísticas clássicas não é possível sem um grande avanço na teoria da complexidade.
O sentido prático desses resultados é este: se a BQP está estritamente separada das classes clássicas conhecidas continua sendo uma questão em aberto depois deste artigo também. Os autores afirmam explicitamente que uma prova disso que não exigisse oráculo significaria um grande avanço na teoria. Nota para o leitor: BPP é a classe dos problemas que um computador clássico resolve em tempo polinomial com aleatoriedade e uma pequena margem de erro; P^#P é uma classe clássica muito poderosa, muito além dos métodos eficientes conhecidos, de modo que o limite superior da BQP é bastante frouxo.
Depois: O texto completo foi publicado em 1997 no SIAM Journal on Computing. O resumo lido é o resumo da versão da SIAM; o texto do artigo de 1993 não foi examinado separadamente.
20. Supremacia Quântica (Quantum Supremacy)
Pergunta principal: Algo que os computadores clássicos não conseguem fazer foi realmente feito?
Supremacia quântica é um dispositivo quântico resolver uma determinada tarefa tão rapidamente que ela não pode ser feita em tempo razoável pelo melhor método clássico conhecido. A tarefa não precisa ser útil. O artigo da Google na Nature, de 2019, é a primeira alegação experimental disso; no mesmo ano, pesquisadores da IBM argumentaram que a simulação clássica poderia levar muito menos tempo do que o alegado.
Artigo da Google que alega supremacia quântica por amostragem de circuito aleatório no processador supercondutor Sycamore, de 53 qubits.
O artigo é apresentado como um teste experimental da promessa de que os computadores quânticos podem realizar certas tarefas exponencialmente mais rápido que os computadores clássicos. A dificuldade é construir um processador que funcione com alta fidelidade e possa executar algoritmos quânticos em um espaço de cálculo muito grande.
Os autores usam um processador formado por qubits supercondutores programáveis e produzem estados quânticos em 53 qubits; a dimensão do espaço de cálculo correspondente é 2^53, ou seja, cerca de 10^16. A tarefa é executar um circuito quântico escolhido ao acaso e amostrar os resultados das medições. O processador Sycamore gasta cerca de 200 segundos para amostrar uma instância de circuito um milhão de vezes. Os autores estimam, segundo seus próprios testes comparativos, que a mesma tarefa levaria cerca de 10.000 anos no supercomputador clássico mais avançado. A distribuição de probabilidade resultante é verificada com simulações clássicas.
Os autores descrevem esse resultado como um aumento dramático de velocidade em relação a todos os algoritmos clássicos conhecidos e como a realização experimental da supremacia quântica para essa tarefa de cálculo específica. Dois pontos merecem atenção. O primeiro é que a tarefa não visa uma aplicação útil; amostrar a saída do circuito quântico é um critério em que a velocidade é medida. O segundo é que o número de 10.000 anos é uma estimativa e pode mudar com a descoberta de melhores algoritmos no lado clássico; de fato, isso se tornou depois objeto de debate.
A expressão que define o alcance da alegação do artigo é "para essa tarefa de cálculo específica". Os autores relatam não que um problema útil foi resolvido, mas que se observou uma diferença de velocidade em uma tarefa específica de amostragem. O artigo trata também do problema da verificação: como calcular o resultado de modo clássico nessa escala é quase impossível, a correção é testada em circuitos menores e em versões simplificadas; este resumo não entra nesse detalhe.
Depois: No mesmo ano, Pednault e colegas argumentaram, com uma simulação que usa armazenamento secundário, que esses circuitos poderiam ser simulados em um supercomputador em questão de dias.
Resposta que argumenta que os circuitos Sycamore poderiam ser simulados em dias em um supercomputador clássico usando armazenamento secundário.
Um trabalho anterior dos autores havia mostrado que o armazenamento secundário (os discos) pode ampliar a faixa de circuitos quânticos que podem ser executados na prática em simulação clássica. Este artigo aprimora essas técnicas e as aplica a circuitos Sycamore de 53 e 54 qubits. O artigo saiu como pré-publicação pouco antes da publicação do artigo da Google na Nature.
O padrão de circuito de interesse (o padrão de emaranhamento chamado ABCDCDAB) é do tipo que se mostrou difícil de simular classicamente por outras abordagens. Segundo a análise dos autores, no supercomputador Summit, do Laboratório Nacional de Oak Ridge, esses circuitos podem ser simulados em alguns dias, até profundidade arbitrária, com alta fidelidade e com todas as amplitudes fornecidas como saída.
Isto não é um experimento, mas uma análise de cálculo. A estimativa de "alguns dias" do artigo é uma contraestimativa colocada diante da estimativa de "cerca de 10.000 anos" do artigo da Google. Como as duas estimativas se baseiam no custo da mesma tarefa com algoritmos clássicos diferentes, o debate não é sobre um resultado experimental, mas sobre qual método clássico é o melhor para essa tarefa e com que fidelidade ela precisa ser calculada.
Este trabalho contrário é citado como exemplo que mostra que as alegações de "supremacia quântica" são um limiar que pode ser deslocado pelo progresso dos algoritmos clássicos. Nota para o leitor: a profundidade do circuito é o número de camadas sucessivas de portas do circuito quântico; à medida que a profundidade aumenta, a simulação clássica geralmente fica mais difícil.
Depois: O debate prosseguiu nos anos seguintes com o desenvolvimento de técnicas de simulação clássica; seus detalhes não estão neste arquivo.