Considere a seguinte tarefa computacional: Queremos provar uma fórmula 3-SAT de variáveis (uma variante: variáveis cláusulas) com relação à distribuição uniforme de probabilidade, condicionada à satisfação da fórmula:n m
Q1: Isso pode ser alcançado com eficiência por um computador clássico (com bits aleatórios)?
P2: Isso pode ser alcançado com eficiência por um computador quântico?
Também estou interessado nas duas variantes a seguir:
V2: Você mostra todas as fórmulas com uma distribuição de probabilidade que fornece fórmulas satisfatórias duas vezes o peso de fórmulas insatisfatórias.
V3: você mostra onde o peso é o número de tarefas satisfatórias (aqui nos preocupamos apenas com o Q2).
Atualização: A resposta de Colins demonstra um algoritmo simples para a V3. (Errei ao supor que isso é classicamente difícil.) Deixe-me mencionar outra variante de todas as três perguntas:
Você especifica antecipadamente cláusulas e precisa amostrar subconjuntos aleatórios e satisfatórios das cláusulas de entrada.
Respostas:
Existe um algoritmo simples para V3. Usarei a convenção de que existem possíveis cláusulas, portanto, fórmulas. (Isso é apenas para simplificar - se você não quiser que todas as cláusulas sejam consideradas válidas, isso não afetará o seguinte argumento.)2 8 n 3 8 n 3(2n)3 28n3 8n3
Escolha uma tarefa aleatória entre . Para cada uma das possíveis cláusulas verdadeiras nesta atribuição, inclua a cláusula com probabilidade . Cada fórmula aparecerá com probabilidade proporcional ao número de tarefas satisfatórias. A variante da cláusula é semelhante: escolha um conjunto de tamanho dentre as cláusulas . 7 N 3 1 / 2 φ m m 7 n 3{0,1}n 7n3 1/2 ϕ m m 7n3
fonte