Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Hidden variable models and classical simulation algorithms for quantum computation with magic states on qubits

Michael Zurel

Published Jan 1, 2020• 6 citations
Publisher

Abstract

An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd. The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space. The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.

DOI
10.14288/1.0394790

Related papers

The role of cohomology in quantum computation with magic states

Robert Raussendorf, Cihan Okay, Michael Zurel +1 more

A web of cohomological facts relates quantum error correction, measurement-based quantum computation, symmetry protected topological order and contextuality. Here we extend this web to quantum computation with magic states. In this computational scheme, the negativity of certain quasiprobability functions is an indicator for quantumness. However, when constructing quasiprobability functions to which this statement applies, a marked difference arises between the cases of even and odd local Hilbert space dimension. At a technical level, establishing negativity as an indicator of quantumness in quantum computation with magic states relies on two properties of the Wigner function: their covariance with respect to the Clifford group and positive representation of Pauli measurements. In odd dimension, Gross' Wigner function – an adaptation of the original Wigner function to odd-finite-dimensional Hilbert spaces – possesses these properties. In even dimension, Gross' Wigner function doesn't exist. Here we discuss the broader class of Wigner functions that, like Gross', are obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurements cannot be positively represented by them in any even dimension whenever the number of qudits is n ≥ 2. We establish that the obstructions to the existence of such Wigner functions are cohomological.

arXiv:2110.11631•Quantum•Apr 13, 2023•26 citations

Phase-space-simulation method for quantum computation with magic states on qubits

Robert Raussendorf, Juan Bermejo-Vega, Emily Tyhurst +2 more

We propose a method for classical simulation of finite-dimensional quantum systems, based on sampling from a quasiprobability distribution, i.e., a generalized Wigner function. Our construction applies to all finite dimensions, with the most interesting case being that of qubits. For multiple qubits, we find that quantum computation by Clifford gates and Pauli measurements on magic states can be efficiently classically simulated if the quasiprobability distribution of the magic states is non-negative. This provides the so far missing qubit counterpart of the corresponding result [V. Veitch et al., New J. Phys. 14, 113011 (2012)] applying only to odd dimension. Our approach is more general than previous ones based on mixtures of stabilizer states. Namely, all mixtures of stabilizer states can be efficiently simulated, but for any number of qubits there also exist efficiently simulable states outside the stabilizer polytope. Further, our simulation method extends to negative quasiprobability distributions, where it provides probability estimation. The simulation cost is then proportional to a robustness measure squared. For all quantum states, this robustness is smaller than or equal to robustness of magic.

arXiv:1905.05374•Physical Review A•Jan 31, 2020•83 citations

Simulation of quantum computation with magic states via Jordan-Wigner transformations

Michael Zurel, Lawrence Z. Cohen, Robert Raussendorf

Negativity in certain quasiprobability representations is a necessary condition for a quantum computational advantage. Here we define a quasiprobability representation exhibiting this property with respect to quantum computations in the magic state model. It is based on generalized Jordan-Wigner transformations, and it has a close connection to the probability representation of universal quantum computation based on the $\mathrm{\ensuremath{\Lambda}}$ polytopes. For each number of qubits, it defines a polytope contained in the $\mathrm{\ensuremath{\Lambda}}$ polytope with some shared vertices. It leads to an efficient classical simulation algorithm for magic state quantum circuits for which the input state is positively represented, and it outperforms previous representations in terms of the states that can be positively represented.

arXiv:2307.16034•Physical Review A•Sep 2, 2025•8 citations

Efficient classical simulation of quantum computation beyond Wigner positivity

Michael Zurel, Arne Heimendahl

We present the generalization of the CNC formalism, based on closed and noncontextual sets of Pauli observables, to the setting of odd-prime-dimensional qudits. By introducing new CNC-type phase space point operators, we construct a quasiprobability representation for quantum computation which is covariant with respect to the Clifford group and positivity preserving under Pauli measurements, and whose nonnegative sector strictly contains the subtheory of quantum theory described by nonnegative Wigner functions. This allows for a broader class of magic state quantum circuits to be efficiently classically simulated than those covered by the stabilizer formalism and Wigner function methods.

