On the Hardness of Measuring Magic
arXiv:2408.01663 · doi:10.1103/qcqv-3ym8
Abstract
Quantum computers promise to solve computational problems significantly faster than classical computers. These 'speed-ups' are achieved by utilizing a resource known as magic. Measuring the amount of magic used by a device allows us to quantify its potential computational power. Without this property, quantum computers are no faster than classical computers. Whether magic can be accurately measured on large-scale quantum computers has remained an open problem. To address this question, we introduce Pauli instability as a measure of magic and experimentally measure it on the IBM Eagle quantum processor. We prove that measuring large (i.e., extensive) quantities of magic is intractable. Our results suggest that one may only measure magic when a quantum computer does not provide a speed-up. We support our conclusions with both theoretical and experimental evidence. Our work illustrates the capabilities and limitations of quantum technology in measuring one of the most important resources in quantum computation.
5 pages
References in corpus (68)
- Quantum entanglement
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Machine Learning
- Quantum Computing
- Quantum computational advantage using photons
- Barren plateaus in quantum neural network training landscapes
- Quantum Teleportation is a Universal Computational Primitive
- Quantum computational chemistry
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Quantum Chemistry in the Age of Quantum Computing
- Quantum Convolutional Neural Networks
- Quantum Resource Theories
- Quantum Computing with Very Noisy Devices
- Measuring entanglement entropy through the interference of quantum many-body twins
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- Logical quantum processor based on reconfigurable atom arrays
- Quantum Computational Supremacy
- Towards Quantum Chemistry on a Quantum Computer
- Roads towards fault-tolerant universal quantum computation
- Quantum advantage in learning from experiments
- Benchmarking an 11-qubit quantum computer
- The Resource Theory of Stabilizer Computation
- Measuring the scrambling of quantum information
- Application of a resource theory for magic states to fault-tolerant quantum computing
- The randomized measurement toolbox
- Verified Quantum Information Scrambling
- Magic state distillation with low overhead
- Information Scrambling in Computationally Complex Quantum Circuits
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Trading classical and quantum computational resources
- Out-of-Time-Order Correlation for Many-Body Localization
- Stabilizer Rényi entropy
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Quantum computational finance: Monte Carlo pricing of financial derivatives
- Quantum Information Scrambling in a Superconducting Qutrit Processor
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Quantum Computing at the Frontiers of Biological Sciences
- Quantifying the magic of quantum channels
- Quantifying nonstabilizerness of matrix product states
- 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
- Probing scrambling using statistical correlations between randomized measurements
- Efficiently computable bounds for magic state distillation
- Does provable absence of barren plateaus imply classical simulability?
- Nonstabilizerness via matrix product states in the Pauli basis
- Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
- Magic spreading in random quantum circuits
- Efficient quantum algorithms for stabilizer entropies
- Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
- On the statistical complexity of quantum circuits
- Resource theory of quantum scrambling
- Quantum scrambling with classical shadows
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- Quantum advantage of unitary Clifford circuits with magic state inputs
- Pseudomagic Quantum States
- A single -gate makes distribution learning hard
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Pseudorandom unitaries are neither real nor sparse nor noise-robust
- Handbook for Quantifying Robustness of Magic
- Classical simulation of quantum circuits by half Gauss sums
- Barren plateaus from learning scramblers with local cost functions
- Pseudorandom density matrices
- Magic of Random Matrix Product States
- Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis