Flexible catalysis and catalytic space: from LOCC reachability to quantum log-space complexity

8^th July 2025, 13:00 Ashton Lecture Theatre
Sergii Strelchuk
University of Oxford

Abstract

I 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.

In 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.

First, 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.

Biography

Dr. Sergii Strelchuk is an Associate Professor in the Department of Computer Science at the University of Oxford and a Tutorial Fellow at Jesus College. His research focuses on Quantum Computing and Quantum Information Theory.

Prior to his appointment at Oxford, Dr. Strelchuk was a Royal Society University Research Fellow from January 2020 to December 2024 at the Department of Applied Mathematics and Theoretical Physics, University of Cambridge.

He held Leverhulme Early Career Fellowship and a John and Delia Agar Junior Research Fellowship at Sidney Sussex College.
Dr. Strelchuk earned his PhD in Quantum Information Theory from the University of Cambridge in 2013, where he was a member of Trinity College and the Centre for Quantum Information and Foundations.

Additional Materials

• https://arxiv.org/abs/2506.16324