[ad_1]

## 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

objectiveof this article is to provide aself-containedpresentation of Grover’s Algorithm. We willavoid mathematical detailsas much as possible, thus providing a practical idea of the power of this quantum algorithm.

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

probabilityof getting thesolutionin a given run of the algorithm ishigherthanthe one of getting aninvalidoutput... Since the probability of getting a wrong output is non-zero, more runs can be required.

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).

However, don’t panic! The Diffuser implementation is the same for every oracle, and I’ll provide the code at the end! Promise!

**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! In this case, we refer to the Amplitude Amplification algorithm, which we can imagine as a generalized Grover’s Algorithm.

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.

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.

- 1) Generate all the possible assignments for the boolean formula:
**¬(¬x ∧¬y) ∧ ¬y**. - 2) Apply the Oracle.
- 3) Apply the Diffuser.
- 4) Perform measurements.

NOTETypically, we need to repeat steps 2) and 3) a number of times according to the formula:

where

nis the number of variables.In our example,

n=2(i.e.,xandy).Thus, the number of repetitions is1. 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.

## 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

conditionthat the input has to satisfy to be our solution (i.e., youroracle/your function!)

Follows the oracle circuit (Figure 12).

Don’t panic! We are going to analyze in detail the whole circuit ❤

## DETAILS

We observe 3 additional qubits in the oracle circuit, respectively:

- 2 working qubits
**w.** - a qubit
**checker.**

## Working qubits

We add as many working qubits

was 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.

## Checker qubit

The purpose of the qubit **checker** is to **mark** the correct solution. That is, when a variables assignment satisfies the oracle conditions, then the **checker** is flipped to **1**.

**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

w0corresponds to¬x ∧¬yand 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-X gate* where:

**w0**and**w1**are the control qubits,**checker**is the target qubit that**flips 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)**.**

The output distribution follow 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!**

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.🎉

[ad_2]

Source link