Behind Oracles: Grover’s Algorithm
Catching the high-level idea and how to implement an oracle for SAT instances
At the beginning of my journey in Quantum Computing, I was confused about what an “oracle” was. Typically, you read something like:
“(…) then, thanks to the oracle, you are able to identify the solution.”
In the end, the only thing that I understood was that:
“It is able to catch the solution of a given problem (somehow)”.
Nevertheless, I didn’t know how. Thus, questions like the followings arise.
What does this “oracle” look like?
How can I identify something that I don’t know a priori?
These are legitimate questions! We will find out the answer to all these questions! In particular:
- We will understand why oracles are important.
- We will catch the high-level intuition behind an oracle.
- We will show how to define an oracle able to solve a Boolean Satisfiability Problem (SAT)
- Furthermore, an implementation in Qiskit will be provided!
Before to start, you need just a few prerequisites:
- What superposition is.
- What quantum gates like H, X, CX are.
- What quantum circuits are.
The objective of this article is to provide a self-contained presentation of Grover’s Algorithm. We will avoid mathematical details as much as possible, thus providing a practical idea of the power of this quantum algorithm.
Why so important?
The “oracle” is part of Grover’s Algorithm: one of the most disruptive quantum algorithms and one of the reasons why quantum computing attracts a lot of interest.
What is the strength of Grover’s Algorithm?
Let us say we need to find a specific target element in an unstructured set of N elements.
In classical computing, since we have no prior knowledge about where this target element is located, we would need to look at every single element.
For example, suppose looking for the number 3 in an unsorted array (Figure 1).
The cost is O(N) (i.e., in the worst case, we need to scan all the N elements).
In quantum computing, thanks to Grover’s Algorithm, it is possible to retrieve the solution in O(√N). We achieved a quadratic speedup with respect to classical computing (Figure 2)!
A little background
Typically, quantum computers have to run a given quantum algorithm more than just a single time. Sometimes they return the correct output, and sometimes they do not.
Thus, our objective is to increase (or “amplify”) the chances of getting the correct output (Figure 3).
The point is that:
We want a probability distribution of the outputs from quantum computers such that the probability of getting the solution in a given run of the algorithm is higher than the one of getting an invalid output.
.. Since the probability of getting a wrong output is non-zero, more runs can be required.
GROVER’S BUILDING BLOCKS
Grover’s Algorithm is made of two parts: an Oracle and a Diffuser.
ORACLE
- The Oracle “marks” the solution(s) (Figure 4).
Thanks to the oracle, we are able to mark the correct element among all the N elements of an unstructured set of data. (Don’t paw! I will tell you shortly what the oracle looks like ❤)
However, the oracle alone is not enough.
In fact, the oracle just marks the correct element, but it does not increase the probability of getting this element as the output of the quantum algorithm. Indeed, the oracle alone would be useless since the probability of getting this element would be 1/N (i.e., at random!).
Visual Example
Let us say that we have N=7 elements, and we look for the element “triangle rectangle” (i.e., our solution). Thus, we apply the oracle that marks “triangle rectangle”.
However, the probability of getting the triangle rectangle is 1/7 (Figure 5), which is the same as getting one of all the other elements! :(
Here the Diffuser comes to the rescue! In fact, it is able to increase the chances of getting the triangle rectangle!
THE DIFFUSER
- The Diffuser “amplifies” the solution(s) (Figure 6).
Why the Diffuser works, is out of the scope of this article. For those curious, I will provide you some references at the end of this article.
The point is that it increases the chances of getting the element marked by the oracle as output (Figure 7).
We can set the Diffuser aside and move to answer the question:
“What does an oracle look like”?
Behind the Oracle
I found the name “oracle” a little misleading. It seems that there is someone that can give you the solution by just asking: “What is the solution?”.
I prefer to picture in my mind the image of a filter! It is up to you to handcraft a filter that has the exact shape of the element you look for (Figure 8)!
Why a filter?
Well, before running Grover’s Algorithm, in some sense, you possess all the elements (I’ll explain how later, but it is pretty straightforward), and you want to filter out the ones that are not your solution.
Still, keep in mind that you, and only you, carefully define this filter.
Now, a question may arise:
I have to design a filter that is able to catch the solution and reject all the other elements. But to be able to catch the solution, I need to know the solution, right?
Thus, this means that I already know the solution. So…
What’s the point of this algorithm?
That is a legitimate concern!
One Step back
Grover’s Algorithm’s original name is “A fast quantum mechanical algorithm for database search.” Thus, the examples I found were on looking for a number in a set of numbers.
If you want to find number 3 in a dataset, you already know the solution a priori. You were defining an oracle that caught for number 3, and the output was 3. Nothing too exciting in the first instance, right?
[Small Note 1] In Grover’s algorithm, you need to know a priori that a solution exists (actually, you need to know the exact number of solutions).
[Small Note 2] There are other quantum algorithms that find out the number of solutions to a given problem. Then, you can use Grover’s algorithms.
Two Step ahead
The turning point is that the oracle can be a function, not just a number!
What do you intend for “an oracle can be a function”?
For example, we can ask our quantum computer: “What is that element greater than 5 and less than 6”?
x > 5 ∧ x < 6
The mental step is small, but the point is that we don’t need to know the solution, which will be your oracle! Hence, obtaining a quadratic speed up with respect to the classical brute force algorithm! Now It is time to stop merely talking and start acting.
Solving SAT with a quadratic speedup
A SAT problem consists in finding an assignment of variables such that it satisfies a given Boolean formula. (I recall you that SAT belongs to the NP-complete class, a very interesting problem!)
For example, in (¬ x1 ∧ x2), the assignment that satisfies the boolean formula is:
x1=False, x2=True
In particular, we focus on a particular form of Boolean formula, the Conjunctive Normal Form (CNF) or Clausal Normal Form.
CNF Refresh
The CNF consists of conjunctions of one or more clauses.
- Each clause contains one or more literals (boolean variables).
- A CNF contains only the operators: ¬(not), ∨ (or), ∧ (and).
- The conjunctions of clauses are obtained by means of the ∧ operator.
- The literals of each clause are related by the ∨ operator
- The ¬ operator can only be used as part of a literal.
Example of a CNF:
(x ∨ y) ∧ ¬y
The solution assignment is: x=True, y=False
We will define the quantum circuit that solves the above CNF.
Before starting, let us rewrite the CNF instance above in terms of AND using De Morgan rules (Figure 9). Why? Just because it will be easier to describe the oracle later :)
Thus, we rewrite (x ∨ y) ∧ ¬y as ¬(¬x ∧¬y) ∧ ¬y.
In particular, we will define an oracle that marks the solution of:
¬(¬x ∧¬y) ∧ ¬y
For simplicity, let us assume that we already know that the above instance has a single solution. At the end of the article, I’ll explain why we make this assumption.
THE QUANTUM CIRCUIT
- 1) Generate all the possible assignments for the boolean formula: ¬(¬x ∧¬y) ∧ ¬y.
- 2) Apply the Oracle.
- 3) Apply the Diffuser.
- 4) Perform measurements.
NOTE
Typically, we need to repeat steps 2) and 3) a number of times according to the formula:
where n is the number of variables.
In our example, n=2 (i.e., x and y). Thus, the number of repetitions is 1. That is, we apply just one time the oracle and the diffuser.
If you want to learn more about how this formula is obtained, I will leave you some references at the bottom of the article.
Setting up the stage
We have 5 qubits in our circuit, respectively:
- 1 qubit x (input qubit);
- 1 qubit y (input qubit);
- 2 qubits w (working qubit);.
- 1 qubit marker.
Input qubits
The input qubits are x and y. These qubits will encode all the possible input configurations (among which we will find our solution).
Working qubits
We add as many working qubits w as the number of clauses of the CNF instance. The scope of working qubits is to store the output of a given clause temporarily.
In our example, ¬(¬x ∧¬y) ∧ ¬y, we have 2 clauses then 2 working qubits w are needed.
Marker qubit
The purpose of the qubit marker is to mark the correct solution. That is, when a variables assignment satisfies the oracle conditions, then we apply a controlled Z gate on the marker qubit. This step changes the phase of the marker qubit (i.e., 1 to -1) for the configuration of the input representing a solution.
STEP 0: Flip to state 1 the marker qubit
This step will be fundamental to marking the solution configuration by changing the phase of the marker qubit.
STEP 1: Generate all the possible assignments for the boolean formula
We put into superposition all of our qubits by means of Hadamard gates (Figure 10)! That is, we generate all the possible assignments for our boolean formula.
Since we know that a solution exists, then our solution is within the assignments (Figure 11) we generated by putting into equal superposition all the qubits.
STEP 2: Apply the Oracle
I want to stress that, in this example, we do not know the solution like in the example “Look for number 3”.
In general, by defining the SAT instance, we just defined the condition that the input has to satisfy to be our solution (i.e., your oracle/your function!)
Follows the oracle circuit (Figure 12).
Don’t panic! We are going to analyze in detail the whole circuit ❤
CLAUSES
We break down ¬(¬x ∧¬y) ∧ ¬y into three parts (Figure 13):
- Clause 1. w0 = ¬x ∧¬y
- Clause 2. w1 = ¬y
- Result. ¬w0 ∧ w1
Note that w0 corresponds to ¬x ∧¬y and not to ¬(¬x ∧¬y)!
We postponed the first ¬ to ¬w0 ∧ w1.
Clause 1. w0 = ¬x ∧¬y
Clause 1 checks the condition ¬x ∧¬y (Figure 14). It is implemented by means of a MultiControlled-X gate where:
- x and y are the control qubits,
- w0 is the target qubit that stores the result of the condition ¬x ∧¬y.
Please note that the MultiControlled-X gate must trigger when ¬x and ¬y. To do so, we prepend and append two X gates respectively to x and y, thus negating them.
Clause 2. w1 = ¬y
Clause 2 checks the condition ¬y (Figure 15). It is implemented by means of a Controlled-X gate where:
- y is the control qubit,
- w1 is the target qubit that stores the result of the condition ¬y.
As before, since we look for the clause ¬y, thus we negate the qubit y in the Controlled-X gate.
Result. ¬w0 ∧ w1
Result checks the condition ¬w0 ∧ w1 which corresponds to our CNF instance ¬(¬x ∧¬y) ∧ ¬y (Figure 16). The condition ¬w0 ∧ w1 is implemented by means of a MultiControlled-Z gate where:
- w0 and w1 are the control qubits,
- marker is the target qubit that changes the phase to -1 if ¬w0 ∧ w1 is satisfied.
We recall that w0 corresponds to ¬x ∧¬y and not to ¬(¬x ∧¬y).
Therefore, we need to negate w0: ¬(¬x ∧¬y) = ¬w0.
UNCOMPUTATION
The oracle’s last step frees the working qubits w0 and w1. This is achieved by performing uncomputation (Figure 17).
To uncompute w0 and w1 it is sufficient to apply the gates implementing Clause 1 and Clause 2 in reversed order.
Eventually, we handcrafted our oracle! The magic has been revealed!
STEP 3: Apply the Diffuser
Last, we apply the Diffuser operator, which amplifies the correct solution (Figure 18).
STEP 4: Measurement
Eventually, we measure qubits x and y (Figure 20).
Note: we applied an X gate on the marker qubit at the beginning of the circuit. This is essential for the interference to occur and thus for the whole algorithm to work.
The output distribution follows in Figure 21.
The highest probability corresponds to the assignment:
y=0 (False), x=1(True) (i.e., 01).
In particular, the assignment 01 satisfies our CNF instance ¬(¬x ∧¬y) ∧ ¬y!
CONCLUSION
The main objective of this article is to give a self-contained presentation of oracles and how to implement them using Qiskit. In particular:
- We catch the idea of what Oracles are.
- The purpose of the Diffuser.
- How to effectively implement an Oracle and a Diffuser in Qiskit.
In the references below, you can find my Github repository with the Qiskit implementation so that you can play with it :)
AH! In the presented example, the number of solutions was exactly 1. However, we can have more than one solution for a given problem! In those cases, we need to make a small change in the formula that computes the number of repetitions of the couple Oracle-Diffuser. In particular, the formula becomes:
In the Github repository, you will also find an example of a CNF instance with more than one solution to play with it. 🎉
Concluding Remarks
I deliberately avoided technical details to let you grasp the general idea 💡.
When I started studying Quantum Computing, I would appreciate this kind of overview. This is the reason why I decided to write this article ❤.
I really hope that you appreciated it too! In case, feel free to leave a clap or a comment. Any kind of feedback will be super valued!
Let’s keep in touch on LinkedIn!
References
- 💻 Qiskit implementation here 👈
- 🔍 Detailed presentation of Grover’s Algorithm here 👈
- 📚 For a comprehensive book here 👈
