Lista de algoritmos de inspiração quântica

11

Os avanços na computação quântica levaram ao desenvolvimento de novos algoritmos clássicos. Exemplos recentes notáveis ​​são algoritmos de inspiração quântica para álgebra linear:

e para Max 3LIN:

Pode ser muito útil compilar uma lista de todos os algoritmos clássicos conhecidos inspirados na computação quântica. Que outros exemplos são conhecidos?

quantum-computing randomized-algorithms Juan Miguel Arrazola
fonte

Respostas:

5

Como reivindicado por Leslie G. Valiant em um artigo seminal 1 dele,

Os algoritmos holográficos são inspirados no modelo computacional quântico. No entanto, eles são executáveis ​​em computadores clássicos e não precisam de computadores quânticos.

Essa é uma técnica de design algorítmico que foi usada (pelo próprio Valiant e outros) para produzir algoritmos de tempo polinomial para vários problemas que são pequenas variações de problemas importantes de NP (mais sobre isso na wikipedia 2 ).

Alessandro Cosentino
fonte
8

Há também um trabalho recente sobre programação semidefinida de baixo escalão que, embora não seja baseada diretamente em um algoritmo quântico, ainda usa as mesmas técnicas de inspiração quântica.

Ewin
fonte
3

Há todo um trabalho a ser feito com algoritmos evolutivos de inspiração quântica (QIEA), com algoritmos reais que usam técnicas de computação quântica, veja pesquisa (fonte ACM) . Outro algoritmo quântico inspirado o utiliza na otimização numérica .

user3483902
fonte
3

O (s) algoritmo (s) de recozimento quântico Monte Carlo quântico (QMC-QA 1 ) ou de recozimento quântico simulado em tempo discreto (SQA 2 ) teve desempenho melhor que o dispositivo D-Wave testado em estudos recentes :

Estabelecemos o primeiro exemplo de uma vantagem de dimensionamento para um recozimento quântico experimental em relação ao recozimento simulado clássico: descobrimos que o dispositivo D-Wave exibe um incrivelmente melhor dimensionamento do que o recozimento simulado, com 95% de confiança, no intervalo de tamanhos de problemas que podemos testar . No entanto, não encontramos evidências de uma aceleração quântica: o recozimento quântico simulado exibe o melhor dimensionamento por uma margem significativa.

Como o dispositivo D-Wave e o SQA superam o SA em determinadas instâncias de problemas, isso dá a impressão de que o SQA é uma espécie de algoritmo de inspiração quântica. O estudo mais recente que testou o processador D-Wave 2000Q também descobriu que seu desempenho se correlaciona melhor com um modelo clássico proposto chamado "algoritmo de Monte Carlo de vetor de spin (SVMC)" naquele estudo do que com o SQA:

Usamos isso para argumentar que uma das principais razões para a desaceleração do recozimento quântico em relação ao SQA é a temperatura subótimamente alta, o que faz com que ele se comporte mais como o SVMC. Portanto, o forte desempenho do SQA na classe de instância plantada lógica sugere que essa classe é um bom alvo ou base para a exploração de uma eventual aceleração quântica usando hardware de controle de qualidade.

Se ignorarmos a história de fundo da D-Wave, ainda podemos concluir que o SQA é um algoritmo de otimização de inspiração quântica que supera o recozimento simulado clássico (e talvez outros algoritmos de otimização) para certos problemas? Depende. Se o objetivo é realmente encontrar o estado fundamental de algum sistema quântico, então a resposta é sim. Mas se o objetivo é ter um algoritmo de otimização de uso geral semelhante ao recozimento simulado, a resposta é não.

  1. Martoňák, R., Santoro, GE & Tosatti, E. Recozimento quântico pelo método de Monte Carlo com integral de caminho: O modelo aleatório bidimensional de Ising. Phys. Rev. B 66 , 094203 (2002). URL http://link.aps.org/doi/10.1103/PhysRevB.66.094203
  2. Santoro, GE, Martokák, R., Tosatti, E. & Car, R. Teoria do recozimento quântico de um vidro de spin Ising. Science 295 , 2427-2430 (2002). URL http://dx.doi.org/10.1126/science.1068774 .
Thomas Klimpel
fonte