Aplicações do mundo real da computação quântica (exceto segurança)

17

Vamos supor que construímos um computador quântico universal.

Exceto por questões relacionadas à segurança (criptografia, privacidade, ...) quais problemas atuais do mundo real podem se beneficiar com o uso?

Estou interessado em ambos:

  • problemas atualmente insolúveis para uma entrada prática,
  • problemas que estão sendo resolvidos no momento, mas uma aceleração significativa melhoraria bastante sua usabilidade.
Piotr Migdal
fonte
8
Talvez isso ajude.
aelguindy
No IIRC, houve uma pergunta sobre quais computadores quânticos podem ser usados ​​para calcular com eficiência. Você pode querer dar uma olhada.
Kaveh
É este útil?
Kaveh
11
@ Kevah: Não muito, para ser honesto. A ênfase da minha pergunta são as aplicações do mundo real (não apenas onde 'há uma aceleração para um algoritmo específico', mas quando uma aceleração resolve um problema prático específico).
Piotr Migdal
11
Construção de árvore filogenética ideal .
Saeed

Respostas:

17

Simulação eficiente da mecânica quântica.

Tyson Williams
fonte
esta é a resposta std / folklore / ironic / glib / near-gracejo e eu me pergunto quem a originou. alguém tem uma referência real? Eu o questiono como não sendo trivialmente possível da seguinte maneira. A computação em qm é amplamente focada nas interações de pares qubit (portões). para provar que é possível simular com eficiência o QM em geral, parece que é preciso mostrar que é possível simular todas as possíveis interações n-wise de maneira eficiente com interações pareadas. não vi isso comprovado em um artigo.
vzn
2
@vzn: na maioria das interações físicas, restringir as interações com 2 partículas é uma boa aproximação, suficiente para simulações baseadas apenas nas interações locais com 2 corpos para fazer sentido (interações que incluem mais termos geralmente decaem muito rapidamente). Portanto, a existência de interações gerais n-corpo não invalida a idéia de simulação.
Marcin Kotowski
@ vzn Não tenho uma referência em papel, mas Scott Aaronson diz isso e mencionou em seu recente artigo do Times .
Tyson Williams
2
@vzn, essa era a aplicação original em mente quando Richard Queynman foi concebido pela computação quântica. Este é o link para o artigo em que ele propôs a idéia de computadores quânticos ( springerlink.com/content/t2x8115127841630 ), e você também pode verificar isso ( sabedoria.weizmann.ac.il/~naor/COURSE/feynman-simulating.pdf )
Marcos Villagra
11
@vzn A resposta é válida, mas a literatura sobre simulação quântica digital é bastante abrangente para resumir apenas através de comentários. Eu recomendaria abrir uma nova discussão, já que o tópico é interessante.
Juan Bermejo Vega
8

Brassard, Hoyer, Mosca e Tapp mostraram que a busca generalizada de Grover, chamada amplificação de amplitude, pode ser usada para obter uma aceleração quadrática em uma grande classe de heurísticas clássicas. A intuição por trás da ideia deles é que as heurísticas clássicas usam a aleatoriedade para procurar uma solução para um determinado problema, para que possamos usar a amplificação de amplitude para pesquisar o conjunto de seqüências aleatórias por uma que faça a heurística encontrar uma boa solução. Isso gera uma aceleração quadrática no tempo de execução do algoritmo. Veja a seção 3 do artigo acima, para mais detalhes.

Philippe Lamontagne
fonte
8

Simulando sistemas quânticos!

Percebi que na outra resposta que mencionou isso, houve vários comentários sobre se isso era verdade, pois é uma afirmação não óbvia. E as pessoas solicitaram referências. Aqui estão algumas referências.

Proposta original de Feynman:

Feynman, R .: Simulando física com computadores. Int. J. Theor. Phys. 21 (6) (1982) 467-488

Algoritmos eficientes para todos os sistemas quânticos definidos por hamiltonianos "locais". (Lloyd também explica que qualquer sistema consistente com a relatividade geral e especial evolui de acordo com as interações locais.)

Lloyd, S .: Simuladores quânticos universais. Science 273 (5278) (1996) 1073-1078

Generalização adicional para Hamiltonianos esparsos, que são mais gerais que Hamiltonianos locais:

Aharonov, D., Ta-Shma, A .: Geração de estado quântico adiabático e conhecimento estatístico zero. In: Proc. 35ª STOC, ACM (2003) 20–29

Leitura adicional:

Berry, D., Ahokas, G., Cleve, R., Sanders, B .: algoritmos quânticos eficientes para simular Hamiltonianos esparsos. Comum. Matemática. Phys. 270 (2) (2007) 359–371

Childs, AM: processamento quântico de informações em tempo contínuo. Tese de doutorado, Instituto de Tecnologia de Massachusetts (2004)

