Towards Optimal Quantum Estimators for State Frame Potential

The state frame potential is a fundamental metric used to quantify how closely a quantum state ensemble approximates Haar randomness. As quantum systems grow in complexity, efficiently benchmarking this randomness becomes essential for verifying quantum simulators, studying scrambling, and validating quantum machine learning models. This paper provides a comprehensive study of the computational complexity of estimating the state frame potential of order t to within additive error epsilon, across three increasingly constrained access models.

The authors analyze the estimation problem under three models:

1. Query Model: The algorithm has access to a multi-state-preparation oracle. The authors reformulate the frame potential as the trace of a subnormalized density operator, allowing them to apply Quantum Singular Value Transformation (QSVT) and polynomial approximation techniques.
2. General Sample Model: The algorithm has access to multiple identical copies of states drawn from the ensemble. The authors utilize a generalized SWAP test to derive an unbiased estimator.
3. Single-Copy Sample Model: The algorithm receives only one labeled copy of a state per sample. The authors introduce a store-and-estimate approach that identifies and stores states from the heavy set of the ensemble, with sample complexity governed by the Rényi entropy of the ensemble weights.

• Query Complexity: The authors establish a near-optimal query complexity of O(sqrt(t)log(1/epsilon)/epsilon), providing a quadratic improvement in the dependence on t compared to prior work.
• Sample Complexity: In the general sample model, they prove an optimal complexity of Theta(t/epsilon^2).
• Single-Copy Efficiency: In the single-copy model, the sample complexity is shown to depend on the Rényi entropy of the ensemble weights, making it particularly efficient for ensembles concentrated on a small effective support, such as projected state ensembles in many-body physics.