BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T121958Z
UID:Seminar-dept-1277@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250708T130000
DTEND:20250708T140000
SUMMARY:School Seminar Series
DESCRIPTION:Sergii Strelchuk: Flexible catalysis and catalytic space: from LOCC reachability to quantum log-space complexity\n\nI will discuss flexible catalysis in quantum information theory—a generalisation of traditional catalysis in which the auxiliary state need not be returned unchanged but may instead be swapped for another element of a predefined catalyst set. For bipartite state transformations under Local Operations and Classical Communication (LOCC), we show that such flexibility enables conversions impossible with any single catalyst from the set.\n\n\n\nIn the second half of the talk I will turn to space complexity and its implications for catalysis. Because qubits are scarce, understanding space-restricted computation is crucial. Catalytic computing, a recent branch of space-bounded complexity, demonstrates that carefully reusing memory can be a powerful resource, particularly for subroutines that incur little or no extra space overhead. Existing notions of quantum catalysis, and the use of “dirty” qubits, are ill-suited to space-bounded algorithms because they either require highly specific catalyst states or irreversibly disturb the borrowed memory.\n\n\n\nFirst, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model. I will conclude by discussing the problem of catalytic transformations as reachability problems.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1277
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR