  Complexity is often invoked alongside size and mass as a characteristic of
macroscopic quantum objects. In 2004, Aaronson introduced the \textit{tree
size} (TS) as a computable measure of complexity and studied its basic
properties. In this paper, we improve and expand on those initial results. In
particular, we give explicit characterizations of a family of states with
superpolynomial complexity $n^{\Omega(\log n)}= \mathrm{TS} =O(\sqrt{n}!)$ in
the number of qubits $n$; and we show that any matrix-product state whose
tensors are of dimension $D\times D$ has polynomial complexity
$\mathrm{TS}=O(n^{\log_2 2D})$.

Quantum Physics