Theory Seminar: Putting Idle Qubits to Work: Catalytic Techniques in Quantum Space

Dr. Marten Folkertsma
QuSoft / University of Amsterdam
QIC Seminar, at the Lecture Hall
Tuesday, September 29, 11:30 CET 

Can idle qubits be put to work? Quantum catalytic computation is a new model of computation built to answer this question. It draws on recent progress in classical catalytic algorithms. These algorithms may borrow extra memory that already holds data, as long as they restore it by the end of the computation. This idea has proved especially useful for subroutines, and it led to breakthroughs such as Ryan Williams' simulation of any time-$T$ computation in $O(\sqrt{T \log T})$ space. I first introduce the quantum catalytic model and compare it with the classical setting. I then explain how catalytic techniques let us reuse qubits that already hold information. For certain quantum algorithms, we show that clean workspace can be replaced by catalytic space. Qubits that would normally be off-limits because they store data can be borrowed and then perfectly restored. In some settings, this greatly reduces the extra quantum memory needed. I end with several applications in which idle qubits replace clean ancillas.