arXiv:2407.10349•Jul 14, 2024•9 citations

Hidden variable model for quantum computation with magic states on qudits of any dimension

Michael Zurel, Cihan Okay, Robert Raussendorf +1 more

It was recently shown that a hidden variable model can be constructed for universal quantum computation with magic states on qubits. Here we show that this result can be extended, and a hidden variable model can be defined for quantum computation with magic states on qudits with any Hilbert space dimension. This model leads to a classical simulation algorithm for universal quantum computation.

Quantum•Apr 30, 2024•7 citations

Negative Quasi-Probability in the Context of Quantum Computation

Victor Veitch

This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. \n \nMoreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. \n \nWe believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.

•Aug 9, 2013•2 citations
An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd. The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space. The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.
A web of cohomological facts relates quantum error correction, measurement-based quantum computation, symmetry protected topological order and contextuality. Here we extend this web to quantum computation with magic states. In this computational scheme, the negativity of certain quasiprobability functions is an indicator for quantumness. However, when constructing quasiprobability functions to which this statement applies, a marked difference arises between the cases of even and odd local Hilbert space dimension. At a technical level, establishing negativity as an indicator of quantumness in quantum computation with magic states relies on two properties of the Wigner function: their covariance with respect to the Clifford group and positive representation of Pauli measurements. In odd dimension, Gross' Wigner function – an adaptation of the original Wigner function to odd-finite-dimensional Hilbert spaces – possesses these properties. In even dimension, Gross' Wigner function doesn't exist. Here we discuss the broader class of Wigner functions that, like Gross', are obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurements cannot be positively represented by them in any even dimension whenever the number of qudits is n ≥ 2. We establish that the obstructions to the existence of such Wigner functions are cohomological.
We propose a method for classical simulation of finite-dimensional quantum systems, based on sampling from a quasiprobability distribution, i.e., a generalized Wigner function. Our construction applies to all finite dimensions, with the most interesting case being that of qubits. For multiple qubits, we find that quantum computation by Clifford gates and Pauli measurements on magic states can be efficiently classically simulated if the quasiprobability distribution of the magic states is non-negative. This provides the so far missing qubit counterpart of the corresponding result [V. Veitch et al., New J. Phys. 14, 113011 (2012)] applying only to odd dimension. Our approach is more general than previous ones based on mixtures of stabilizer states. Namely, all mixtures of stabilizer states can be efficiently simulated, but for any number of qubits there also exist efficiently simulable states outside the stabilizer polytope. Further, our simulation method extends to negative quasiprobability distributions, where it provides probability estimation. The simulation cost is then proportional to a robustness measure squared. For all quantum states, this robustness is smaller than or equal to robustness of magic.
Negativity in certain quasiprobability representations is a necessary condition for a quantum computational advantage. Here we define a quasiprobability representation exhibiting this property with respect to quantum computations in the magic state model. It is based on generalized Jordan-Wigner transformations, and it has a close connection to the probability representation of universal quantum computation based on the $\mathrm{\ensuremath{\Lambda}}$ polytopes. For each number of qubits, it defines a polytope contained in the $\mathrm{\ensuremath{\Lambda}}$ polytope with some shared vertices. It leads to an efficient classical simulation algorithm for magic state quantum circuits for which the input state is positively represented, and it outperforms previous representations in terms of the states that can be positively represented.
We present the generalization of the CNC formalism, based on closed and noncontextual sets of Pauli observables, to the setting of odd-prime-dimensional qudits. By introducing new CNC-type phase space point operators, we construct a quasiprobability representation for quantum computation which is covariant with respect to the Clifford group and positivity preserving under Pauli measurements, and whose nonnegative sector strictly contains the subtheory of quantum theory described by nonnegative Wigner functions. This allows for a broader class of magic state quantum circuits to be efficiently classically simulated than those covered by the stabilizer formalism and Wigner function methods.
This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. \n \nMoreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. \n \nWe believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.