Based on reference I read in this site learn.qiskit.org here is simple problem example about 3-SAT problem in dimacs format:
c example DIMACS-CNF 3-sat
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
And here is the solution I find using classical algorithm with using python:
from random import randint
# three variable
x1 = 0
x2 = 0
x3 = 0
def formula(x1, x2, x3):
#c stand for clause
c1 = (not x1) or (not x2) or (not x3)
c2 = x1 or (not x2) or x3
c3 = x1 or x2 or (not x3)
c4 = x1 or (not x2) or (not x3)
c5 = (not x1) or x2 or x3
return c1 and c2 and c3 and c4 and c5
result = []
for i in range(32):
x1 = randint(0, 1)
x2 = randint(0, 1)
x3 = randint(0, 1)
if formula(x1, x2, x3) == True:
result.append((x3, x2, x1)) #bit order, x3 is MSB, x1 is LSB
print(set(result))
And here is the output:
{(0, 0, 0), (1, 0, 1), (0, 1, 1)}
So the solution is 000, 011, 101
based on classical computation.
Now let's talk about quantum computing about 3-SAT problem with using Grover's Algorithm.
This is the overview of Grover's Algorithm based on that site:
Now we understand the problem, we finally come to Grover’s algorithm. Grover’s algorithm has three steps:
1. The first step is to create an equal superposition of every possible input to the oracle.
2. The next step is to run the oracle circuit on these qubits. On this page, we'll use the circuit (oracle).
3. The final step is to run a circuit called the 'diffusion operator' or 'diffuser' on the qubits.
Based on that step, we should FIND the oracle matrix. I will quote what that site says about this.
For example, the only solutions to this problem are 000, 011, and 101, so the circuit above has this matrix:
As you see, we already found the solution to this problem after we find out the oracle matrix. So why should we run the quantum circuit until measurement or even using diffuser while we already found the solution? Basically finding oracle matrix is already require computation power. I thought quantum computer will find oracle matrix by itself, turn out it still need done by classical computer.
(this is fast to do)
, why are you sure? I need to know the algorithm to prove is it really fast or not. So far the python code I provided above is require 32 repetition to find solution so that it can be used to construct oracle. $\endgroup$