Aparentemente, algoritmos quânticos têm pouco a ver com computação clássica e P vs NP em particular: resolver problemas de NP com computadores quânticos não nos diz nada sobre as relações dessas classes de complexidade clássica 1 .
Por outro lado, a 'descrição alternativa' da classe de complexidade clássica PP como a classe PostBQP apresentada neste artigo é, tanto quanto sei, considerada um resultado importante para 'complexidade clássica', por 'complexidade quântica' .
De fato, Scott Aaronson, autor do artigo, escreve no final do resumo:
Isso ilustra que a computação quântica pode produzir provas novas e mais simples dos principais resultados sobre a computação clássica.
Portanto, minha pergunta é: existem resultados do campo da complexidade quântica que "simplificam" o problema P vs NP, semelhante à descrição quântica de PP? Se não houver tais resultados, há uma boa razão para não esperar esses resultados, apesar do 'sucesso' do PP?
1: Pegue a resposta a esta pergunta, por exemplo: o problema P vs. NP se tornaria trivial como resultado do desenvolvimento de computadores quânticos universais?
fonte
Respostas:
Não acho que haja razões claras para uma resposta "sim" ou "não". No entanto, posso fornecer uma razão pela qual o PP tinha muito mais probabilidade de admitir tal caracterização do que o NP , e dar algumas intuições para o motivo pelo qual o NP nunca poderia ter uma caracterização simples em termos de modificação do modelo computacional quântico.
Contando complexidade
As classes NP e PP podem ser caracterizadas em termos do número de ramos aceitantes de uma máquina de Turing não determinística, que podemos descrever de maneira mais prática em termos dos possíveis resultados de uma computação aleatória que utiliza bits uniformemente aleatórios. Podemos então descrever essas duas classes como:
L ∈ NP se houver um algoritmo aleatório de tempo polinomial que produza um único bit α ∈ {0,1}, tal que x ∈ L se e somente se Pr [ α = 1 | x ] é diferente de zero (embora essa probabilidade possa ser pequena), em oposição a zero.
L ∈ PP se houver um algoritmo aleatório de tempo polinomial que produza um único bit α ∈ {0,1}, tal que x ∈ L se e somente se Pr [ α = 1 | x ] é maior que 0,5 (embora possivelmente apenas na menor quantidade), em vez de ser igual ou menor que 0,5 ( por exemplo, em uma quantidade minúscula).
Uma maneira de ver por que essas classes não podem ser praticamente resolvidas usando essa descrição probabilística é que pode levar exponencialmente muitas repetições para ter certeza de uma estimativa de probabilidade para Pr [ α = 1 | x ] por causa da pequenez das diferenças nas probabilidades envolvidas.
Complexidade de lacunas e complexidade quântica
Vamos descrever os resultados '0' e '1' no cálculo acima como 'rejeitar' e 'aceitar'; e vamos chamar uma ramificação aleatória que fornece um resultado de rejeição / aceitação, uma ramificação de rejeição ou aceitação . Como todo ramo da computação aleatória que não está aceitando está, portanto, rejeitando, o PP também pode ser definido em termos da diferença entre o número de caminhos computacionais de aceitação e rejeição - uma quantidade que podemos chamar de lacuna de aceitação : especificamente, se a aceitação a diferença é positiva ou menor ou igual a zero. Com um pouco mais de trabalho, podemos obter uma caracterização equivalente para PP, em termos de se a diferença de aceitação é maior que algum limite ou menor que algum limite, que pode ser zero ou qualquer outra função computável da entrada x .
Por sua vez, isso pode ser usado para caracterizar linguagens em PP em termos de computação quântica. A partir da descrição do PP em termos de cálculos aleatórios com probabilidades de aceitação (possivelmente ligeiramente) maiores que 0,5 ou no máximo 0,5, todos os problemas no PP admitem um algoritmo quântico de tempo polinomial que tem a mesma distinção em probabilidades de aceitação; e modelando cálculos quânticos como uma soma sobre caminhos computacionais e simulando esses caminhos usando ramos rejeitados para caminhos com peso negativo e aceitando ramos de caminhos com peso positivo, também podemos mostrar que esse algoritmo quântico que faz uma distinção (estatisticamente fraca) descreve um problema no PP .
Não é óbvio que possamos fazer o mesmo pelo NP . Não existe uma maneira natural de descrever o PN em termos de lacunas de aceitação, e o palpite óbvio de como você pode tentar ajustá-lo ao modelo computacional quântico - perguntando se a probabilidade de medir um resultado '1' é zero ou não- zero - em vez disso, fornece uma classe chamada coC = P , que não é conhecida como NP , e pode ser descrita como sendo tão poderosa quanto a PP, em vez de próxima à NP no poder.
Certamente, algum dia alguém poderá encontrar uma caracterização de NP em termos de lacunas de aceitação, ou poderá encontrar novas maneiras de relacionar a computação quântica à complexidade da contagem, mas não tenho certeza de que alguém tenha alguma idéia convincente de como isso pode acontecer.
Sumário
As perspectivas de obter informações sobre o problema P versus NP em si, via computação quântica, não são promissoras - embora não sejam impossíveis.
fonte