Robin Kothari
fonte
2

A visão é perigosa e polêmica nesse campo, por isso devemos ser cautelosos com esse tópico. No entanto, alguns algoritmos Q com acelerações polinomiais têm aplicações potenciais interessantes.

Sabe-se que a pesquisa Grover pode ser usada para buscar polinomialmente a solução para problemas de NP-completos [1] . Isso é comprovado para o 3-SAT em [2] . Algumas aplicações do SAT, emprestadas de [3] , são: verificação da equivalência de circuitos , geração automática de padrões de teste , verificação de modelos usando a Linear Time Logic , planejamento em inteligência artificial e haplotipagem em bioinformática . Embora eu não saiba muito sobre esses tópicos, essa linha de pesquisa parece bastante prática para mim.

Além disso, existe um algoritmo quântico para avaliar árvores NAND com uma aceleração polinomial em relação à computação clássica [ 8 , 10 , 11 ]. A árvore NAND é um exemplo de uma árvore de jogo, uma estrutura de dados mais geral usada para estudar partidas de jogos de tabuleiro como Chess e Go. Parece plausível que esse tipo de aceleração possa ser usado para projetar jogadores de software mais poderosos. Isso poderia interessar a alguns desenvolvedores de jogos quânticos?

Infelizmente, jogar na realidade não é exatamente o mesmo que avaliar árvores: há complicações, por exemplo, se seus jogadores não estiverem usando estratégias ótimas [ 12 ]. Não vi nenhum estudo considerando um cenário da vida real, por isso é difícil dizer o quão benéfico é o aumento de velocidade na prática [ 8 ]. Este poderia ser um bom tópico para discussão.

Juan Bermejo Vega
fonte
11
Aceite meu convite para participar: quantumcomputing.stackexchange.com .
Rob
-6

acho que você levantou uma excelente pergunta nas fronteiras da pesquisa de QM (parcialmente indicada por sua falta de respostas até agora), mas ela não foi totalmente formalmente definida ou capturada como um problema. a questão está na linha de "o que exatamente os algoritmos QM podem computar com eficiência de qualquer maneira?" e uma resposta completa não é conhecida e está sendo ativamente buscada. parte disso está relacionada à (questões em aberto) complexidade das classes relacionadas ao QM.

esse seria o caso em que há uma pergunta um tanto formal definida. se for possível demonstrar que as classes QM são equivalentes a classes não-QM "significativamente poderosas", então a resposta é sua. o tema geral desse tipo de resultado seria uma classe "não tão difícil de QM" é equivalente a uma classe "difícil de não-QM". existem várias separações de classes de complexidade aberta desse tipo (talvez alguém possa sugeri-las com mais detalhes).

algo estranho no conhecimento atual de QM sobre algoritmos quânticos é que há um tipo de algoritmo estranho conhecido por funcionar em QM, mas aparentemente não há muita coerência / coesão para eles. eles parecem estranhos e desconectados em alguns aspectos. não existe uma "regra de ouro" aparente para "problemas que são computáveis ​​no QM geralmente estão nessa forma", apesar de uma expectativa razoável de que alguém possa estar lá.

por exemplo, compare isso com a teoria da completude da PN, que é muito mais coesa em comparação. parece que, se a teoria da QM for melhor desenvolvida, ela obteria esse maior senso de coesão que lembra a teoria da completude da PN.

uma idéia mais forte pode ser que, eventualmente, quando a teoria da complexidade de QM for aprimorada, a integridade do NP se encaixará "perfeitamente" nela de alguma forma.

para mim, a aceleração QM mais geral ou a estratégia amplamente aplicável que eu já vi parece ser o algoritmo de Grovers, porque muitos softwares práticos estão relacionados a consultas de banco de dados. e, de certa forma, cada vez mais "não estruturado":

O(N)Ω(N)

vzn
fonte
3
"A teoria da complexidade QM é aprimorada, a completude do NP se encaixará" perfeitamente "nela de alguma forma". Existe uma teoria bem desenvolvida de sistemas de prova interativa quântica (classes de complexidade como QMA etc.) que generalizam classes de complexidade clássica como NP, PSPACE etc. Nesse sentido, a completude da NP se encaixa perfeitamente na teoria da complexidade quântica. (por outro lado, concordo que o campo dos algoritmos quânticos carece de coesão, mas algoritmos quânticos e complexidade quântica são subcampos diferentes).
Marcin Kotowski
concordamos que existem classes e hierarquias de QM bem definidas que espelham classes que não são de QM, mas sua relação com (poder em relação a) classes de QM não clássicas e NP em particular é em grande parte uma questão em aberto, como afirmado.
vzn
11
O que você quer dizer com "bancos de dados cada vez mais desestruturados"? Um banco de dados parece algo bastante ordenado por definição.
Juan Bermejo Vega