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

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? $n\log n$

algorithms quantum-computing hgund
fonte

Eu sugiro que você reformule sua pergunta. Você está realmente perguntando quais problemas podem ser resolvidos mais rapidamente com computadores quânticos.

Yuval Filmus

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

Intimamente relacionado: por que e como um computador quântico é mais rápido que um computador comum?

Gilles 'SO- stop be evil'

Respostas:

$k$ $a^{k} = b$ $a$ $b$
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