Faster computation of nonstabilizerness

Abstract

The 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 a useful tool to estimate the simulation cost using rank-based simulators, one of the state-of-the-art simulators of Clifford+$T$ circuits. In this work, we propose faster 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. In order to update the subset, we make use of a newly proposed subroutine for calculating the stabilizer fidelity that (i) achieves 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 faster when the target state vector is real. We prove that the problem size is reduced by $\mathcal{O}(2^n)$ compared to the general cases, which makes it computable for the case of $n=10$ qubits.

15pages, 4 figures

References in corpus (30)

• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Surface code quantum computing by lattice surgery
• Application of a resource theory for magic states to fault-tolerant quantum computing
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum computing enhanced computational catalysis
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Measuring magic on a quantum processor
• Scalable measures of magic resource for quantum computers
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Conformal field theories are magical
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics
• Efficient quantum algorithms for stabilizer entropies
• Hunting for quantum-classical crossover in condensed matter problems
• Pseudomagic Quantum States
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Stabilizer extent is not multiplicative
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Handbook for Quantifying Robustness of Magic

Cited by in corpus (4)

• A nonstabilizerness monotone from stabilizerness asymmetry
• Nonstabilizerness and Error Resilience in Noisy Quantum Circuits
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits