Quantum Advantage via Efficient Postprocessing on Qudit Classical Shadow Tomography.

Area of Science:

• Quantum Information Science
• Quantum Computing
• Artificial Intelligence

Background:

• Computing inner products tr(AB) is crucial for quantum science and AI.
• Classical methods require prohibitive O(d^2) resources for high-dimensional density matrices (A) and observables (B).

Purpose of the Study:

• To develop a quantum approach for efficient inner product computation.
• To reduce computational and storage complexity compared to classical methods.

Main Methods:

• Utilizing qudit classical shadow tomography.
• Applying the method to n-qubit systems for stabilizer states and bounded-norm observables.

Main Results:

• Reduced computational complexity from O(d^2) to O(poly(logd)) in typical cases.
• Achieved classical storage complexity reduction from O(d^2) to O(m logd), with m typically exponentially smaller than d^2.
• Guaranteed efficient estimation of tr(ρO) for stabilizer states using polynomial resources.

Conclusions:

• Established a practical quantum subroutine for scalable quantum advantage in high-dimensional data analysis.
• The method supports both qubit and qudit platforms with constant-time classical postprocessing per measurement.