Handbook for Quantifying Robustness of Magic

Nonstabilizerness, or magic, is an essential quantum resource for performing universal quantum computation. Specifically, Robustness of Magic (RoM) characterizes the usefulness of a given quantum state for non-Clifford operations. While the mathematical formalism of RoM is concise, determining RoM in practice is highly challenging due to the necessity of dealing with a super-exponential number of stabilizer states. In this work, we present novel algorithms to compute RoM. The key technique is a subroutine for calculating overlaps between all stabilizer states and a target state, with the following remarkable features: (i) the time complexity per state is reduced {exponentially}, and (ii) the total space complexity is reduced {super-exponentially}. Based on this subroutine, we present algorithms to compute RoM for arbitrary states up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mn>8</mml:mn></mml:math> qubits, whereas the naive method requires a memory size of at least <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">86 PiB</mml:mtext></mml:mrow></mml:math>, which is infeasible for any current classical computer. Additionally, the proposed subroutine enables the computation of stabilizer fidelity for a mixed state up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mo>=</mml:mo><mml:mn>8</mml:mn></mml:math> qubits. We further propose novel algorithms that exploit prior knowledge of the structure of the target quantum state, such as permutation symmetry or disentanglement, and numerically demonstrate our results for copies of magic states and partially disentangled quantum states. This series of algorithms constitutes a comprehensive ``handbook'' for scaling up the computation of RoM. We envision that the proposed technique will also apply to the computation of other quantum resource measures.