7 papers
Fast Cliffords When Your Quantum Memory Is Full
Marten Folkertsma, Ian Mertz, Sergii Strelchuk +1
Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in…
Understanding Robust Catalytic Computing
Michal Koucký, Ian Mertz, Sasha Sami
Catalytic computing concerns space bounded computation which starts with memory full of data that have to be restored by the end of the computation. Lossy catalytic computing, defi…
Quantum Catalytic Space
Harry Buhrman, Marten Folkertsma, Ian Mertz +4
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation…
Catalytic Computing and Register Programs Beyond Log-Depth
Yaroslav Alekseev, Yuval Filmus, Ian Mertz +2
In a seminal work, Buhrman et al. (STOC 2014) defined the class of problems solvable in space with an additional catalytic tape of size , which is a tape whose…
Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded s…
Collapsing Catalytic Classes
Michal Koucký, Ian Mertz, Edward Pyne +1
A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be pr…
Fully Characterizing Lossy Catalytic Computation
Marten Folkertsma, Ian Mertz, Florian Speelman +1
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being…