Research Institutes

https://domino.mpi-inf.mpg.de/internet/events.nsf/0/BFFD9321722F6405C1258951004E357F

Title: Quantum Pseudoentanglement

Abstract: Quantum pseudorandom states are efficiently constructable states which
nevertheless masquerade as Haar-random states to poly-time observers. First
defined by Ji, Liu and Song, such states have found a number of applications
ranging from cryptography to the AdS/CFT correspondence. A fundamental question
is exactly how much entanglement is required to create such states. Haar-random
states, as well as t-designs for t≥2, exhibit near-maximal entanglement. Here we
provide the first construction of pseudorandom states with only polylogarithmic
entanglement entropy across an equipartition of the qubits, which is the minimum
possible. Our construction can be based on any one-way function secure against
quantum attack. We additionally show that the entanglement in our construction
is fully "tunable", in the sense that one can have pseudorandom states with
entanglement Θ(f(n)) for any desired function ω(logn)≤f(n)≤O(n). More
fundamentally, our work calls into question to what extent entanglement is a
"feelable" quantity of quantum systems. Inspired by recent work of Gheorghiu and
Hoban, we define a new notion which we call "pseudoentanglement", which are
ensembles of efficiently constructable quantum states which hide their
entanglement entropy. We show such states exist in the strongest form possible
while simultaneously being pseudorandom states. We also describe diverse
applications of our result from entanglement distillation to property testing to
quantum gravity.

Based on joint work with Bill Fefferman, Soumik Ghosh, Umesh Vazirani, and Zixin
Zhou, arXiv:2211.00747

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

Bhaskar Ray Chaudhury (University of Illinois Urbana-Champaign, USA)

https://uni-saarland.us20.list-manage.com/track/click?u=997406072676c8ace8a944a4b&id=d3d90b74e0&e=55e0ebfed1

https://domino.mpi-inf.mpg.de/internet/events.nsf/0/0B8E2D36FB936D00C125896300394A26

https://domino.mpi-inf.mpg.de/internet/events.nsf/0/AFD1558F6C7EA09FC125895E004A2C54

am Donnerstag, 9. März 2023, um 12:30 Uhr in Gebäude E2 4, HS IV

Titel: “Classification and homological invariants of compact quantum
groups of combinatorial type“

Die Arbeit wurde von Prof. Dr. Moritz Weber betreut.

Abstract:
Compact quantum groups can be found by solving certain combinatorics
problems, as first shown by Banica and Speicher. In particular, Tarrago
and Weber proved that any system of decorated partitions of finite sets
which is closed under reflection and two kinds of concatenation gives
rise to a quantum subgroup of the free unitary quantum group. The effort
to describe all these quantum relatives of the classical matrix groups
has advanced to the point where only so-called hyperoctahedral ones
remain to be found, the most plentiful and most difficult examples.
Classifying them in part, a family of non-hyperoctahedral quantum groups
can be recognized by observing that certain colored orders induced by a
*-betweenness relation between the blocks of the partitions are stable
under reflection and concatenation.
While constructions as the one described produce numerous examples of
quantum groups, little is known about which of those are actually new
and not just known ones in disguise. For instance, it can be proved that
any such quantum group interpolating the unitary group and the free
unitary quantum group can be written as a quotient of a wreath graph
product of one of the two. One way of making distinctions is to study
quantum group invariants, such as cohomology. For example, it is
possible to compute the first order with trivial coefficients for the
discrete duals of all of Tarrago and Weber’s quantum groups, even the
ones not yet classified.
Finally, the kind of construction sketched above, giving rise to quantum
groups of combinatorial type, can be understood in the abstract terms of
categories of generalized relations with respect to orthogonal
factorization systems. While much remains to be investigated further,
one can prove in this framework theorems which hold for all reasonably
well-behaved constructions.

am Donnerstag 09. März 2023 um 14:00 Uhr in Gebäude E1 4, MPII, Raum
0.24

Titel: “On a Notion of Abduction and Relevance for First-Order Logic
Clause Sets“

Die Arbeit wurde von Prof. Dr. Christoph Weidenbach und Dr. Sophie
Tourret betreut.

Abstract:
I propose techniques to help explain entailment and non-entailment in
first-order logic. For entailment, I classify clauses necessary for any
possible deduction (syntactically relevant), usable for some deduction
(syntactically semi-relevant), or unusable (syntactically irrelevant)
along with a semantic characterization via conflict literals
(contradictory simple facts). This offers a novel insight beyond the
existing notion of minimal unsatisfiable set. The need to test if a
clause is syntactically semi-relevant leads to a generalization of the
completeness result of a well-known resolution strategy: resolution with
the set-of-support (SOS) strategy is refutationally complete on a
clause set N and SOS M if and only if there is a resolution refutation
from N ∪ M using a clause in M. For non-entailment, abductive reasoning
helps find extensions of a knowledge base to obtain an entailment of
some missing consequence. I focus on EL TBox abduction that is
lightweight but prevalent in practice. The solution space can be huge
so, to help sort the chaff from the grain, I introduce
connection-minimality, a criterion such that accepted hypotheses always
immediately relate the observation to the given axioms. I show that such
hypotheses are computable using prime implicate-based abduction in
first-order logic. I evaluate this notion on ontologies from the medical
domain using an implementation with SPASS as a prime implicate
generation engine.

am Montag, 13. März 2023 um 10:00 Uhr in Gebäude E2 4, HS IV

Titel: “Monte-Carlo methods for backwardstochastic differential equa-tions:
Segment-wise dynamic programming and fast rates for lower bounds“

Die Arbeit wurde von Prof. Dr. Christian Bender betreut.

Abstract:
In this talk we cover two different algorithms using Monte-Carlo methods for solving backward stochastic differential equations.

We first present a new algorithm where the backward stochastic differential equation is discretized to a dynamic programming equation using a multi-step forward approach on segments of the time grid. Appearing conditional expec-tations are computed via least squares regression on function spaces. We op-timize the length of the segments in dependence on the dimension and smoothness of the backward stochastic differential equation and compute the complexity needed to achieve a desired accuracy in the limit as the number of time points in the discretization goes to infinity.

Additionally we briefly cover an algorithm for the construction of lower bounds for the solution at time zero. This algorithm uses a pre-computed ap-proximate solution of the BSDE to sample a control process which are then used to derive the lower bound for the solution.

https://infolab.cs.uni-saarland.de/2023/03/08/astropi-programmieren-fuer-die-iss-2/

https://uni-saarland.us20.list-manage.com/track/click?u=997406072676c8ace8a944a4b&id=1a6cb44401&e=55e0ebfed1

https://www.uni-saarland.de/aktuell/studieninfotage-vorstellung-der-mint-studiengaenge-26275.html

https://stadtbibliothek.saarbruecken.de/veranstaltungen/veranstaltungen/veranstaltungs_detailseite/event-62389d18d5900

https://informatikdidaktik.cs.uni-saarland.de/2023/01/26/5-tag-des-informatikunterrichts/