Quantum Advantage via Efficient Postprocessing on Qudit Classical Shadow Tomography.

Abstract

Computing inner products of the form tr(AB), where A is a d-dimensional density matrix [with tr(A)=1, A≥0] and B is a bounded-norm observable [Hermitian with tr(B^{2})≤O[poly(logd)] and tr(B) known], is fundamental across quantum science and artificial intelligence. Classically, both computing and storing such inner products require O(d^{2}) resources, which rapidly becomes prohibitive as d grows exponentially. In this Letter, we introduce a quantum approach based on qudit classical shadow tomography, significantly reducing computational complexity from O(d^{2}) down to O[poly(logd)] in typical cases and at least to O[dpoly(logd)] in the worst case. Specifically, for n-qubit systems (with n being the number of qubit and d=2^{n}), our method guarantees efficient estimation of tr(ρO) for any known stabilizer state ρ and arbitrary bounded-norm observable O, using polynomial computational resources. Crucially, it ensures constant-time classical postprocessing per measurement and supports qubit and qudit platforms. Moreover, classical storage complexity of A reduces from O(d^{2}) to O(mlogd), where the sample complexity m is typically exponentially smaller than d^{2}. Our results establish a practical and modular quantum subroutine, enabling scalable quantum advantages in tasks involving high-dimensional data analysis and processing.