Existem exemplos de casos em que a simulação clássica de um algoritmo quântico para um problema supera o melhor algoritmo clássico conhecido anteriormente para esse problema? "Supera desempenho" não precisa significar classe de complexidade diferente; poderia simplesmente ser melhor dimensionado.
Esta questão foi inspirada no caso de simulação clássica eficiente de um algoritmo de recomendação quântica .
Respostas:
Sua pergunta foi inspirada no recente avanço clássico de inspiração quântica no algoritmo de recomendação. Note que não é a primeira vez que isso acontece. Em 2015, desenvolvimentos semelhantes ocorreram com o MAX3LIN aproximado : um algoritmo de quanutro que superava todos os algoritmos clássicos conhecidos anteriores motivou uma busca bem-sucedida por um algoritmo clássico melhor. No entanto, tanto quanto eu sei, em ambos os casos, os algoritmos clássicos não se parecem com a simulação clássica de uma evolução quântica.
Conheço um artigo que descreve uma simulação clássica de um sistema quântico que permite superar algoritmos previamente conhecidos (divulgação completa: os autores são meus amigos) :
Isso se baseia na conexão entre as ópticas permanente e quântica, mostrada pela amostragem do bóson . Em oposição à abordagem usual, eles analisam estados que são conhecidos por serem fáceis de simular (estados térmicos) e usam essa simulação para realizar um cálculo em Monte-Carlo da permanente das matrizes semidefinidas positivas hermitianas. Para algumas classes de matrizes, esse algoritmo fornece uma aproximação melhor do que o melhor algoritmo conhecido anteriormente (algoritmo de Gurvits).
fonte