Titulo Estágio
Designing and Implementing Quantum Algorithms
Áreas de especialidade
Engenharia de Software
Local do Estágio
DEI-FCTUC
Enquadramento
Quantum Computing (QC) is bound to change the world as we know it. By ex-ploring the properties of quantum theory for computational purposes, we expectto substantially reduce the amount of problems that are nowadays consideredcomputationally intractable. This means that Quantum Computers have thepower of providing solutions for some of the problems of practical interest forwhich a Classical Computer cannot, at least in a timely manner. This is evenmore revolutionary and remarkable given the fact these problems range frommultidisciplinary domains such as Chemistry, Medicine, Routing and Finance.Quantum computation models have originally been studied in the 1980s andalgorithms to explore quantum computing started appearing in the early 1990s,even if back then quantum computational devices were essentially theoretical.Two of the most well known quantum algorithms are Shor’s polynomial-timealgorithm [Shor, 1994] for prime factorization and discrete logarithm and Grover’s algorithm [Grover, 1996] that can efficiently search data in an unstructureddatabase.While the groundbreaking nature of these well known algorithms can not bedenied, a challenge that we face here is that they are not possible to be executedin the near-term. While NISQ hardware implementations (of less than a hundredqubits) have recently been developed, their limitations pose significant challen-ges regarding the development of practical algorithms, the ones we propose totarget. Nevertheless, a number of NISQ algorithms have already been pro-posed, namely the Variational Quantum Eigensolver [Peruzzo et al., 2014] andthe Quantum Approximate Optimization Algorithm [Farhi et al., 2014], whichdemonstrate the feasibility of the approach.In this project, we will analyse, propose and implement data structures that are amenable to be executed in quantum computers. We subscribe to the workof Niklaus Wirth, who in 1976 coined a famous equation in Computer Science -‘Algorithms + Data Structures = Programs’, and in this case we will focus onthe algorithmic counterpart of the equation.
Objetivo
The candidate will join a group of researchers who are doing intensive, foundational work on QC.
The general goal is to design, implement and analyse algorithms that can leverage quantum properties. In concrete, we aim at reaching the following goals:
- The specification of an algorithm amenable for implementation on a quantum computer.
- The implementation and empirical assessment of the proposed algorithm on a state of the art quantum computer.
The development of quantum algorithms is particularly challenging since it requires a combination of skills which include, e.g., quantum mechanics and complexity theory, as well as a deep computer science background.
The outcomes of this project will be made publicly available as open source tool sets that can benefit the entire community.
These artifacts will target multiple platforms that are already available for general-purpose quantum computing such as IBM Qiskit or Google’s Cirq.
Plano de Trabalhos - Semestre 1
1- State of the Art (3 months) [Sept – Nov]
2- Identification of a Quantum Algorithm of choice for the study (2 months) [Nov-Dec]
3- Development of the first experiments towards its implementation (1 month) [Dec]
4- Thesis Proposal Writing (2 months) [Dec – Jan]
Plano de Trabalhos - Semestre 2
5- Going beyond a prototype to a fully mature implementation (2 months) [Feb – Apr]
6- Experimental Tests (1.5 months) [Apr – May]
7- Analysis of results (1,5 months) [May – Jun]
8- Thesis Writing (4 months) [Jan – Jul]
Condições
The eligible student will have at disposal all the necessary computational platforms, tools and devices.
He will work within a research team that is working on related issues.
It might also be possible to ensure funding for the student in the form of a research grant.
Observações
Co-orientador: João Paulo Fernandes (FEUP)(jpaulo@fe.up.pt)
Referências
[Farhi et al., 2014] Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quan-tum approximate optimization algorithm applied to a bounded occurrenceconstraint problem.arXiv: Quantum Physics.
[Grover, 1996] Grover, L. K. (1996). A fast quantum mechanical algorithm fordatabase search. InProceedings of the Twenty-Eighth Annual ACM Sym-posium on Theory of Computing, STOC ’96, page 212–219, New York, NY,USA. Association for Computing Machinery.
[Peruzzo et al., 2014] Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H.,Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., and O’Brien, J. L. (2014). Avariational eigenvalue solver on a photonic quantum processor.Nature Com-munications, 5(1).
[Shor, 1994] Shor, P. (1994). Algorithms for quantum computation: discrete lo-garithms and factoring.Proceedings 35th Annual Symposium on Foundationsof Computer Science, pages 124–134.
Orientador
Luís Macedo
macedo@dei.uc.pt 📩