Algum algoritmo quântico aprimora o SAT clássico?

29

Algoritmos clássicos podem resolver 3-SAT em tempo (aleatório) ou tempo (determinístico). (Referência: Melhores limites superiores no SAT )1,3303 n1.3071n1.3303n

Para comparação, o uso do algoritmo de Grover em um computador quântico procuraria e forneceria uma solução em , randomizada. (Isso ainda pode exigir um conhecimento de quantas soluções podem ou não existir, não tenho certeza do quanto esses limites ainda são necessários.) Isso é claramente significativamente pior. Existem algoritmos quânticos que se saem melhor do que os melhores algoritmos clássicos (ou pelo menos - quase tão bons?)1.414n

Obviamente, os algoritmos clássicos poderiam ser usados ​​em um computador quântico, assumindo espaço de trabalho suficiente; Eu estou querendo saber sobre algoritmos quânticos inerentemente.

Alex Meiburg
fonte

Respostas:

21

Penso que se pode obter um limite superior não trivial da computação quântica, acelerando os algoritmos aleatórios de Schöning para o 3-SAT. O algoritmo de Schöning é executado no tempo e usando técnicas padrão de amplificação de amplitude, é possível obter um algoritmo quântico que é executado no tempo que é significativamente mais rápido que o algoritmo clássico. ( 2 / (4/3)n(2/3)n=1.15n

wwjohnsmith1
fonte
Bom, isso parece certo. Mostra que eu deveria ter analisado os algoritmos clássicos uma vez antes de perguntar! :) Um pouco mais de pesquisa sugere que o melhor algoritmo aleatório para o 3-SAT (não necessariamente único) é , então acho que poderíamos esperar de um computador quântico ... obrigado! 1.1492 n1.32065n1.1492n
precisa saber é o seguinte
Talvez você também goste deste artigo: digitalcommons.utep.edu/cgi/…
Martin Schwarz
30

De fato, como wwjohnsmith1 disse, você pode obter uma aceleração da raiz quadrada do algoritmo de Schöning para o 3-SAT, mas também de maneira mais geral para o algoritmo de Schöning para o k-SAT. De fato, muitos algoritmos aleatórios para k-SAT podem ser implementados quadraticamente mais rápido em um computador quântico.

A razão para esse fenômeno geral é a seguinte. Muitos algoritmos aleatórios do k-SAT que são executados no tempo (onde é uma função exponencialmente crescente de ) realmente fazem algo mais forte. Em sua essência, existe um algoritmo de tempo polinomial que gera uma atribuição satisfatória, se houver, com probabilidade de pelo menos . A partir disso, fica claro que, se você repetir esse algoritmo poli-tempo muitas vezes e aceitar se alguma das execuções retorna uma solução, você obterá um algoritmo aleatório para o k-SAT que é executado no tempo .O(T(n)poly(n))T(n)n1/T(n)O(T(n))O(T(n)poly(n))

Agora, em vez de executar esse algoritmo vezes, você pode executar a amplificação de amplitude nesse algoritmo de politempo. Amplificação de amplitude é um algoritmo quântico geral que pode decidir se outro algoritmo aceita com probabilidade 0 ou com probabilidade usando apenas usa esse algoritmo. A aplicação da amplificação de amplitude a um solucionador de k-SAT produzirá imediatamente um algoritmo quântico para k-SAT com tempo de execução , que é quadraticamente mais rápido (ignorando o poli (n) termo).O(T(n))1/TO(T)O(T(n)poly(n))

Robin Kothari
fonte