Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography

Abstract

The computation of \(\operatorname{tr}(AB)\) is essential in quantum science and artificial intelligence, yet classical methods for \( d \)-dimensional matrices \( A \) and \( B \) require \( O(d^2) \) complexity, which becomes infeasible for exponentially large systems. We introduce a quantum approach based on qudit shadow tomography that reduces both computational and storage complexities to \( O(\text{poly}(\log d)) \) in specific cases. The proposed method applies to quantum density matrices \( A \) and Hermitian matrices \( B \) with given \(\operatorname{tr}(B)\) and \(\operatorname{tr}(B^2)\) bounded by a constant (referred to as BN-observables). It guarantees at least a quadratic speedup (\(O(d^2) \to O(d)\)) in the worst case and achieves exponential speedup for approximately average cases. For any \( n \)-qubit stabilizer state \(ρ\) and arbitrary BN-observable \( O \), we show that \(\operatorname{tr}(ρO)\) can be efficiently estimated with \(\text{poly}(n)\) computations. Moreover, our approach significantly reduces the post-processing complexity in shadow tomography using random Clifford measurements, and it is applicable to arbitrary dimensions \( d \). These advances open new avenues for efficient high-dimensional data analysis and modeling.

Accepted for publication in Physical Review Letters

References in corpus (22)

• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Entanglement detection
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Quantum advantage in learning from experiments
• Direct Fidelity Estimation from Few Pauli Measurements
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Multiqubit Clifford groups are unitary 3-designs
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Robust shadow estimation
• Classical Shadows With Noise
• Experimental Estimation of Quantum State Properties from Classical Shadows
• How to efficiently select an arbitrary Clifford group element
• Optimising shadow tomography with generalised measurements
• Entanglement Detection Beyond Measuring Fidelities
• Shadow tomography from emergent state designs in analog quantum simulators
• Shadow tomography on general measurement frames
• Error-mitigated fermionic classical shadows on noisy quantum devices
• Triply efficient shadow tomography
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate