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.
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.
Abstract Magic states are the resource that allows quantum computers to attain an advantage over classical computers. This resource consists in the deviation from a property called stabilizerness which in turn implies that stabilizer circuits can be efficiently simulated on a classical computer. Without magic, no quantum computer can do anything that a classical computer cannot do. Given the importance of magic for quantum computation, it would be useful to have a method for measuring the amount of magic in a quantum state. In this work, we propose and experimentally demonstrate a protocol for measuring magic based on randomized measurements. Our experiments are carried out on two IBM Quantum Falcon processors. This protocol can provide a characterization of the effectiveness of a quantum hardware in producing states that cannot be effectively simulated on a classical computer. We show how from these measurements one can construct realistic noise models affecting the hardware.
Nonstabilizerness or magic resource characterizes the amount of non-Clifford operations needed to prepare quantum states.It is a crucial resource for quantum computing and a necessary condition for quantum advantage.However, quantifying magic resource beyond a few qubits has been a major challenge.Here, we introduce efficient measures of magic resource for pure quantum states with a sampling cost that is independent of the number of qubits.Our method uses Bell measurements over two copies of a state, which we implement in experiment together with a cost-free error-mitigation scheme.We show the transition of classically simulable stabilizer states into intractable quantum states on the IonQ quantum computer.For applications, we efficiently distinguish stabilizer and nonstabilizer states with low measurement cost even in the presence of experimental noise.Further, we propose a variational quantum algorithm to maximize our measure via the shift rule.Our algorithm can be free of barren plateaus even for highly expressible variational circuits.Finally, we experimentally demonstrate a Bell-measurement protocol for the stabilizer Rényi entropy as well as the Wallach-Meyer entanglement measure.Our results pave the way to understanding the nonclassical power of quantum computers, quantum simulators, and quantum many-body systems.
In this thesis we address the question, what is the resource, or property, that enables the advantage of quantum computers?The theory of quantum computers dates back to the eighties, so one would think there already is an answer to this question.There are several proposed solutions, but to this date, there is no consensus on an answer.Primarily, the advantage of quantum computers is characterized by a speedup for certain computational problems.This speedup is measured by comparing quantum algorithms with the bestknown classical algorithms.For some algorithms we assume access to an object called oracle.The oracle computes a function, and the complexity of the oracle is of no concern.Instead, we count the number of queries to the oracle needed to solve the problem.Informally, the question we ask using an oracle is: if we can compute this function efficiently, what else could we then compute.However, using oracles while measuring a quantum speedup, we assume access to vastly different oracles residing in different models of computation.For our investigation of the speedup, we introduce a classical simulation framework that imitates quantum algorithms.The simulation suggests that the property enabling the potential quantum speedup is the ability to store, process, and retrieve information in an additional degree of freedom.We then theoretically verified that this is true for all problems that can be efficiently solved with a quantum computer.In parallel to this, we also see that quantum oracles sharply specify the information we can retrieve from the additional degree of freedom, while regular oracles do not.A regular oracle does not even allow for an extra degree of freedom.We conclude that comparing quantum with classical oracle query complexity bounds does not provide conclusive evidence for a quantum advantage.I want to thank Jan-Åke Larsson, without whom this research would not have been possible.If there is any magic in the world, it shows through Jan-Åke's ability to simultaneously be a good supervisor, colleague, and friend.I would also like to thank my co-supervisor Peter Jonsson, for many valuable discussions -not only restricted to theoretical computer science.To my friends and collogues that have challenged me to become better, especially Jonathan Jogenfors
Quantum computing promises the ability to compute properties of quantum systems exponentially faster than classical computers. Quantum advantage is achieved when a practical problem is solved more efficiently on a quantum computer than on a classical computer. Demonstrating quantum advantage requires a powerful quantum computer with low error rates and an efficient quantum algorithm that has a useful application. Despite rapid progress in hardware development, we still lack useful applications that are feasible for the next generation of quantum computers. Here we argue that an exponential quantum advantage exists in producing numerical resource estimates of larger quantum algorithms by accurately measuring simulation errors. We provide a quantum algorithm for measuring simulation errors of Trotter-based algorithms. Our results indicate that this method will reduce runtimes of quantum algorithms by approximately three orders of magnitude for one-hundred qubit systems. We also predict that these reductions will increase with system size. The methods we propose require relatively few qubits and operations, meaning the next generation of quantum computers could compute simulation errors for classically intractable systems. Since the underlying computations that lead to reduced resource estimates are infeasible for classical computers, this task is a candidate for demonstrating practical quantum advantage.
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits n, even approximately. We reduce the problem to solving a 3-\class{SAT} instance on n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
Magic states and magic gates are crucial for achieving universal quantum computation, but important questions about how magic resources should be implemented to attain maximal quantum advantage have remained unexplored, especially in the context of measurement-based quantum computation (MQC). This work bridges the gap between MQC and the resource theory of magic by introducing the key concepts of "invested" and "potential" magic resources. The former quantifies the magic cost associated with MQC, serving as both a resource witness and a feasible upper bound for the practical realization, and is gate-order independent; The latter represents the maximal achievable magic resource in a given graph structure defining MQC. We utilize both concepts to analyze the quantum Fourier transform (QFT) and provide a fresh perspective on the universality of MQC, highlighting the crucial role of non-Pauli measurements in injecting magic. In particular, we theoretically prove that high-dimensional graphs can generate an exponential advantage of MQC compared to classical computing. We demonstrate experimentally our theoretical findings in a high-fidelity four-photon setup, surpassing conventional magic state injection (MSI) methods in both qubit efficiency and resource utilization. Our findings pave the way for future research exploring magic resource optimization and novel distillation schemes within the MQC framework, advancing fault-tolerant universal quantum computation.