  While quantum state tomography is notoriously hard, most states hold little
interest to practically-minded tomographers. Given that states and unitaries
appearing in Nature are of bounded gate complexity, it is natural to ask if
efficient learning becomes possible. In this work, we prove that to learn a
state generated by a quantum circuit with $G$ two-qubit gates to a small trace
distance, a sample complexity scaling linearly in $G$ is necessary and
sufficient. We also prove that the optimal query complexity to learn a unitary
generated by $G$ gates to a small average-case error scales linearly in $G$.
While sample-efficient learning can be achieved, we show that under reasonable
cryptographic conjectures, the computational complexity for learning states and
unitaries of gate complexity $G$ must scale exponentially in $G$. We illustrate
how these results establish fundamental limitations on the expressivity of
quantum machine learning models and provide new perspectives on no-free-lunch
theorems in unitary learning. Together, our results answer how the complexity
of learning quantum states and unitaries relate to the complexity of creating
these states and unitaries.
