Quantum Qomrades: Catalysts in Resource Theories and Memories in Dynamic Programming

Abstract

Quantum information theory explores the limits of manipulating quantum states. While auxiliary systems often enhance information processing, a systematic explanation for their power has been lacking. This thesis addresses this gap by investigating the underlying sources of strength in using auxiliary systems. We then apply these insights to practical problems in quantum computing and devise an algorithmic paradigm leveraging auxiliary systems. The first part examines catalysts -- auxiliary systems that remain unaltered -- and identifies three advantages: a memory effect, the ability to fine-tune catalyst states, and their role as seed states for resource distribution. The second part presents a strategy for solving recursive problems in quantum algorithms by employing auxiliary states as memories, achieving an exponential reduction in circuit depth at the cost of increased width. The findings in this thesis would facilitate future research into fundamental problems like resource interconversion and practical ones like optimal quantum circuit synthesis.