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

arXiv:1703.04630 · Entropy

Discrete Wigner Function Derivation of the Aaronson–Gottesman Tableau Algorithm

Lucas Kocia, Yifei Huang, Peter Love

Published Jul 11, 2017• 12 citations
arXivHTMLPDF

Abstract

The Gottesman–Knill theorem established that stabilizer states and Clifford operations can be efficiently simulated classically. For qudits with odd dimension three and greater, stabilizer states and Clifford operations have been found to correspond to positive discrete Wigner functions and dynamics. We present a discrete Wigner function-based simulation algorithm for odd-d qudits that has the same time and space complexity as the Aaronson–Gottesman algorithm for qubits. We show that the efficiency of both algorithms is due to harmonic evolution in the symplectic structure of discrete phase space. The differences between the Wigner function algorithm for odd-d and the Aaronson–Gottesman algorithm for qubits are likely due only to the fact that the Weyl–Heisenberg group is not in S U ( d ) for d = 2 and that qubits exhibit state-independent contextuality. This may provide a guide for extending the discrete Wigner function approach to qubits.

DOI
10.3390/e19070353

Related papers

Positive Wigner Functions Render Classical Simulation of Quantum Computation Efficient

Andrea Mari, Jens Eisert

We show that quantum circuits where the initial state and all the following quantum operations can be represented by positive Wigner functions can be classically efficiently simulated. This is true both for continuous-variable as well as discrete variable systems in odd prime dimensions, two cases which will be treated on entirely the same footing. Noting the fact that Clifford and Gaussian operations preserve the positivity of the Wigner function, our result generalizes the Gottesman-Knill theorem. Our algorithm provides a way of sampling from the output distribution of a computation or a simulation, including the efficient sampling from an approximate output distribution in the case of sampling imperfections for initial states, gates, or measurements. In this sense, this work highlights the role of the positive Wigner function as separating classically efficiently simulable systems from those that are potentially universal for quantum computing and simulation, and it emphasizes the role of negativity of the Wigner function as a computational resource.

arXiv:1208.3660•Physical Review Letters•Dec 4, 2012•457 citations

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

Michael Zurel

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.

•Jan 1, 2020•4 citations

Discrete Wigner formalism for qubits and noncontextuality of Clifford gates on qubit stabilizer states

Lucas Kocia, Peter J. Love

We show that qubit stabilizer states can be represented by non-negative quasiprobability distributions associated with a Wigner-Weyl-Moyal formalism where Clifford gates are positive state-independent maps. This is accomplished by generalizing the Wigner-Weyl-Moyal formalism to three generators instead of two---producing an exterior, or Grassmann, algebra---which results in Clifford group gates for qubits that act as a permutation on the finite Weyl phase space points naturally associated with stabilizer states. As a result, a non-negative probability distribution can be associated with each stabilizer state's three-generator Wigner function, and these distributions evolve deterministically to one another under Clifford gates. This corresponds to a hidden variable theory that is noncontextual and local for qubit Clifford gates while Clifford (Pauli) measurements have a context-dependent representation. Equivalently, we show that qubit Clifford gates can be expressed as propagators within the three-generator Wigner-Weyl-Moyal formalism whose semiclassical expansion is truncated at order ${\ensuremath{\hbar}}^{0}$ with a finite number of terms. The $T$ gate, which extends the Clifford gate set to one capable of universal quantum computation, requires a semiclassical expansion of the propagator to order ${\ensuremath{\hbar}}^{1}$. We compare this approach to previous quasiprobability descriptions of qubits that relied on the two-generator Wigner-Weyl-Moyal formalism and find that the two-generator Weyl symbols of stabilizer states result in a description of evolution under Clifford gates that is state-dependent, in contrast to the three-generator formalism. We have thus extended Wigner non-negative quasiprobability distributions from the odd $d$-dimensional case to $d=2$ qubits, which describe the noncontextuality of Clifford gates and contextuality of Pauli measurements on qubit stabilizer states.

arXiv:1705.08869•Physical Review A•Dec 29, 2017•33 citations

Semiclassical formulation of the Gottesman-Knill theorem and universal quantum computation

Lucas Kocia, Yifei Huang, Peter J. Love

