Consumption of magic states promotes the stabilizer model of computation to universal quantum computation.Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones.Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity.We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits.Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds.Our third simulator trades precision for speed by discarding negative quasiprobabilities.We connect each algorithm's performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds.Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones.For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators' performance scaling.Furthermore, our monotones establish several asymptotic and nonasymptotic bounds on state interconversion and distillation rates.Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.
Consumption of magic states promotes the stabilizer model of computation to universal quantum computation.Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones.Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity.We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits.Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds.Our third simulator trades precision for speed by discarding negative quasiprobabilities.We connect each algorithm's performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds.Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones.For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators' performance scaling.Furthermore, our monotones establish several asymptotic and nonasymptotic bounds on state interconversion and distillation rates.Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.
The development of a framework for quantifying ‘non-stabilizerness’ of quantum operations is motivated by the magic state model of fault-tolerant quantum computation and by the need to estimate classical simulation cost for noisy intermediate-scale quantum (NISQ) devices. The robustness of magic was recently proposed as a well-behaved magic monotone for multi-qubit states and quantifies the simulation overhead of circuits composed of Clifford + T gates, or circuits using other gates from the Clifford hierarchy. Here we present a general theory of the ‘non-stabilizerness’ of quantum operations rather than states, which are useful for classical simulation of more general circuits. We introduce two magic monotones, called channel robustness and magic capacity, which are well-defined for general n -qubit channels and treat all stabilizer-preserving CPTP maps as free operations. We present two complementary Monte Carlo-type classical simulation algorithms with sample complexity given by these quantities and provide examples of channels where the complexity of our algorithms is exponentially better than previously known simulators. We present additional techniques that ease the difficulty of calculating our monotones for special classes of channels.
Abstract To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum ‘magic’ or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d , it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.
To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum 'magic' or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d, it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.
The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of mn-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements m and polynomial in the number of qubits n. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless P=NP, no algorithm polynomial in m can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.
The stabiliser formalism is a widely used and successful subtheory of quantum mechanics consisting of stabiliser states, Clifford unitaries and Pauli measurements. The power of the formalism comes from the description of its elements via simple group theory. Although the origins of the formalism lie in quantum error correction and fault-tolerant quantum computing, the utility of the formalism goes beyond that. The Gottesman-Knill theorem states that the dynamics of stabiliser states under Clifford unitaries and Pauli measurements can be efficiently simulated on a classical computer. This algorithm can be extended to arbitrary states and unitaries in multiple ways at the cost of an increased runtime. This runtime can be seen as a quantification of the non-stabiliser resources needed to implement a quantum circuit. Moreover, as non-stabiliser elements are necessary for universal quantum computing, the runtime provides a way to measure the “non-classicality” of a computation. This is particularly pronounced in the magic state model of quantum computing where the only non-stabiliser elements are given by magic states. Hence, in the resource theory of magic, resources are measured through magic monotones which are operationally linked to runtimes of classical simulation algorithms. In this thesis, I discuss different aspects of the resource theory of magic. The mentioned classical simulation algorithms require the computation of magic monotones which is in general a computationally intractable problem. However, I show that the computational complexity can be exponentially reduced for certain classes of symmetric states, such as copies of magic states. To this end, the symmetries of the convex hull of stabiliser states are characterised and linked to their properties as so-called designs. In addition, I study the recently introduced class of completely stabiliser-preserving channels (CSP), which is the class of quantum channels unable to generate magic resources. It is shown that this class is strictly larger than the class of stabiliser operations, composed of Clifford unitaries and Pauli measurements. This finding could have several interesting consequences. First, it implies that there is a class of efficiently simulable quantum channels beyond the Gottesman-Knill theorem. Second, it is possible that optimal magic state distillation rates cannot be achieved via stabiliser operations and this gap is in fact significant. Further applications of the stabiliser formalism come through design theory. A unitary t-design is an ensemble of unitaries which reproduce the first t moments of the Haar measure on the unitary group. Randomness in the form of Haar-random unitaries is an essential building block in many quantum information protocols. Implementing such Haar-random unitaries is however often impractical. Here, designs can exhibit considerably lower resource requirements while still being random enough for most applications. Some of the most prominent examples of such protocols concern the certification and characterisation of quantum systems, such as randomised benchmarking. Interestingly, the group of Clifford unitaries forms a unitary 3-design and is often the prime choice thanks to efficient group operations. In this thesis, I summarise my recent results obtained with collaborators in constructing approximate unitary t-designs from the Clifford group supplemented by only few non-Clifford gates. Intriguingly, this construction uses only O(t^4) single qubit non-Clifford gates and is independent of the number of qubits n. Overall, this yields a gate count which is a significant improvement over for the Brandao-Harrow- Horodecki construction based on local random circuits. To provide context for this result, I review the representation theory of the Clifford group and define the Clifford semigroup. In an attempt to generalise approximations results for the unitary group to the Clifford group, the Clifford semigroup is investigated for suitable approximations of the Clifford twirl.