Faster Computation of Stabilizer Extent

Characterization of nonstabilizerness is fruitful due to its application in gate synthesis and classical simulation. In particular, the resource monotone called the stabilizer extent is indispensable to estimate the simulation cost using the rank-based simulators, one of the state-of-the-art simulators of Clifford+T circuits. In this work, we propose fast numerical algorithms to compute the stabilizer extent. Our algorithm utilizes the Column Generation method, which iteratively updates the subset of pure stabilizer states used for calculation. This subset is selected based on the overlaps between all stabilizer states and a target state. Upon updating the subset, we make use of a newly proposed subroutine for calculating the stabilizer fidelity that (i) achieves the linear time complexity with respect to the number of stabilizer states, (ii) super-exponentially reduces the space complexity by in-place calculation, and (iii) prunes unnecessary states for the computation. As a result, our algorithm can compute the stabilizer fidelity and the stabilizer extent for Haar random pure states up to n=9 qubits, which naively requires a memory of 305 EiB. We further show that our algorithm runs even faster when the target state vector is real. The optimization problem size is reduced so that we can compute the case of n=10 qubits in 4. 7 hours.