Qubit, An Intuition #6 — Two Famous Quantum Algorithms, Shor’s and Grover Algorithms

The beauty of Quantum Mechanics for Quantum Computation, featuring IBM Quantum

Andi Sama — CIO, Sinergi Wahana Gemilang with Cahyati S. Sangaji

TL;DR; 
- Shor's Quantum Factoring and Grover's Quantum Search algorithms.
- Implementation of Shor's and Grover's algoritms in IBM Quantum.
- The source code (in Python) for the sample use cases (party's invitation using Grover's algorithm) -- to be available on github
- This is the final article in the "Qubit, An Intuition" series. Previous articles (since mid 2021) have discussed "First Baby Steps in Exploring the Quantum World", "Inner Product, Outer Product, and Tensor Product", "Quantum Measurement", "Unitary Matrices", and "Quantum Circuit and Reversible Transformation."

For an introductory helicopter view of the overall six articles in the series, please visit this link “Embarking on a Journey to Quantum Computing — Without Physics Degree.”

Finally, we have come to the last article in the “Qubit, An Intuition” series. This final article discusses two famous quantum algorithms, namely Shor’s and Grover’s algorithms, with their implementation examples in IBM Quantum.

Please refer to the previous articles:
“Qubit, An Intuition #1 — First Baby Steps in Exploring the Quantum World” for a discussion on a single qubit as a computing unit for quantum computation.
- "Qubit, An Intuition #2 - Inner Product, Outer Product, and Tensor Product" for a discussion on two-qubits operations.
- "Qubit, An Intuition #3 - Quantum Measurement, Full and Partial Qubits" for examples on full and partial quantum measurements.
- "Qubit, An Intuition #4 - Unitary Matrices for Quantum Computation."
- "Qubit, An Intuition #5 - Quantum Circuit and Reversible Transformation."

When we build quantum-based applications, a typical approach is to utilize a hybrid classical-quantum. A classical computer does part of the processing (like preparing the quantum circuit and performing post-processing). The quantum computer does another part of the processing (run the quantum circuit consisting of the quantum algorithm by exploiting inherent parallelism through superposition, entanglement, and interference).

Shor’s algorithm is the most famous one to factor large prime numbers with O(log N), a polynomial-time. Grover’s search algorithm can do a non-sorted data search with quadratic-time (O(sqrt(N))) over a classical algorithm with O(N) time complexity.

The implementations with IBM Quantum in this article use Qiskit Aqua (Algorithm for Quantum Applications), the higher-level implementation of Qiskit without going through the detailed steps of each algorithm.

Qiskit (Quantum Information Science Kit) is an open-source quantum development framework. Qiskit has 4 elements: Terra, Aer, Ignis, and Aqua (Qiskit, 2021c):

• Terra provides the base for composing quantum programs at the level of circuits and pulses, optimizing them for the constraints of a particular device, and managing the execution of batches of experiments on remote-access devices.
• Aer helps us understand the limits of classical processors by demonstrating to what extent they can mimic quantum computation.
• Ignis is dedicated to fighting noise and errors and to forging a new path. This includes better characterization of errors, improving gates, and computing in the presence of noise.
• Aqua is where algorithms for quantum computers are built to make quantum computing live up to its expectations by having to solve real-world applications.

Let’s discuss Grover’s algorithm first, then Shor’s algorithm.

Grover’s Algorithm — Search

In a classical search algorithm for unsorted data (such as a list of numbers), the time complexity of searching an item within N items is O(N). This is a worst-case scenario if the element is at the very end of the list.

