In this talk, I'll motivate studying the complexity of quantum states and transformations. I'll discuss how this general study is related to a seminal theoretical computer science concept: search vs. decision. I'll show how to construct a form of search-to-decision reductions for QMA problems and show why it is unlikely that we can do (much) better. I'll conclude by discussing a parametrized notion of QMA and the notion of QMA solutions in this context.
This talk will be based on a work with Irani, Natarajan, Rao and Yuen (https://arxiv.org/abs/2111.02999) and a work with Arunachalam, Bravyi, and O'Gorman (https://arxiv.org/abs/2202.08119).
