1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ @MonteNero So what is the answer of my question based on question that you refer? $\endgroup$ Jan 9, 2023 at 2:00
  • 1
    $\begingroup$ What is explained in the other question is that generally, even when building the oracle, you don't know the solution of the problem. Think about it in a classical way: you are able, being given a 3-SAT instance, to write a function $f$ such that $f(x)=1$ iff $x$ is a solution to your problem, without knowing the solution $x$ itself (it's just a verification function). In a real-world case, this is the function you will implement as a quantum oracle, which can be done without knowing the solution. The example you took is simply a toy one to understand the process, though it can be misleading. $\endgroup$
    – Tristan Nemoz
    Jan 9, 2023 at 5:29
  • $\begingroup$ So does it mean I should use classical computation or manual computation whenever I'm finding out oracle matrix? $\endgroup$ Jan 9, 2023 at 7:25
  • 1
    $\begingroup$ @MuhammadIkhwanPerwira Yes, classical computation will be used to create the circuit of the oracle (this is fast to do). Once you got the circuit, you can construct the whole circuit of Grover's algorithm (once again, classically), and then run this circuit on a Quantum Computer to get a quadratic speedup. $\endgroup$
    – Tristan Nemoz
    Jan 9, 2023 at 11:17
  • $\begingroup$ @TristanNemoz (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$ Jan 9, 2023 at 14:41

0