The time complexity comparison graph of classical search algorithm vs. Grover’s quantum algorithm for unsorted data (The Graph is created by an online tool at https://www.desmos.com/calculator). Grover’s search quantum algorithm promises a quadratic time over the classical algorithm.

We can reduce the time complexity O(log(N)) If the data is sorted. Note that sorting the data needs additional time that we can not ignore, especially with large N.

In the Big O notation, the time complexity reduction in unstructured data search for Grover’s Quantum Search algorithm is further reduced from O(N) to a square root of N. This is a quadratic-time.

Grover’s algorithm (introduced in 1996) is the second most famous quantum algorithm, after the most famous one: Shor’s algorithm.

Lov Kumar Grover, A Computer Scientist (source: dotquantum.io).

Grover’s Algorithm: Party’s Invitation Guest List — An Implementation in IBM Quantum

We will now look into a use-case for Grover's algorithm for selecting the best possible combination of invitees to a Party’s invitation. We determine who will be allowed on the invitee list, ranked by the best combination of invitees, given constraints. This is a satisfiability problem.

Given a list of people for Party’s Invitation list, we will find the best combinations of people to be invited, given constraints.

We use both backend quantum computers: the IBM quantum simulator: qasm_simulator and the real IBM quantum computer: ibmq_16_melbourne. The quantum computers are accessed through the IBM qiskit aqua quantum programming framework with Python programming language.

The complete code is in GitHub, as listed in the TL;DR; section at the beginning of this article.

First, load a few libraries (qiskit and general libraries) for our use case:

# IBM qiskit related 
from qiskit import BasicAer
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle
from qiskit.tools.visualization import plot_histogram
from qiskit import IBMQ
# string manipulation
import re, string

Then, define the invitation list to process, with constraints: e.g., Lia & Martin can not be invited together.

log_expr = '((Ben & Lia) | (Martin & Mia) | (Ben & Feyling) | (Jack & Mia)) & ~(Lia & Martin)'
sorted_words = sort_string(log_expr, reversed=True)
print("Potential invitees:", sorted_words)
potential_invitees = sorted_words

Running the Algorithm on an IBM Quantum Computer

In the end, we can run the algorithm on a quantum computer. Select the top 3 list of the best possible combinations of people to be invited. First, we show the sorted potential invitees, and then we select the potential invitee if the corresponding index of qubit measurement is “1”. Finally, we build the invitation list.

algorithm = Grover(LogicalExpressionOracle(log_expr))
IBMQ.load_account()
provider = IBMQ.get_provider(group='open', project='main')
backend = provider.get_backend('ibmq_16_melbourne')
result = algorithm.run(backend)
print("Potential invitees:", sorted_words)
max = len(top_list)-1
num_qubits = len(top_list[max][0])
for i in range(3):
    k=1
    print("Top 3 best invitation list (", i+1, "):", top_list[max-i][0])
    for j in range(num_qubits):
        if top_list[max-i][0][j] == "1":
            print("", k, potential_invitees[j])
            k=k+1
    print("")

The result:

Potential invitees: ['Mia', 'Martin', 'Lia', 'Jack', 'Feyling', 'Ben']
Top 3 best invitation list ( 1 ): 100101
 1 Mia
 2 Jack
 3 Ben

Top 3 best invitation list ( 2 ): 000000

Top 3 best invitation list ( 3 ): 010000
 1 Martin

And, the plot of the result in a histogram ‘backend = ibmq_16_melbourne’:

Running the Algorithm on a Quantum Simulator

Alternatively, we can change the backend to run our algorithm in a quantum simulator.

backend = BasicAer.get_backend('qasm_simulator')

The result:

Potential invitees: ['Mia', 'Martin', 'Lia', 'Jack', 'Feyling', 'Ben']
Top 3 best invitation list ( 1 ): 110001
 1 Mia
 2 Martin
 3 Ben

Top 3 best invitation list ( 2 ): 101001
 1 Mia
 2 Lia
 3 Ben

Top 3 best invitation list ( 3 ): 001011
 1 Lia
 2 Feyling
 3 Ben

And, the plot of the result in a histogram for ‘backend = qasm_simulator’:

Shor’s Algorithm — Factoring Large Integer

Current cryptography RSA-based implementations (such as protecting our typical payment transactions on the Internet) rely heavily on the time complexity of factoring a product of two large prime numbers. It could take many years for the classical computer to find the prime factors which are considered safe.

Following Shor’s algorithm (in 1995) that promises a polynomial-time to factor a multiplied product of two large prime numbers, all that was suddenly changed. As of April 2021 (Craig Gidney and Martin Ekera, 2021), there is an algorithm to break 2048-bits RSA integers in 8 hours if we have 20 million qubits now (provided the hardware with a sufficient number of qubits is available). Could it be by the next decade after 2030? Well, time will tell.

Peter Shor, a Professor in Applied Mathematics at MIT (source: nature.com).

Shor’s algorithm has been the most famous quantum algorithm so far and still be the main quantum algorithm inspiring and accelerating the development of quantum computers and surrounding supporting infrastructures & applications since then.

In the Big O notation, Shor’s quantum factoring algorithm reduces the time complexity for large prime number factoring from the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time (Wikipedia, 2021).

From the classical factoring algorithm:

To the Shor’s quantum factoring algorithm:

The time complexity comparison graph of classical factoring algorithm vs. Shor’s quantum algorithm (The Graph is created by an online tool at https://www.desmos.com/calculator). Shor’s search quantum algorithm promises a polynomial-time.

Shor’s Algorithm — An Implementation in IBM Quantum

First, load a few libraries (qiskit and general libraries) for our use case:

# qiskit related
from qiskit.aqua.algorithms import Shor
from qiskit.aqua import QuantumInstance
from qiskit import QuantumCircuit, Aer, execute
from qiskit.tools.visualization import plot_histogram
# general libraries
import numpy as np

Running the Algorithm on an IBM Quantum Simulator

Then define a simple number to factor, N=21:

backend = Aer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots = 1024)
my_shor = Shor(N=21, a=2, quantum_instance=quantum_instance)

Then we run Shor’s algorithm:

Shor.run(my_shor)

The result:

{'factors': [[3, 7]], 'total_counts': 137, 'successful_counts': 29}

When we try to factor a large number (using a 32-qubits ‘qasm_simulator’ quantum simulator) that is not supported by the quantum computer (as the current quantum computers have a limited number of qubits), the following message occurs. e.g., when we try to factor N=61267, producing the two prime numbers: 197 and 311.

Simulation failed and returned the following error message:
ERROR:  [Experiment 0] QasmSimulator: Insufficient memory for 66-qubit circuit using "statevector" method. You could try using the "matrix_product_state" or "extended_stabilizer" method instead.

Availability of IBM Quantum Computers

For exploration purposes, to some extent, using the IBM Quantum Experience on IBM Cloud is free of charge, from 1-qubit to 15-qubits (as of July 2021).

To be eligible to access higher capacity quantum computers with more qubits or better job priority in the queue when processing our submitted quantum circuits, we can arrange to have a special agreement through IBM Q Network at a certain annual cost. By 2020, IBM has a quantum computer with 65 qubits and intends to launch 1,121 qubits by 2023 and millions of qubits later on.

References

• Advanced Maths, 2021, “Quantum Computing: Quantum Circuit Example.”
• Andi Sama, Cahyati S. Sangaji, 2021a, “Qubit, An Intuition #1 — First Baby Steps in Exploring the Quantum World.”
• Andi Sama, Cahyati S. Sangaji, 2021b, “Qubit, An Intuition #2 — Inner Product, Outer Product, and Tensor Product.”
• Andi Sama, Cahyati S. Sangaji, 2021c, “Qubit, An Intuition #3 — Quantum Measurement.”
• Andi Sama, Cahyati S. Sangaji, 2021d, “Qubit, An Intuition #4 — Unitary Matrices for Quantum Computation.”
• Andi Sama, Cahyati S. Sangaji, 2021e, “Qubit, An Intuition #5 — Quantum Circuit and Reversible Transformation.”
• Andi Sama, 2021, “My Journey to Quantum Computing.”
• Craig Gidney and Martin Ekera, 2021, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. “
• edX Quantum Computing, 2021, “edX Introduction to Grover’s Algorithm,” University of Chicago.
• IBM, 2021, “IBM Quantum on IBM Cloud.”
• Jin-Sung Kim et al., 2020, “Dinner Party using Grover’s Algorithm -Programming on Quantum Computers — Coding with Qiskit S2E5”, https://www.youtube.com/watch?v=ePr2MgQkqL0, IBM, November 2020.
• Peter Shor, 2021, “The Story of Shor’s Algorithm, Straight From the Source,” MIT.
• Qiskit, 2021a, “Qiskit: Grover Algorithm.”
• Qiskit, 2021b, “Qiskit Aqua: Grover Algorithm.”
• Qiskit, 2021c, “The Qiskit Elements.”
• Wikipedia, 2021, “Shor’s algorithm.”