Interested in learning how to program quantum computers? Then check out our Qiskit textbook Introduction to Quantum Computing with Qiskit.
Introduction
In this tutorial we will learn how to satisfy logical expressions using Grover’s Search algorithm in Qiskit on IBM’s quantum devices.
A logical expression can be defined as an expression made up of a combination of variables that can be true or false. For example consider the following expression:
A AND B
This consists of two variables A, B. The AND operation means that the function will be true if both A,B are true.
Truth table
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Where A and B are variables and F is the output.
A OR B
This again consists of two variables A,B. The OR operation means the function will be true if either A or B are true.
Truth Table
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Where A and B are variables and F is the output.
These expressions can get more complex for example:
(A AND B) OR (C)
This would mean that the function is true if A and B are both true OR C is true.
Truth Table
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
As the number of variables and clauses increases in the expression the more harder it is for a classical computer to evaluate the expression.
However using Grover’s search algorithm we can find the variable combinations needed that will satisfy the logical expression. Grover’s algorithm has a huge advantage over classical methods as the time complexity is only O(√n).
Implementation
Grover’s search for logical expressions can be implemented very easily in Qiskit with the following steps:
Step 1: Specify the logical expression
The first step is to specify the logical expression. In Qiskit the logical expression has to be in a specific format where the ‘AND’ operation is replaced with ‘&’ and the OR operation is replaced with ‘^’. Negation is done with the ‘~’ character.
For example for the logical expression A AND B we would write:
expression = '(a & b)'
For the logical expression (A AND B) AND NOT(C):
expression = '(a & b)& ~(c)'
Step 2: Specify the oracle and pass to the Grover function
The first step is to specify the correct oracle. Since we are evaluating logical expressions you will need to use the LogicalExpressionOracle function:
oracle = LogicalExpressionOracle(expression)
Where the expression is the logical expression explained earlier. Then pass the oracle in to the Grover function:
grover = Grover(oracle)
Step 4 : Run the algorithm
Next we just need to run the algorithm using grover.run():
result = grover.run(backend, shots=1024)
Where backend is the quantum device that the algorithm is run on and shots is the number of times we run the algorithm.
Step 5: Obtain the results
Next we need to get the results using the following code:
counts = result['measurement']
How to run the program
Copy and paste the code below in to a python file
Enter your API token in the IBMQ.enable_account('Insert API token here') part
Save and run
Code
from qiskit import IBMQ from qiskit.aqua.algorithms import Grover from qiskit.aqua.components.oracles import LogicalExpressionOracle IBMQ.enable_account('ENTER API KEY HERE') provider = IBMQ.get_provider(hub='ibm-q') backend = provider.get_backend('ibmq_qasm_simulator') expression = '(a & b)& ~(c)' oracle = LogicalExpressionOracle(expression) grover = Grover(oracle) result = grover.run(backend, shots=1024) counts = result['measurement'] print(counts) print('Press any key to close') input()
Output
Output displaying the results for the expression (A AND B) AND (NOT C). Notice how 011 has the most measurements as it satisfies the expression.