HASLab

10/26/2016

By Carlos Tavares, HASLab, INESC TEC & University of Minho.

Abstract. In the eighties, the discovery that the exploitation of the strange phenomena present in quantum physics could lead to ground- breaking improvements in computational capacity, generated a lot of enthusiasm and research efforts both from industry and research communities. The most visible result of such efforts is the Shor algorithm, which can potentially break RSA cryptography and put in jeopardy most of the security mechanisms used in modern information systems. However, contrary to the general belief, it does end here. Since Shor’s early days of quantum computation, a myriad of computer models, algorithms and techniques have been developed, exploring quantum phenomena in a diversity of ways and successfully expanding the realm of applications of quantum computation, to search, machine learning and the simulation of large quantum physical systems. We aim at briefly introduce such techniques, algorithms and applications, while discussing their semantics and complexity limits.

Keywords. Quantum computation, Quantum algorithms, Semantics, Complexity.

About the speaker. Carlos Tavares is currently a PhD Student at the MAP-i Doctoral Programme under the supervision of Prof. Luis Soares Barbosa, and a researcher at HASLab, INESC TEC. He obtained his MSc degree in Informatics Engineering from University of Porto in 2008, working in the area of ubiquitous computing. His excellent performance within the two INESC TEC’s research projects caalyx.eu and ecaalyx.eu, in the area of ambient assisted living, lead to several publications, among which one was highly cited (around 600 citations). Carlos also worked as a software engineer in the area of multimedia industry, where he played several roles (as technical product lead, leading product definition and development, etc.) and participated in the standardisation efforts of the Society of Motion Picture and Television Engineers. Carlos is currently working on his thesis with the title “Foundations for quantum algorithms”, where he aims at finding appropriate foundational mathematical tools and methodologies to model quantum algorithms and analyse their validity and complexity. His main research interests are quantum algorithms, semantics, complexity, formal methods and computational phenomena in nature.