Distributed inner product estimation (DIPE) is a fundamental task in quantum information, aiming to estimate the inner product between two unknown quantum states prepared on distributed quantum platforms. Existing rigorous sample complexity analyses are limited to unitary 4-designs, which pose significant practical challenges for near-term quantum devices. This work addresses this challenge by exploring DIPE with structured random circuits. We first establish that DIPE with an arbitrary unitary 2-design ensemble achieves an average sample complexity of \({\mathcal{O}}(\sqrt{{2}^{n}})\), where n is the number of qubits. We then analyze ensembles below unitary 2-designs—specifically, the brickwork and local unitary 2-design ensembles—demonstrating average sample complexities of \({\mathcal{O}}(\sqrt{2.1{8}^{n}})\) and \({\mathcal{O}}(\sqrt{2.{5}^{n}})\), respectively. Furthermore, we analyze the state-dependent sample complexity. For brickwork ensembles, we develop a tensor network approach to compute the asymptotic state-dependent sample complexity, showing that it converges to \({\mathcal{O}}(\sqrt{2.1{8}^{n}})\) as the circuit depth increases. Remarkably, we find that DIPE with the global Clifford ensemble requires \(\Theta (\sqrt{{2}^{n}})\) copies, matching the performance of unitary 4-designs. For both local and global Clifford ensembles, we find that the efficiency can be further enhanced by the nonstabilizerness of states. Additionally, for approximate unitary 4-designs, the performance exponentially approaches that of exact unitary 4-designs as the circuit depth increases. Our results provide theoretically guaranteed methods for implementing DIPE with experimentally feasible unitary ensembles.
