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

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

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

Shor’s Algorithm — An Implementation in IBM Quantum

# 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

--

--

--

https://www.linkedin.com/in/andisama/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Blue-Green deployments for Sidekiq workers in docker

Python Wrangling for Beginners — Where and How?

About Me — Sunku Ranganath

27 questions guaranteed to improve Lead Qualification and increase Bookings

Poor Quality - Lead Qualification

I Failed My First Mock Tech Interview

PHP Deployment with Deployer to AWS via Bitbucket Pipeline

Learn GoF Design patterns to solve problems in software design

Apply. Engage and make an impact. My experience with Galaxy.

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
Andi Sama

Andi Sama

https://www.linkedin.com/in/andisama/

More from Medium

Simplified: Vectors, Tensor, Spinors and Phasors

Quantum Computing — Learn by Asking (Entanglement)

Math of Two-Qubit Circuits

An Introduction to Grover’s Algorithm