Classically, the sample complexity \(m\)  for reconstructing \(\rho ^\star \in \mathbb {C}^{d \times d}\)  is \(O(d^2),\)  where \(d\)  itself grows exponentially with \(n\) .
To address such large sample complexity requirements, we use low-rankness as prior, as many lab-constructed density matrices have low-rank structure, including the maximally-entangled Greenberger-Horne-Zeilinger (GHZ) state [1]}.
While the low-rank constraint is non-convex, it provides a significant reduction in the sample complexity. Under appropriate assumptions,
a rank-\(r\)  density matrix can be reconstructed with \(m = O(r \cdot d \cdot \text{poly} \log (d))\)  measurements,
instead of \(m = O(d^2)\) [2]}.
