Cientistas da NTT dizem ter uma nova maneira de verificar a vantagem quântica

Sunnyvale, Califórnia – 26 de outubro de 2022 – A NTT Research anunciou que um cientista de seu Laboratório de Criptografia e Segurança da Informação (CIS) e um colega do Laboratórios de Informática Social da NTT (SIL) escreveram um artigo pioneiro sobre vantagem quântica. O artigo foi selecionado para ser apresentado no Simpósio anual do IEEE sobre Fundamentos da Ciência da Computação (FOCS), que acontecerá de 31 de outubro a 3 de novembro. XNUMX em Denver.

Os coautores do artigo, intitulado “Vantagem Quântica Verificável sem Estrutura,” são o Dr. Takashi Yamakawa, distinto pesquisador da NTT SIL e o Dr. Mark Zhandry, cientista sênior da Pesquisa NTT Laboratório CEI. O trabalho foi feito em parte na Universidade de Princeton, onde o Dr. Yamakawa foi pesquisador visitante e o Dr. Zhandry também atua como professor assistente de ciência da computação. 

O tópico da vantagem quântica (ou aceleração quântica) está relacionado aos tipos de problemas que os computadores quânticos podem resolver mais rapidamente que os computadores clássicos ou não quânticos e o quanto eles são mais rápidos. Os problemas em questão são comumente descritos como classe não-determinística de tempo polinomial (NP). Quanta vantagem pode variar em grande medida. Um computador quântico pode ser capaz de resolver um problema específico em um minuto ou um segundo que um computador clássico leva uma semana, ou possivelmente uma quantidade de tempo incompreensivelmente exponencial. Neste artigo, os autores abordam o desafio de verificar essa superioridade e fazê-lo de forma eficiente. Até o momento, as demonstrações de vantagem quântica envolveram uma “estrutura” significativa ou comunicação de ida e volta entre duas ou mais partes. O avanço do artigo de Yamakawa e Zhandry é demonstrar um problema NP difícil onde a verificação é possível sem estrutura.

“Esta é a primeira vez que vimos uma aceleração quântica exponencial para um problema de busca NP, que requer apenas um oráculo aleatório”, disse o professor de ciência da computação da Universidade do Texas em Austin, Dr. Scott Aaronson, que comentou uma versão inicial do artigo durante um workshop em 13 de junho de 2022, no Simons Institute for the Theory of Computing. Ao exigir apenas um oráculo aleatório, ou seja, uma caixa preta teórica que gera respostas aleatórias para cada consulta, Yamakawa e Zhandry construíram seu problema com base em suposições computacionais não estruturadas. Como tal, seu problema se alinha mais com funções unidirecionais em vez de funções estruturadas, como as encontradas na criptografia de chave pública. Esse alinhamento unidirecional facilita a verificação eficiente.

“É emocionante ver criptógrafos afiliados à NTT colaborando em pesquisas que mais uma vez merecem o rótulo de ‘descoberta’, especialmente em um artigo que enriquece nossa compreensão da computação quântica, outra área de foco para nós da NTT Research”, disse Kazuhiro Gomi , Presidente e CEO da NTT Research. “Parabéns e votos de felicidades a todos os participantes desta prestigiosa conferência IEEE.” 

O problema de busca NP que Yamakawa e Zhandry criaram era um problema dois em um que implica encontrar 1) uma string de n símbolos que é uma palavra de código de um determinado código de correção de erros e 2) uma string de n símbolos onde cada símbolo é mapeado para zero sob o oráculo aleatório. Cada problema separadamente é fácil. Mas encontrar uma única sequência de símbolos que seja uma palavra de código e mapeie para zero é muito mais difícil, pelo menos classicamente. “Se você é quântico, pode resolver isso em tempo polinomial”, disse Zhandry, “mas se você é clássico, pelo menos se estiver nesse modelo de caixa preta, precisa de tempo exponencial”. Por outro lado, dada uma solução potencial, é simples verificá-la verificando se ela resolve separadamente cada um dos dois problemas. Observe que, como convém a um artigo para FOCS, este trabalho é básico ou fundamental. Conforme apontado na palestra do Dr. Aaronson no Simons Institute (discutido neste NTT Research artigo de blog), o argumento Yamakawa-Zhandry se enquadra em uma classe de acelerações que podem ser facilmente verificadas matematicamente, mas não demonstradas na prática por um computador quântico real em breve. Além de seu esquema de verificação inovador, no entanto, o artigo também aponta para algo novo em relação à extensão da aceleração quântica.

“Antes de nosso trabalho, tínhamos exemplos de vantagem quântica para problemas NP, como fatoração ou, na configuração da caixa preta, descoberta de período. Mas acontece que o algoritmo quântico subjacente a todos esses exemplos era basicamente a descoberta do período – embora mostrar como aplicar a descoberta do período a esses exemplos muitas vezes não fosse trivial”, disse o Dr. Zhandry. “Nosso artigo mostra que há pelo menos um segundo caso. Você poderia interpretar isso com otimismo como dizendo que há esperança de que a vantagem quântica seja mais difundida do que talvez pensássemos anteriormente.”

Patrocinado pelo IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), o FOCS é uma conferência líder no campo da ciência da computação teórica. A chamada de artigos para o FOCS 2022, o 63º encontro anual, listou a computação quântica como uma das 17 áreas gerais de interesse. O artigo de Yamakawa-Zhandry está programado para ser apresentado em 31 de outubro de 2022, às 10h15 MT. Para saber mais e se inscrever neste evento, acesse o site FOCS 2022 .