Handbook for Quantifying Robustness of Magic

Abstract

The nonstabilizerness, or magic, is an essential quantum resource to perform universal quantum computation. Robustness of magic (RoM) in particular characterizes the degree of usefulness of a given quantum state for non-Clifford operation. While the mathematical formalism of RoM can be given in a concise manner, it is extremely challenging to determine the RoM in practice, since it involves superexponentially many pure stabilizer states. In this work, we present efficient novel algorithms to compute the RoM. The crucial technique is a subroutine that achieves the remarkable features in calculation of overlaps between pure stabilizer states: (i) the time complexity per each stabilizer is reduced exponentially, (ii) the space complexity is reduced superexponentially. Based on this subroutine, we present algorithms to compute the RoM for arbitrary states up to $n=7$ qubits on a laptop, while brute-force methods require a memory size of 86 TiB. As a byproduct, the proposed subroutine allows us to simulate the stabilizer fidelity up to $n=8$ qubits, for which naive methods require memory size of 86 PiB so that any state-of-the-art classical computer cannot execute the computation. We further propose novel algorithms that utilize the preknowledge on the structure of target quantum state such as the permutation symmetry of disentanglement, and numerically demonstrate our state-of-the-art results for copies of magic states and partially disentangled quantum states. The series of algorithms constitute a comprehensive ``handbook'' to scale up the computation of the RoM, and we envision that the proposed technique applies to the computation of other quantum resource measures as well.

17+8 pages, 9+2 figures

References in corpus (13)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Stabilizer Rényi entropy
• Quantum computing enhanced computational catalysis
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Efficient quantum algorithms for stabilizer entropies
• Hunting for quantum-classical crossover in condensed matter problems
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Tensorized Pauli decomposition algorithm
• Classical simulation of non-Gaussian fermionic circuits
• PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently
• On the Geometry of Stabilizer States

Cited by in corpus (12)

• Tensorized Pauli decomposition algorithm
• Stabilizer Rényi Entropy and Conformal Field Theory
• A nonstabilizerness monotone from stabilizerness asymmetry
• Fermionic Magic Resources of Quantum Many-Body Systems
• Computing quantum magic of state vectors
• Prepare-and-Magic: Semi-Device Independent Magic Certification in the Prepare-and-Measure Scenario
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Faster computation of nonstabilizerness
• Nonstabilizerness and Error Resilience in Noisy Quantum Circuits
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• On the Hardness of Measuring Magic
• Resource-efficient Quantum Algorithms for Selected Hamiltonian Subspace Diagonalization