  Shallow quantum circuits feature not only computational advantage over their
classical counterparts but also cutting-edge applications. Storing quantum
information generated by shallow circuits is a fundamental question of both
theoretical and practical importance that remained largely unexplored. In this
work, we show that $N$ copies of an unknown $n$-qubit state generated by a
fixed-depth circuit can be compressed into a hybrid memory of $O(n \log_2 N)$
(qu)bits, which achieves the optimal scaling of memory cost. Our work shows
that the computational complexity of resources can significantly impact the
rate of quantum information processing, offering a unique and unified view of
quantum Shannon theory and quantum computing in the NISQ era.
