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

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."
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."
  • 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.

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

# 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
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
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("")
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
backend = BasicAer.get_backend('qasm_simulator')
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

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.

Peter Shor, a Professor in Applied Mathematics at MIT (source: nature.com).
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
backend = Aer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots = 1024)
my_shor = Shor(N=21, a=2, quantum_instance=quantum_instance)
Shor.run(my_shor)
{'factors': [[3, 7]], 'total_counts': 137, 'successful_counts': 29}
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).

References

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store