(Desculpe por uma pergunta um pouco amadora)
Estudei computação quântica de 2004 a 2007, mas perdi a noção do campo desde então. Naquela época, havia muito hype e conversas sobre QC potencialmente resolvendo todos os tipos de problemas, superando os computadores clássicos, mas, na prática, havia realmente apenas duas descobertas teóricas:
- O algoritmo de Shor, que mostrou uma velocidade significativa, mas que tinha aplicabilidade limitada e não era realmente útil fora da fatoração de número inteiro.
- O algoritmo de Grover, aplicável a uma categoria mais ampla de problemas (uma vez que poderia ser usado para resolver problemas do NP-Complete), mas que apenas mostrou aceleração polinomial em comparação com os computadores clássicos.
O recozimento quântico também foi discutido, mas não ficou claro se era realmente melhor do que o recozimento simulado clássico ou não. O controle de qualidade baseado na medição e a representação do estado gráfico do controle de qualidade também foram tópicos importantes, mas nada definitivo também foi provado nessa frente.
Houve algum progresso no campo dos algoritmos quânticos desde então? Em particular:
- Houve algum algoritmo verdadeiramente inovador além dos de Grover e Shor?
- Houve algum progresso na definição do relacionamento do BQP com P, BPP e NP?
- Fizemos algum progresso na compreensão da natureza da velocidade quântica, além de dizer que "deve ser por causa do emaranhado"?
speedup
grovers-algorithm
shors-algorithm
Alex Kinman
fonte
fonte
Respostas:
Depende do que você quer dizer com "verdadeiramente inovador". Grover e Shor são particularmente únicos porque foram realmente as primeiras instâncias que mostraram tipos particularmente valiosos de velocidade com um computador quântico (por exemplo, a suposta melhoria exponencial para Shor) e eles tinham aplicativos matadores para comunidades específicas.
Existem alguns algoritmos quânticos que foram projetados desde então, e acho que três são particularmente dignos de menção:
O algoritmo BQP-completo para avaliar o polinômio de Jones em pontos específicos. Menciono isso porque, além de coisas mais óbvias, como a simulação Hamiltoniana, acredito que foi o primeiro algoritmo completo do BQP, por isso mostra realmente a potência total de um computador quântico.
O algoritmo HHL para resolver equações lineares. Este é um pouco engraçado, porque é mais como uma sub-rotina quântica, com entradas e saídas quânticas. No entanto, ele também é completo em BQP e está recebendo muita atenção no momento, devido a possíveis aplicações em aprendizado de máquina e similares. Eu acho que este é o melhor candidato para inovar verdadeiramente, mas isso é uma questão de opinião.
Química Quântica . Sei muito pouco sobre isso, mas os algoritmos se desenvolveram substancialmente desde o momento em que você mencionou e sempre foram citados como uma das aplicações úteis de um computador quântico.
Essencialmente, não. Sabemos que o BQP contém BPP e não sabemos a relação entre BQP e NP.
Mesmo quando você estava estudando originalmente, eu diria que era mais precisamente definido do que isso. Existem (e houve) boas comparações entre conjuntos de portas universais (potencialmente capazes de fornecer aceleração exponencial) e conjuntos de portas classicamente simuláveis. Por exemplo, lembre-se de que os portões de Clifford produzem emaranhamento, mas são classicamente simuláveis. Não é fácil afirmar com precisão o que é necessário de uma maneira mais pedagógica.
Talvez onde algum progresso tenha sido feito seja em termos de outros modelos de computação. Por exemplo, o modelo DQC1 é melhor compreendido - este é um modelo que parece ter uma certa aceleração em relação aos algoritmos clássicos, mas é improvável que seja capaz de cálculos completos de BQP (mas antes de você se interessar pelo hype que você pode encontrar online , não é emaranhamento presente durante a computação).
Por outro lado, o tipo de afirmação "é por causa do emaranhado" ainda não está totalmente resolvido. Sim, para computação quântica em estado puro, deve haver algum emaranhado, porque caso contrário o sistema é fácil de simular, mas para estados separáveis mistos, não sabemos se eles podem ser usados para cálculos ou se podem ser eficientemente simulados.
Além disso, pode-se tentar fazer uma pergunta mais esclarecedora: fizemos algum progresso no entendimento de quais problemas serão passíveis de aceleração quântica? Isso é sutilmente diferente, porque se você acha que um computador quântico oferece novas portas lógicas que um computador clássico não tem, é óbvio que, para acelerar, você deve usá-las. No entanto, não está claro que todos os problemas sejam passíveis de tais benefícios. Quais são? Existem classes de problemas em que se pode esperar acelerar, mas acho que isso ainda depende da intuição individual. Provavelmente ainda pode ser dito sobre algoritmos clássicos. Você escreveu um algoritmo x. Existe uma versão clássica melhor? Talvez não, ou talvez você não esteja percebendo. É por isso que não sabemos se P = NP.
fonte
O algoritmo Kerenidis-Prakash foi inovador, até que Ewin Tang consertou o terreno de volta:
Revista Quanta: Grande avanço na computação quântica tornado obsoleto pelo adolescente .
fonte