Grover en acción

El problema a resolver

Vamos a resolver el problema 3SAT dado por

$\mathrm{\neg }(\mathrm{\neg }x\wedge \mathrm{\neg }y)\wedge \mathrm{\neg }y$

usando el algoritmo de Glover. Para ello necesitamos crear el Oráculo que define la acción de las cláusulas lógicas anteriores sobre los qubits. Vamos a representar $x$ e $y$ por los cubits q[0] y q[1] respectivamente.

El oráculo

Empecemos por ver qué hace el siguiente circuito:

cuya implementación es SAT Oracle Clause 1.

Efectivamente, este circuito hace la operación AND: $\mathrm{\neg }x\wedge \mathrm{\neg }y$ y si el cubit 2 está en el estado 0, se guarda el resultado de dicha operación en el mismo. Finalmente los NOT sobre los cubit 0 y 1 los devuelven a su estado original.

De la misma forma se puede seguir operando sobre los cubits, negando ahora el resultado de la operación anterior para obtener $\mathrm{\neg }(\mathrm{\neg }x\wedge \mathrm{\neg }y)$ en el cubit 3

En el siguiente paso, se realiza el último AND entre el resultado anterior y $\mathrm{\neg }y$.

Finalmente, es necesario deshacer las operaciones sobre los cubits auxiliares q[2] y q[3]. En efecto, como el estado cuántico está compuesto de todas las contribuciones de los cubits, es importante ‘borrar’ el estado de esos cubits auxiliares para que solamente se tenga como inputs los valores necesarios de los cubits 0, 1 y 4 en el siguiente paso.

El circuito difusor

Para el difusor se propone el siguiente circuito:

que se encuentra acá.

Finalmente, el circuito completo es SAT Solver

El resultado que se obtiene al correr 1024 instancias es:

Es decir, $x=1$ y $y=0$ con alta probabilidad, que es el resultado esperado clásicamente.