Computer Science Honours Project

0-1 Knapsack Problem

Summary

The purpose of this article is to analyze the 0/1 Knapsack Problem and explore possible quantum algorithms for its computation on a quantum computer. The Knapsack problem is an interesting computer science problem where one has to maximize the total value of items in a knapsack of known capacity when given a list of items to select from. This article shows that a modified Grover’s search algorithm and the Quantum approximate optimization algorithm (QAOA) that can be used in exploring the creation a Quantum algorithm for the 0/1 Knapsack Problem.

SHOR'S ALGORITHM AND QUANTUM FOURIER TRANSFORM (QFT)

THE IMPORTANCE OF FACTORIZATION

The integer factorization problem is about finding two factors N1 and N2 which when multiplied gives the number N (N, N1, N2 > 1) [1]. When N1 and N2 are primes, this becomes especially hard. The problem is useful in the scientific community. The public and private key of the RSA cryptosystem are modern implementations of integer factorization problem with primes [2]. There is no known classical polynomial-time algorithm currently for this problem [1]. Currently, integers with 1000 or more bits are impossible to factor using known algorithms and classical hardware. Quantum computing is believed to have the potential to change this. Meanwhile, Shor’s algorithm is a breakthrough for this problem, factoring small numbers at time O(n^3logn) [1].

1. Review of paper “Simulating a perceptron on a quantum computer” by Schulda et al.

2. Change of direction for project.

GROVER'S ALGORITHM

more background information Quantum states (|0⟩, |1⟩, |+⟩, |-⟩) can be represented as a superposition. |ψ⟩= α|0⟩+ β|1⟩

|α|^2+ |β|^2=1

α=√(1-p,) β=e^jφ √p, 0≤p≤1,0≤φ<2π

|ψ⟩=√(1-p)|0⟩+ e^jφ √p,|1⟩

e^jφ is the phase

The phase can be used to offset the qubit. There are different gates we can use to do the offsets (T, S, Z etc.)

A phase change example can be found here. https://quantum-computing.ibm.com/composer/d065727b7bdddc3f658e2ad8badeb1ba.

Grover's Algorithm

Grover's algorithm shows the exponential advantage of a quantum computer. It is a search algorithm that provides a huge improvement to a regular classical sorting algorithm. This is because Quantum Mechanics systems can be in a state of superposition and algorithms can simultaneously examine multiple states. A search for an item from a random list of n items can be obtained in O(√n)steps.

WEEK 5

1. How to sum two numbers using a quantum processor

2. The structure of Quantum algorithms. How different are they from classical ones?

WEEK 3-4

INTRODUCTION TO QUANTUM COMPUTING

(Using the IBMQ Environment (https://quantum-computing.ibm.com))

Learning to build or program a quantum circuit requires the following knowledge

Qubit – A qubit (or quantum bit) is the quantum-mechanical analog of a classical bit. It has two basis states: |1⟩ and |0⟩ and can be in state |1⟩ or |0⟩ in a linear combination of both.

WEEK 2

REVIEW OF ARTIFICIAL NEURAL NETWORKS

Artificial neural networks (ANN) hold the key to new technologies like driverless cars and voice control. It stems from bio-inspired computing. ANN is an information processing model that is inspired by the way the biological nervous system such as the brain processes information. It is composed of highly interconnected neurons that are processing elements. These elements work together to solve a specific problem.

WEEK 1

PROJECT INTRODUCTION