Quantum algorithms and their applications

Project reference: 2119

The paradigm of quantum computers is completely different from the paradigm of classical digital computers. Understanding this paradigm will allow the student to understand, for example, how it is possible that quantum computers are able to solve the problem of exponential complexity in less than exponential time.

Currently, there are rapid developments in this field of quantum computers. The aim of this project is not to deal with all the news in this area, but to give a theoretical basis that will allow the student to understand the potential of quantum computers. For example, the difference between quantum natural parallelism and parallel programming on HPC will be shown.

Thanks to this knowledge, the student will be able not only to understand existing basic quantum algorithms such as Grover’s, Shor’s, Deutsch-Jozsa, estimating Gauss sums, element distinctness problem or quantum algorithm for solving linear systems of equations, but also to optimize their implementation or create their modifications.

Implementation of 8-qbit Grover algorithm. At the top of the image is the oracle function and at the bottom is the Grover diffusion operator. The answer that is sought is code 00101010 (42). This quantum circuit represents only 1 iteration of this algorithm. To achieve the maximum probability (in this case 0.999947) for the correct answer, 12 of these iterations are needed.

Project Mentor: Jiří Tomčala

Project Co-mentor: 

Site Co-ordinator: Karina Pešatová

Participants: Lucia Absalom Bautista, Spyridon-Andreas Siskos

Learning Outcomes:
Understanding the paradigm of quantum computers and their programming. Ability to design a quantum circuit, enabling the solution of problems with exponential complexity in a shorter time.

Student Prerequisites (compulsory):
Knowledge of Linux as the development environment.

Student Prerequisites (desirable):
Knowledge of linear algebra. Experience in Python programming.

Training Materials:
“Quantum Computation and Quantum Information” by Isaac Chuang and Michael Nielsen.
“Quantum Algorithm Implementations for Beginners” by various authors, which can be downloaded from here: https://arxiv.org/pdf/1804.03719.pdf
Etc.

Workplan:

1^st week: quantum bits
2^nd week: single qubit operations
3^rd week: quantum gates
4^th week: Grover’s algorithm
5^th week: element distinctness problem quantum algorithm
6^th week: estimating Gauss sums quantum algorithm
7^th week: Shor’s algorithm
8^th week: solving linear systems of equations quantum algorithm

Final Product Description:
Running the student’s own quantum programs (circuits) on a simulator and then on a real quantum computer.

Adapting the Project: Increasing the Difficulty:
Attempting to create interesting modifications of the discussed algorithms.

Adapting the Project: Decreasing the Difficulty:
Omitting algorithms that are too difficult to understand.

Resources:

Organisation:

IT4Innovations National Supercomputing Center at VSB – Technical University of Ostrava