Hardness of measuring magic resource

Quantum computers promise to solve computational problems significantly faster than classical computers. These “speedups” are achieved by utilizing a resource known as magic resource. Measuring the amount of magic resource 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 resource can be accurately measured on large-scale quantum computers has remained an open problem. To address this question, we introduce as a measure of magic resource and experimentally measure it on the IBM Eagle quantum processor. We show that sufficiently small quantities of magic resource can be measured efficiently. We also prove that measuring large (i.e., extensive) quantities of magic resource with our measure is intractable. Our results lead us to surmise that magic resource may be difficult to measure when a quantum computer provides a speedup. We find that one of the most sought-after properties in quantum computation is only partially accessible to experiments. We support our conclusions with both theoretical and experimental evidence. Our work illustrates the capabilities and limitations encountered when studying the power of quantum computers.