Quantum Computing Advances with Algorithms for Measuring State Vector Magic, Revealing Complexity of Qudits

The quantification of ‘magic’, or non-stabilizerness, is a crucial step towards unlocking the full potential of quantum computation and understanding the complexity of quantum states. Piotr Sierant, Jofre Vallès-Muns, and Artur Garcia-Saez, from the Barcelona Supercomputing Center and Qilimanjaro Quantum Tech, have now developed significantly more efficient algorithms for calculating this vital property. Their research addresses the computational cost associated with existing methods for quantifying magic, such as the stabilizer Rényi entropy and mana, which rapidly increase with system size. By exploiting the fast Hadamard transform, the team achieves an exponential improvement in computational speed, enabling practical large-scale numerical studies of quantum magic in complex quantum systems and offering a powerful new tool for researchers in the field. The algorithms are readily available within the open-source Julia package, HadaMAG, complete with support for parallel processing and GPU acceleration.

Their research addresses the computational cost associated with existing methods for quantifying magic, such as the stabilizer Rényi entropy and mana, which rapidly increase with system size.

By exploiting the fast Hadamard transform, the team achieves an exponential improvement in computational speed, enabling practical large-scale numerical studies of quantum magic in complex quantum systems and offering a powerful new tool for researchers in the field. The algorithms are readily available within the open-source Julia package, HadaMAG, complete with support for parallel processing and GPU acceleration. These new methods leverage the fast Hadamard transform, dramatically reducing computational cost from a naive scaling of O(d³N) to O(Nd²N), where ‘d’ represents the local dimension and ‘N’ the number of qudits.

The study also pioneered a method combining the Hadamard transform with Monte Carlo sampling to estimate SRE for state vectors and extend the approach to mixed states, broadening the applicability of the technique. This advancement allows for substantial parallelism and straightforward implementation with GPU acceleration, unlocking the potential for detailed investigations of magic in quantum many-body systems. The system delivers a high-performance toolbox for computing SRE and mana, designed for large-scale numerical studies.

Efficient Algorithms Quantify Quantum Magic Measures

Scientists achieved a significant breakthrough in quantifying ‘magic’, a measure of a quantum state’s departure from classical behaviour, by developing efficient algorithms for calculating the Stabilizer Rényi Entropy (SRE) for qubits and the mana for qutrits. The research team devised methods that compute SRE and mana with a computational cost of O(Nd²N), representing an exponential improvement over previously existing techniques. These algorithms leverage the fast Hadamard transform to analyse pure states represented as state vectors, offering substantial parallelism and the potential for straightforward GPU acceleration.

Experiments revealed that the new algorithms can calculate SRE and mana far more rapidly than conventional methods, particularly as the number of qudits increases. The work demonstrates the ability to compute the SRE for systems of up to 22 qubits in under one hour using a single node with 112 CPU cores, a feat previously unattainable with naive algorithms limited to 16 qubits within the same timeframe. The team also implemented the algorithms within an open-source Julia package, HadaMAG, which supports multithreading, MPI-based distributed parallelism, and GPU acceleration.

Measurements confirm that the SRE grows monotonically with increasing circuit depth in random quantum circuits, eventually approaching a characteristic value for Haar-random states, as predicted by theoretical analysis. The algorithms’ efficiency stems from partitioning calculations into independent chunks, enabling near-ideal speedup as the number of cores increases, and the ability to offload core kernels to GPUs for substantial performance gains. This delivers a practical route to large-scale numerical studies of quantum magic, with the package requiring a manageable memory footprint even with extensive parallelisation.

Efficient Stabiliser Rényi Entropy and Mana Calculation

This work introduces a family of algorithms for efficiently calculating the stabilizer Rényi entropy (SRE) and mana, measures of ‘magic’, or the departure from stabiliser states, in many-body quantum systems. The core algorithms achieve a computational scaling of O(Nd²N), where N is the system size and d is the local Hilbert space dimension, representing a significant improvement over previously established methods which scale as O(d³N). Importantly, this enhanced speed is achieved without increasing memory requirements, maintaining a footprint of O(dN).

The researchers demonstrate that these algorithms are highly parallelisable and well-suited for implementation on modern high-performance computing architectures. This is realised through the open-source Julia package, HadaMAG.jl, which supports multi-threading, distributed memory parallelism and GPU acceleration, enabling the calculation of SRE and mana for larger systems than previously possible. Furthermore, the work reveals a unifying mathematical structure underlying these non-stabiliser measures, connecting the fast Hadamard transform to SRE and its ternary analogue to mana, expressed as fast Fourier transforms.

The developed tools offer a practical pathway for detailed numerical investigations of ‘magic’ in quantum computation and information processing. Future research could explore the application of these algorithms to study quantum dynamics and resource-theoretic diagnostics in larger and more complex quantum systems. The authors acknowledge that their sampling scheme for SRE relies on assumptions about the scaling of statistical uncertainty, and further investigation may be needed to confirm these findings across a wider range of states.