Oracle

A quantum computing demo using various oracles in Grover's algorithm.

Read the full article Quantum Computing Hello World.

Here's an example for printing "Hello World"!

Random letters:
['l', 'h', 'Q', 'o', 'l', 'Q', 'C', 'e']

Final result from the quantum circuit:

h (at index 1 [001])
e (at index 7 [111])
l (at index 0 [000])
l (at index 0 [000])
o (at index 3 [011])

What is it?

Oracle is a tutorial example of writing a quantum computing program in Qiskit that searches through a random array of letters in order to find each letter in sequence for a target sentence, such as "Hello World!".

The idea is similar to the traditional ransom note problem. You're given a magazine of randomly cut out letters. The letters are strewn across a table in a random fashion. Your task is to find enough letters from the table in order to paste them together to produce the phrase "hello world".

Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.

Other Examples

• Hello World
• Even Numbers
• Odd Numbers
• Magic Eight Ball

Why would you use a quantum computer for this?

To demonstrate the power of a quantum computer compared to a classical one, of course!

On a classical computer, the time complexity for searching through an unordered list of elements would take O(n). That is, in the worst case we would need to iterate through the entire array in order to locate a target element - if the last element in the array is the target.

By contrast, a quantum computer using Grover's algorithm can locate the target element in O(sqrt(n)). This provides a quadratic speed-up in time complexity to find the target element. A quantum computer does this by representing each bit in the length of the array with a qubit. For example, for a random array of length 8, we can represent this on a quantum computer using 3 qubits, which gives us 2^3=8 possible combinations. Since a quantum computer can calculate all possible values for qubits within a quantum circuit in a single cycle, the program can evaluate all potential indices in the array in order to locate the target element.

While the example in this tutorial of selecting letters from an array of random elements is simplistic, it nevertheless demonstrates the speed-up in time complexity for searching and locating the desired elements.

Hello World

Below is an example of a random array being searched to produce the word "hello".

Consider the following array of random letters that we want to search through to produce the word "hello".

['a','y','h','p','e','o','l','l']

Length = 8

Running on a classical computer

On a classical computer, we would iterate through the array in order to search for each letter. For the first letter, 'h', we search up to index 3 to locate the letter. However, for letter 'l' we need to search through the entire array to locate the letter at index 7. In the worst-case scenario, this algorithm requires searching through all elements, thus it has a time complexity of O(n).

For an entire phrase, "hello", we could leverage a hash map to store the indices of the elements within the array. This would take O(n) to create the hash map of indices. We could then iterate through each letter in the target string and retrieve each index. This would take an additional O(m), where m = length of the phrase (5), as each lookup in the hash is a single execution of O(1).

This would be a total time complexity of O(n+m) => O(n).

Running on a quantum computer

On a quantum computer, we can represent each index within the array using enough qubits to represent the length of the array. In this example, we have an array of length 8, thus we can represent this number of indices in the array using 3 qubits. This is equivalent to 2^3=8 possibilities for 3 qubits.

In simplified terms, a quantum computer can effectively search through all possibilites of qubit values in a single CPU cycle.

Imagine the 3 qubits in this example 000, 001, 010, 011, etc. being searched simulataneously for the target letter. In this manner, a single CPU cycle on a quantum computer can look in the array at each possible index and determine if the letter is located at that slot. After just 1 cycle, we can return the index 011=3 for the letter 'h'. Likewise, in a single cycle, we can locate the letter 'l' at the last index of 111=7.

This solution has a time complexity of O(sqrt(n)). For the entire phrase, "hello", we iterate across each letter in the target phrase (5 times in total) to execute the quantum circuit for a single CPU cycle. This would take an additional O(m), where m = length of the phrase (5).

This would be a total time complexity of O(sqrt(n)+m) => O(sqrt(n)).

Creating the Oracle

Grover's algorithm on a quantum computer works by using an oracle.

An oracle is a black-box mechanism that indicates to the quantum program circuit when a correct solution has been found. Without an oracle, the quantum computing algorithm would have no means of determining when it has located the correct letter in the sequence for the target phrase.

An oracle can consist of logic that determines a solution state, given the values for the qubits being evaluated, or it can simply give the solution state (as seen in this tutorial). Consider an example of simplified Sudoku, where a unique number must exist within a row or column with no duplicate. We could design an oracle using logic for this problem by representing clauses for the logic using qubits. Since each combination of qubit values can represent a different combination of clauses, we can determine when a satisfactory solution is associated with those clauses (in that no duplicated number exists in the same row or column) and thus those qubit values become a solution.

The oracle used in this tutorial is a very simplistic one. Rather than using a logical set of clauses, we'll have the oracle simply return the target index for the desired letter. The quantum circuit will still execute a full search and use the oracle to determine which combination of qubits is a valid solution. This allows us to more easily see how to construct an oracle for a quantum computer.

Creating the clauses for the Oracle

As a quantum computing Oracle requires some means of determining a valid solution of qubit values, we need a way to represent our target indices for each letter. The way that we can do this is to create a logical function for the correct qubit values and provide this function to the oracle.

Keep in mind, typically an Oracle does not know ahead-of-time what the correct solution is, rather it formulates the solution from given clauses and identifies the qubit solution values. However, for this example, we are more or less directly providing the Oracle with the solution via a logical function (to serve as our clause) in order to demonstrate a simple example of searching for elements in an unordered list.

To create the logical function, we first identify the target element index in the array. Let's suppose the letter 'l' is found at index 0 (000) and 3 (011). We formulate a logical clause using the following Python function structure:

(not x1 and not x2 and not x3) or (x1 and x2 and not x3)

We pass the clause into our Oracle builder, which returns a QuantumCircuit. Specifically, we leverage the Qiskit method ClassicalFunction and synth method in order to automatically generate the quantum circuit from the Python function.

# Convert the logic to a quantum circuit.
formula = ClassicalFunction(logic)
fc = formula.synth()

This generates the following quantum circuit for the above example.

(not x1 and not x2 and not x3) or (x1 and x2 and not x3)

q_0: ──■───────
       │
q_1: ──┼────o──
       │    │
q_2: ──o────o──
     ┌─┴─┐┌─┴─┐
q_3: ┤ X ├┤ X ├
     └───┘└───┘

We then insert this quantum circuit oracle into our parent quantum circuit program to complete Grover's algorithm and run the application.

Let's take a quick look at how we map qubits to indices within the array.

Mapping qubits to letters

Consider the following array of random letters that we want to search through to form the word "hello".

['a','y','h','p','e','o','l','l']

The length of this array is 8 and can thus be represented using 3 qubits, since 2^3=8. This means we can get 8 different combinations of values for those qubits, which correspond to all possible indices in the array.

Imagine that when the quantum program runs, it simulataneously evaluates all possible combinations of qubits, calling the oracle for each one, and getting back an indication of which combination is a valid solution. For the letter 'h' the only solution is at index 2 or 010.

Index o