Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography

Efficiently computing the trace of the product of exponential-scale matrices A and B presents a significant challenge in classical computation, particularly when A is a d-dimensional positive Hermitian matrix with trace 1, and B is a Hermitian matrix with a bounded norm. This computation traditionally requires O(d²) time complexity. We explore leveraging quantum advantage to perform this computation in O(poly(log d)) time for a broad class of matrices A, offering potential applications in high-dimensional data analysis and complex systems. We propose a shadow tomography scheme for arbitrary d-dimensional systems that utilizes random projective measurements onto Dense Dual Bases for efficient sampling and post-processing. Unlike random Clifford or mutually unbiased bases (MUB) measurements, our method is experimentally feasible on optical platforms. It requires exponentially fewer computations to determine all coefficients of the randomly projected states, with a constant post-processing time per measurement, as opposed to the exponential worst-case scenario seen with random Clifford (MUB) measurements. For general dimensions d, the existence of $d+1$ MUBs in general dimensions is still an open question, and the processing of randomized Clifford measurements is not fully understood. While the applicability of matrix A may be more limited compared to random Clifford measurements, our approach remains efficient in several cases, with average performance that is particularly efficient. For all A, the computational complexity is $O(d)$, and in the approximately average case, it is O(poly(log d)). This scheme holds significant potential beyond quantum information science; it could be instrumental in fields such as artificial intelligence, enabling efficient computation of tr(AB).