On the Need for (Quantum) Memory with Short Outputs

Zihan Hao, Zikuan Huang, Qipeng Liu

In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially lar…