Memory compression, quantum walks, and limits to quantum speed-ups for various problems

Sala 6.3.27, Ciências ULisboa (com transmissão via Zoom)
Banner do evento

Por Bruno Loff (Faculdade de Ciências, Universidade do Porto).

The talk is on two recent works with Harry Buhrman, Subhasree Patro, and Florian Speelman (CWI). The first is as follows.
In the classical RAM, any algorithm that uses M memory cells so that, at any point in time, only m out of M cells will be non-zero, may be "compressed” into an algorithm using only m log M memory and running in almost the same time. We may do so by simulating the memory using, e.g., a hash table. In our work, we show an analogous result for quantum algorithms equipped with quantum random-access gates, i.e., for a Quantum Random- Access Machine (QRAM).
The second work pertains to quantum reductions. A reduction from a problem A to a problem B is an algorithm that uses a subroutine for solving problem B in order to solve problem A. If such a reduction from A to B exists, then assuming that A is hard we must conclude that B is hard.
In the second work I will mention in this talk, we singled out a particular problem, the 3SUM problem, and conjectured that it cannot be solved in sublinear quantum time. From this conjecture, we were able to show the hardness of many different problems (many different Bs). This proof, which was quite sophisticated when the paper originally came out, was drastically simplified by the use of the first, later work.
The talk will be broad-scope and intended for a general computer science audience.

Short Bio: Bruno Loff did MSc with José Felix Costa at IST, and was part of CMAF (now CMAFio) at the time. He then moved to Amsterdam to do his PhD with Harry Buhrman at the Centrum voor Wiskunde en Informatica (Center for Mathematics and Informatics, CWI), which he defended in 2014. He was a postdoctoral researcher at Charles University, in Prague, from 2015-2016, and at the Faculty of Sciences at the University of Porto, 2017-2020. Since March 2020, he has worked as an assistant professor at the Department of Computer Science.

Transmissão via Zoom.

LASIGE Computer Science and Engineering Research Centre

Ação de formação para docentes, por Carlos Seco.

Título/data do evento e logótipos das entidades organizadoras

The program will consist of plenary lectures, oral, flash and poster communications, and a round table about “Science beyond academia: entrepreneurship” - registration is mandatory but free of charge!

This course offers an overview of the different ways to measure biodiversity, and provides tips for the stratification of primary biodiversity data and the construction of variables that describe its various facets. It also includes an in-depth review of the different types of data used to measure biodiversity and their problems and limitations.

The goal of this course is to provide participants with current and practical knowledge on urban ecology, including its ecological and social aspects.

Logótipo do programa e fotografias de jovens investigadores

Candidata-te até 23 de junho e vem investigar connosco!

Logótipo do evento

The most important international scientific meeting on the theory and applications of stochastic processes.

Placa de circuito

4.ª edição do Prémio de Inovação IN3+, com candidaturas até 31 de julho de 2023.

Sediment continuum: applying an integrated management approach.

Vista aérea da Estação Experimental de Moluscicultura de Tavira (EEMT)

EDUCOAST Summer School 2023, com candidaturas até 07 de junho de 2023.

RUTTER training school - new deadline for registration: 15 May 2023.

Título, data e localização do evento

The EU PVSEC is the largest international Conference for Photovoltaic research, technologies and applications and at the same time a PV Industry Exhibition, where specialized PV Industry presents technologies, innovations and new concepts in the upstream PV sector.