We give a path-integral formulation of the time evolution of qudits of odd dimension. This allows us to consider semiclassical evolution of discrete systems in terms of an expansion of the propagator in powers of $\ensuremath{\hbar}$. The largest power of $\ensuremath{\hbar}$ required to describe the evolution is a traditional measure of classicality. We show that the action of the Clifford operators on stabilizer states can be fully described by a single contribution of a path integral truncated at order ${\ensuremath{\hbar}}^{0}$ and so are ``classical,'' just like propagation of Gaussians under harmonic Hamiltonians in the continuous case. Such operations have no dependence on phase or quantum interference. Conversely, we show that supplementing the Clifford group with gates necessary for universal quantum computation results in a propagator consisting of a finite number of semiclassical path-integral contributions truncated at order ${\ensuremath{\hbar}}^{1}$, a number that nevertheless scales exponentially with the number of qudits. The same sum in continuous systems has an infinite number of terms at order ${\ensuremath{\hbar}}^{1}$.

arXiv:1612.05649•Physical Review A•Sep 20, 2017•9 citations

Classicality in discrete Wigner functions

Cecilia Cormick, Ernesto F. Galvão, Daniel Gottesman +2 more

Gibbons et al., [Phys. Rev. A 70, 062101 (2004)] have recently defined discrete Wigner functions $W$ to represent quantum states in a Hilbert space with finite dimension. We show that such a class of Wigner functions $W$ can be defined so that the only pure states having non-negative $W$ for all such functions are stabilizer states, as conjectured by Galv\~ao, [Phys. Rev. A 71, 042302 (2005)]. We also show that the unitaries preserving non-negativity of $W$ for all definitions of $W$ in the class form a subgroup of the Clifford group. This means pure states with non-negative $W$ and their associated unitary dynamics are classical in the sense of admitting an efficient classical simulation scheme using the stabilizer formalism.

arXiv:quant-ph/0506222•Physical Review A•Jan 3, 2006•129 citations

Noise thresholds for higher-dimensional systems using the discrete Wigner function

Wim van Dam, Mark Howard

For a quantum computer acting on $d$-dimensional systems, we analyze the computational power of circuits wherein stabilizer operations are perfect, and we allow access to imperfect nonstabilizer states or operations. If the noise rate affecting the nonstabilizer resource is sufficiently high, then these states and operations can become simulable in the sense of the Gottesman-Knill theorem, reducing the overall power of the circuit to no better than classical. In this paper we find the depolarizing noise rate at which this happens and consequently the most robust nonstabilizer states and non-Clifford gates. In doing so, we make use of the discrete Wigner function and derive facets of the so-called qudit Clifford polytope, i.e., the inequalities defining the convex hull of all qudit Clifford gates. Our results for robust states are provably optimal. For robust gates we find a critical noise rate that, as dimension increases, rapidly approaches the the theoretical optimum of 100%. Some connections with the question of qudit magic state distillation are discussed.

