O Google está correndo para desenvolver processadores aprimorados quânticos que usam efeitos da mecânica quântica para aumentar a velocidade com que os dados podem ser processados. No curto prazo, O Google desenvolveu novos algoritmos aprimorados quânticos que operam na presença de ruído realista. O chamado algoritmo de otimização aproximada quântica, ou QAOA para breve, é a pedra angular de um movimento moderno em direção ao desenvolvimento de algoritmo com tolerância a ruído aprimorado por quantum.

A célebre abordagem adotada pelo Google em QAOA despertou um vasto interesse comercial e acendeu uma comunidade de pesquisa global para explorar novas aplicações. Ainda, pouco se sabe sobre as limitações de desempenho do algoritmo QAOA do Google.

Uma equipe de cientistas do Deep Quantum Laboratory da Skoltech aceitou esse desafio contemporâneo. A equipe totalmente Skoltech liderada pelo Prof. Jacob Biamonte descobriu e quantificou o que parece ser uma limitação fundamental na abordagem amplamente adotada iniciada pelo Google.

Reportando Cartas de revisão física , os autores detalham a descoberta dos chamados déficits de alcançabilidade - os autores mostram que esses déficits colocam uma limitação fundamental na capacidade do QAOA de até aproximar uma solução para um problema, instância.

As descobertas da equipe Skoltech relatam uma limitação clara do algoritmo quântico QAOA variacional. QAOA e outros algoritmos quânticos variacionais têm se mostrado extremamente difíceis de analisar usando técnicas matemáticas conhecidas devido a um processo interno de feedback quântico para clássico. Nomeadamente, uma determinada computação quântica só pode ser executada por um período fixo de tempo. Dentro deste tempo fixo, um número fixo de operações quânticas pode ser executado. O QAOA busca utilizar essas operações quânticas de forma iterativa, formando uma sequência de aproximações cada vez mais otimizadas para minimizar uma função objetivo. O estudo impõe novos limites a esse processo.

Os autores descobriram que a capacidade do QAOA de aproximar soluções ótimas para qualquer circuito quântico de profundidade fixa é fundamentalmente dependente da "densidade" do problema. No caso do problema denominado MAX-SAT, a chamada densidade pode ser definida como a razão entre as restrições do problema e a contagem de variáveis. Isso às vezes é chamado de densidade de cláusula.

Os autores descobriram instâncias problemáticas de alta densidade com soluções ótimas que não podem ser aproximadas com sucesso garantido, independentemente do tempo de execução do algoritmo.