Problemas intermediários NP com soluções quânticas eficientes

27

Peter Shor mostrou que dois dos mais importantes problemas intermediários de NP, fatoração e o problema de log discreto, estão no BQP. Por outro lado, o algoritmo quântico mais conhecido para SAT (busca de Grover) produz apenas uma melhoria quadrática em relação ao algoritmo clássico, sugerindo que problemas de NP-completos ainda são intratáveis ​​em computadores quânticos. Como Arora e Barak apontam, também há um problema no BQP que não é conhecido por NP, levando à conjectura de que as duas classes são incomparáveis.

Existe algum conhecimento / conjectura sobre por que esses problemas intermediários de NP estão no BQP, mas por que o SAT (até onde sabemos) não está? Outros problemas intermediários de NP seguem essa tendência? Em particular, o isomorfismo de grafos no BQP? (este não faz uma boa busca no Google).

Huck Bennett
fonte
4
Suponho que devo abordar a questão de por que certos problemas intermediários de NP estão no BQP e outros não são conhecidos. A única coisa que posso dizer com confiança é que os problemas conhecidos no BQP se enquadram em várias classes e, dentro de cada classe, geralmente as mesmas técnicas são usadas na solução. Veja os dois links no meu comentário anterior
Peter Shor
1
Qualquer problema completo do BQP serve como um exemplo de um problema no BQP que não é conhecido por estar no NP.
Robin Kothari
2
Em relação a um algoritmo de isomorfismo de gráfico quântico: tuvalu.santafe.edu/~moore/qip-slides.pdf .
Huck Bennett
1
BQP-completo? Alguém pode citar um problema completo do BQP, por favor?
Cem Say

Respostas:

32

Não se sabe que o isomorfismo do gráfico esteja no BQP. Muito trabalho foi feito para tentar inseri-lo. Uma observação muito intrigante é que o isomorfismo do gráfico poderia ser resolvido se os computadores quânticos pudessem resolver o problema de subgrupo oculto não abeliano do grupo simétrico (fatoração e log discreto são resolvidos por usando o problema do subgrupo oculto abeliano, que por sua vez é resolvido aplicando a transformada quântica de Fourier em grupos abelianos).

Uma das maneiras pelas quais as pessoas tentaram resolver o isomorfismo de grafos foi aplicando a transformada quântica de Fourier para grupos não abelianos. Existem algoritmos para a transformada quântica de Fourier para muitos grupos não abelianos, incluindo o grupo simétrico. Infelizmente, parece que pode não ser possível usar a transformada quântica de Fourier para o grupo simétrico para resolver o isomorfismo gráfico; existem muitos artigos escritos sobre isso que mostram que não funciona, dadas várias suposições sobre a estrutura do algoritmo. Estes documentos são provavelmente o que você encontra quando pesquisa no Google.

Peter Shor
fonte
1
Eu acho que os problemas que eu perguntei se enquadram na categoria 2 (QFT / HSP) na pergunta MathOverflow, e esse é o principal ponto em comum. Obrigado!
Huck Bennett
10
Esta é uma boa pesquisa sobre tudo o que Peter disse arxiv.org/abs/0812.0380
Marcos Villagra
Com o resultado do Prof. Babai no isomorfismo Graph, qual é a complexidade do algoritmo de computador Quantum na IG?
XL _At_Here_There
Não temos algoritmos quânticos que se saem melhor que os algoritmos clássicos neste momento.
quer
20

A resposta do folclore é que o fatoramento é "estruturado" de uma maneira que os problemas gerais completos de NP não são, e é por isso que só conseguimos encontrar vantagens quânticas para problemas intermediários.

Indiscutivelmente, uma versão mais simples da sua pergunta é olhar não para a complexidade computacional, mas para a complexidade da consulta das funções booleanas. Aqui, podemos dizer algumas coisas de maneira comprovada, como o fato de que as acelerações superpolinomiais são possíveis apenas para funções parciais (comprovadas em http://arxiv.org/abs/quant-ph/9802049 ) e não para funções simétricas em suas entradas e resultados (comprovados em http://arxiv.org/abs/0911.0996 ).

Esses resultados não lançam luz diretamente sobre a questão BQP vs NP, mas acho que são etapas significativas para determinar onde há vantagem quântica.

Aram Harrow
fonte