arXiv:1011.2497•Physical Review A•Mar 17, 2011•39 citations
The Gottesman–Knill theorem established that stabilizer states and Clifford operations can be efficiently simulated classically. For qudits with odd dimension three and greater, stabilizer states and Clifford operations have been found to correspond to positive discrete Wigner functions and dynamics. We present a discrete Wigner function-based simulation algorithm for odd-d qudits that has the same time and space complexity as the Aaronson–Gottesman algorithm for qubits. We show that the efficiency of both algorithms is due to harmonic evolution in the symplectic structure of discrete phase space. The differences between the Wigner function algorithm for odd-d and the Aaronson–Gottesman algorithm for qubits are likely due only to the fact that the Weyl–Heisenberg group is not in S U ( d ) for d = 2 and that qubits exhibit state-independent contextuality. This may provide a guide for extending the discrete Wigner function approach to qubits.
We show that quantum circuits where the initial state and all the following quantum operations can be represented by positive Wigner functions can be classically efficiently simulated. This is true both for continuous-variable as well as discrete variable systems in odd prime dimensions, two cases which will be treated on entirely the same footing. Noting the fact that Clifford and Gaussian operations preserve the positivity of the Wigner function, our result generalizes the Gottesman-Knill theorem. Our algorithm provides a way of sampling from the output distribution of a computation or a simulation, including the efficient sampling from an approximate output distribution in the case of sampling imperfections for initial states, gates, or measurements. In this sense, this work highlights the role of the positive Wigner function as separating classically efficiently simulable systems from those that are potentially universal for quantum computing and simulation, and it emphasizes the role of negativity of the Wigner function as a computational resource.
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.
We show that qubit stabilizer states can be represented by non-negative quasiprobability distributions associated with a Wigner-Weyl-Moyal formalism where Clifford gates are positive state-independent maps. This is accomplished by generalizing the Wigner-Weyl-Moyal formalism to three generators instead of two---producing an exterior, or Grassmann, algebra---which results in Clifford group gates for qubits that act as a permutation on the finite Weyl phase space points naturally associated with stabilizer states. As a result, a non-negative probability distribution can be associated with each stabilizer state's three-generator Wigner function, and these distributions evolve deterministically to one another under Clifford gates. This corresponds to a hidden variable theory that is noncontextual and local for qubit Clifford gates while Clifford (Pauli) measurements have a context-dependent representation. Equivalently, we show that qubit Clifford gates can be expressed as propagators within the three-generator Wigner-Weyl-Moyal formalism whose semiclassical expansion is truncated at order ${\ensuremath{\hbar}}^{0}$ with a finite number of terms. The TTT gate, which extends the Clifford gate set to one capable of universal quantum computation, requires a semiclassical expansion of the propagator to order ${\ensuremath{\hbar}}^{1}$. We compare this approach to previous quasiprobability descriptions of qubits that relied on the two-generator Wigner-Weyl-Moyal formalism and find that the two-generator Weyl symbols of stabilizer states result in a description of evolution under Clifford gates that is state-dependent, in contrast to the three-generator formalism. We have thus extended Wigner non-negative quasiprobability distributions from the odd ddd-dimensional case to d=2d=2d=2 qubits, which describe the noncontextuality of Clifford gates and contextuality of Pauli measurements on qubit stabilizer states.
We give a path-integral formulation of the time evolution of qudits of odd dimension. This allows us to consider semiclassical evolution of discrete systems in terms of an expansion of the propagator in powers of $\ensuremath{\hbar}$. The largest power of $\ensuremath{\hbar}$ required to describe the evolution is a traditional measure of classicality. We show that the action of the Clifford operators on stabilizer states can be fully described by a single contribution of a path integral truncated at order ${\ensuremath{\hbar}}^{0}$ and so are ``classical,'' just like propagation of Gaussians under harmonic Hamiltonians in the continuous case. Such operations have no dependence on phase or quantum interference. Conversely, we show that supplementing the Clifford group with gates necessary for universal quantum computation results in a propagator consisting of a finite number of semiclassical path-integral contributions truncated at order ${\ensuremath{\hbar}}^{1}$, a number that nevertheless scales exponentially with the number of qudits. The same sum in continuous systems has an infinite number of terms at order ${\ensuremath{\hbar}}^{1}$.
Gibbons et al., [Phys. Rev. A 70, 062101 (2004)] have recently defined discrete Wigner functions WWW to represent quantum states in a Hilbert space with finite dimension. We show that such a class of Wigner functions WWW can be defined so that the only pure states having non-negative WWW for all such functions are stabilizer states, as conjectured by Galv\~ao, [Phys. Rev. A 71, 042302 (2005)]. We also show that the unitaries preserving non-negativity of WWW for all definitions of WWW in the class form a subgroup of the Clifford group. This means pure states with non-negative WWW and their associated unitary dynamics are classical in the sense of admitting an efficient classical simulation scheme using the stabilizer formalism.
For a quantum computer acting on ddd-dimensional systems, we analyze the computational power of circuits wherein stabilizer operations are perfect, and we allow access to imperfect nonstabilizer states or operations. If the noise rate affecting the nonstabilizer resource is sufficiently high, then these states and operations can become simulable in the sense of the Gottesman-Knill theorem, reducing the overall power of the circuit to no better than classical. In this paper we find the depolarizing noise rate at which this happens and consequently the most robust nonstabilizer states and non-Clifford gates. In doing so, we make use of the discrete Wigner function and derive facets of the so-called qudit Clifford polytope, i.e., the inequalities defining the convex hull of all qudit Clifford gates. Our results for robust states are provably optimal. For robust gates we find a critical noise rate that, as dimension increases, rapidly approaches the the theoretical optimum of 100%. Some connections with the question of qudit magic state distillation are discussed.