Que tipo de algoritmos são mais rápidos com um computador quântico?

11

Eu sou um estudante iniciante em CS e estou aprendendo algoritmos. Ouvi dizer que, mesmo com computadores quânticos, esses algoritmos de classificação geral nunca podem ter tempo melhor que . No entanto, eu também sei que algoritmos de fatoração seriam muito mais rápidos. Em termos gerais, que tipo de algoritmos se tornaria substancialmente mais rápido com computadores quânticos?nregistron

hgund
fonte
1
Eu sugiro que você reformule sua pergunta. Você está realmente perguntando quais problemas podem ser resolvidos mais rapidamente com computadores quânticos.
Yuval Filmus
1
Scott Aaronson (o guru da computação quântica) (exatamente duas versões de a) falou sobre esse assunto, intitulado * Quando exatamente os computadores quânticos fornecem uma aceleração? ". Você pode encontrá-lo (ou melhor, eles) aqui: scottaaronson.com/ fala .
Yuval Filmus
Tanto quanto eu sei, nenhum . Precisamos de novos algoritmos. (cf. o primeiro comentário de Yuval.)
Raphael
ele não é realmente provado que factoring é mais rápido, a apenas conjecturou, etc., sua uma questão em aberto P = BQP etc?
vzn

Respostas:

12
  • kumak=bumab
  • O algoritmo de Grover fornece uma aceleração quadrática na pesquisa de listas não classificadas (que podem ser usadas como uma aceleração para muitos algoritmos).
  • A simulação de sistemas quânticos também está no BQP, mas exponencialmente mais lenta em uma MT clássica.
  • Resolver a equação de Pell (não realmente uma equação) está no BQP, outra aceleração exponencial.
  • Há também vários outros problemas mais obscuros que estão no BQP, mas parecem não estar em P. Wocjan e Zhang, são um bom ponto de partida para desenterrá-los.
Luke Mathieson
fonte