Truth tables with Grover's Search in Qiskit

Interested in learning how to program quantum computers? Then check out our Qiskit textbook Introduction to Quantum Computing with Qiskit.

Introduction

In our last tutorial we learned how to evaluate logical expressions using Grover’s search. In this tutorial we will explore how to use Grover’s search to instead evaluate truth tables.

A truth table can be defined as a table that shows the output of a function given each combination of a number of inputs.

With a truth table we may want to see what inputs will make the output true. For a small number of inputs this can be fairly straight forward

However if a truth table has a large number of outputs it can become quite difficult to evaluate. However with Grover’s Search we can evaluate the table in only O(√n) time.

Implementation

Grover’s search for truth tables can be implemented very easily in Qiskit with the following steps:

Step 1: Find the bit string for the truth table

The first step is to specify the bit string associated with the truth table as this will be the input for our oracle. For any truth table the bit string is simply the function/output column. For example consider the following truth table:

A B F
0 0 0
0 1 0
1 0 0
1 1 1

Column F is our bit string ie ‘0001’

Another example:

A B F
0 0 1
0 1 1
1 0 1
1 1 0

Here the bit string would be ‘1110’

Rule of thumb is for a truth table consisting of N variables the bit string will be 2^n. For example if we have 4 variables in our truth table the bit string will have a length of 16.

Step 2: Pass the bit string in to the TruthTableOracle function

The second step is to specify the correct oracle. Since we are evaluating truth tables you will need to pass the bit string in to the TruthTableOracle function:

expression = '11000001' # Our bit string  oracle = TruthTableOracle(expression)

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

  1. Enter your API token in the IBMQ.enable_account('Insert API token here') part

  2. Save and run

Code

from qiskit import IBMQ
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import TruthTableOracle

IBMQ.enable_account('ENTER API KEY HERE')
provider = IBMQ.get_provider(hub='ibm-q')

backend = provider.get_backend('ibmq_qasm_simulator')

expression = '11000001'

oracle = TruthTableOracle(expression)

print(oracle)

grover = Grover(oracle)

result = grover.run(backend, shots=1024)
           
counts = result['measurement']

print('\nTruth tables with Grovers Search')
print('--------------------------------\n')
print('Bit string is ', expression)
print('\nResults ',counts)
print('\nPress any key to close')
input()

Output

From the results we can see that the correct inputs are 000, 001, and 111

From the results we can see that the correct inputs are 000, 001, and 111