Research Institutes

https://www.uni-saarland.de/page/quantum-information.html

One of the major challenges in computer science is to establish lower bounds on
the resources, usually time, that are needed to solve computational problems.
This holds in particular for computational problems that appear in practise.

One way towards dealing with this situation is the study of fine-grained
complexity where we use special reductions to prove time lower bounds for many
diverse problems based on the conjectured hardness of some key problems. For
example, computing the edit distance between two strings, a problem that has a
practical interest when determining the genetic distance between species based
on their DNA, has an algorithm that takes O(n^2) time. Using a fine-grained
reduction it can be shown that faster algorithms for edit distance also imply a
faster algorithm for the Boolean Satisfiability (SAT) problem (that is believed
to not exist). This is evidence that the current edit distance algorithms are
optimal. Another problem, besides SAT, that is used as a basis for these
reductions is the 3SUM problem.

The situation in the quantum regime is no better; almost all known lower bounds
for quantum algorithms are defined in terms of query complexity, which doesn’t
help much for problems for which the best-known algorithms take super-linear
time. Therefore, employing fine-grained reductions in the quantum setting seems
a natural way forward. However, translating the classical fine-grained
reductions directly into the quantum regime is not always possible for various
reasons. In this talk, I will present some recent results in which we circumvent
these challenges and prove quantum time lower bounds for some problems in BQP
conditioned on the conjectured quantum hardness of for example SAT (and its
variants) the 3SUM problem, and the All Pairs Shortest Path (APSP) problem.

One consequence of our work is that many computational problems have at most a
quadratic quantum speedup and often even less. In practise, this speedup is
countered by the slowdown quantum computers incur due to error-correction and
fault tolerant computation, which means that for these tasks quantum advantage
only kicks in for very large inputs. This in turn means that they require many
logical qubits which will not be available in the foreseeable future.

This is based on joint work with Koen Leijnse, Bruno Loff, Subhasree Patro ,and
Florian Speelman.

Location https://zoom.us/j/94577321297?pwd=N3l5K1ZtZ3E1aytnWlBkL1FUazNXZz09
Meeting ID 945 7732 1297
Passcode 205903

Host: Kurt Mehlhorn (MPI-INF).

Information about the series and recordings of previous talks can be found at
https://www.mpi-inf.mpg.de/departments/algorithms-complexity/quantum-lecture-series

Abstract: All living beings try to save effort, and humans are no exception. In this talk I will shows how we save time and energy during communication by making efficient choices in grammar, lexicon and phonology. I present a synthesis of theoretical ideas and empirical evidence demonstrating that language is designed to be as efficient as possible, as a system of communication. My framework, which is based on three general pragmatic principles, accounts for the diverse manifestations of communicative efficiency across a different languages and relies on typological, corpus-based and experimental evidence.

Join Zoom Meeting
https://us06web.zoom.us/j/82326276868?pwd=bVptN1QwMUt0SkdjcExCakZjaThkdz09

https://www.uni-saarland.de/page/quantum-information.html

https://www.uni-saarland.de/aktuell/ringvorlesung-going-digital-1-1-1-1-1-25838.html

https://jurix2022.rechtsinformatik.saarland/

https://jurix2022.rechtsinformatik.saarland/

https://jurix2022.rechtsinformatik.saarland/

https://www.uni-saarland.de/aktuell/ringvorlesung-going-digital-1-1-1-1-1-1-25839.html