Construct Grover's circuit to find solutions of a Boolean function
Grover's search algorithm is a quantum algorithm that efficiently finds a marked item in an unsorted database. The algorithm is also applicable to solving the satisfiability problem (SAT), where the goal is to determine if there exists an assignment of variables that satisfies a given Boolean formula.
The action of a Boolean oracle is defined by this transformation:
|x〉|q〉->|x〉|q⊕f(x)〉
with
|x〉
the index register state of n-qubits, and
|q〉
the state of an ancillary qubit carrying the result of Boolean function
f(x)
; meaning if
|q〉=|0〉
then it will be
|1〉
if x is a solution of f(x), and no change if not.
Define a Boolean function of 3-SAT with 5 clauses:
We shall prepare the 4-qubit in the above circuit (i.e., the ancillary qubit) in the 0 state, and then other qubits (1-3) in the index register states. To compare with the above truth table, we will create the index register states
Contents cannot be rendered at this time; please try again later
Generate the corresponding Grover circuit using a Boolean oracle:
In[14]:=
QuantumCircuitOperator[{"Grover",bf}]["Diagram"]
Out[14]=
Contents cannot be rendered at this time; please try again later
Consider the following Boolean function and explore different cases and how the probability of success of the algorithm depends on circuit design or the initial state of the ancillary qubit: