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

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

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

Grover’s Algorithm — Search

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

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

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