Considere la siguiente tarea computacional: Queremos muestrear una fórmula 3-SAT de variables (una variante: n variables m cláusulas) con respecto a la distribución de probabilidad uniforme, condicionada a que la fórmula sea satisfactoria:
P1: ¿Se puede lograr esto de manera eficiente con una computadora clásica (con bits aleatorios)?
P2: ¿Se puede lograr esto de manera eficiente con una computadora cuántica?
También estoy interesado en las siguientes dos variantes:
V2: Muestra todas las fórmulas con una distribución de probabilidad que da fórmulas satisfactorias dos veces el peso de las fórmulas insatisfactorias.
V3: muestra donde el peso es el número de tareas satisfactorias (Aquí solo nos preocupamos por Q2).
Actualización: la respuesta de Colins demuestra un algoritmo simple para V3. (Me equivoqué al suponer que esto es clásicamente difícil). Permítanme mencionar otra variante de las tres preguntas:
Especifica de antemano cláusulas y necesita muestrear subconjuntos aleatorios satisfactorios de las cláusulas de entrada.
Respuestas:
Hay un algoritmo simple para V3. Usaré la convención de que hay cláusulas posibles, entonces 2 8 n 3 fórmulas. (Esto es solo por simplicidad: si no desea que todas las cláusulas 8 n 3 se consideren válidas, no afectará el siguiente argumento).( 2 n )3 28 n3 8 n3
fuente