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:1612.05649 · Physical Review A

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

Lucas Kocia, Yifei Huang, Peter J. Love

Published Sep 20, 2017• 9 citations
arXivHTMLPDF

Abstract

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}$.

DOI
10.1103/physreva.96.032331

Related papers

Path integral formulation of finite-dimensional quantum mechanics in discrete phase space

Leonardo A. Pachon, Andres D. Gomez

We develop a path integral representation for the dynamics of quantum systems with a finite-dimensional Hilbert space, formulated entirely within a discrete phase space. Starting from the discrete Wigner function on ${\mathbb{Z}_d} \times {\mathbb{Z}_d}$ ($d$ an odd prime) and the associated Weyl transform built from generalized displacement operators, we derive an exact kernel that propagates the discrete Wigner function in time and, by iterating its composition law through a short-time approximation, obtain a sum-over-paths expression weighted by a discrete phase-space action -- the natural finite-dimensional counterpart of Marinov's functional. For Hamiltonians linear in the phase-space coordinates and at times strictly commensurate with the lattice, the fluctuation sum collapses to a deterministic shift, realizing the discrete analog of classical Hamiltonian flow. Applying the formalism to one and to two interacting qutrits ($d=3$), we show that the full entanglement dynamics -- captured by a closed-form linear entropy valid for all times -- requires the coherent contribution of all fluctuation sectors; the boundary-term (mean-field) sector alone fails to reproduce it. For a non-stabilizer Hamiltonian, where the short-time kernel is only approximate, the time-sliced path integral converges to the exact dynamics, including the dynamical generation of Wigner negativity. We discuss implications for the semiclassical simulation of many-body spin systems and for the characterization of non-classicality through Wigner negativity.

quant-pharXiv:2604.20776•Apr 23, 2026•0 citations

Discrete Wigner Function Derivation of the Aaronson–Gottesman Tableau Algorithm

Lucas Kocia, Yifei Huang, Peter Love

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.

arXiv:1703.04630•Entropy•Jul 11, 2017•12 citations

On the stabilizer formalism and its generalization

Éloi Descamps, Borivoje Dakić

Abstract The standard stabilizer formalism provides a setting to show that quantum computations restricted to operations within the Clifford group are classically efficiently simulable: this is the content of the well-known Gottesman–Knill theorem. This work analyzes the mathematical structure behind this theorem to find possible generalizations and derivation of constraints required for constructing a non-trivial generalized Clifford group. We prove that if the closure of the stabilizing set is dense in the set of SU(d) transformations, then the associated Clifford group is trivial, consisting only of local gates and permutations of subsystems. This result demonstrates the close relationship between the density of the stabilizing set and the simplicity of the corresponding Clifford group. We apply the analysis to investigate stabilization with binary observables for qubits and find that the formalism is equivalent to the standard stabilization for a low number of qubits. Based on the observed patterns, we conjecture that a large class of generalized stabilizer states are equivalent to the standard ones. Our results provide better insights into the structure of Gottesman–Knill-type results, consequently allowing us to draw a sharper line between quantum and classical computation.

arXiv:2309.09815•Journal of Physics A Mathematical and Theoretical•Oct 11, 2024•1 citation

Clifford Circuits on Qudits of Mixed Dimension

Milo Moses, Jacek Horecki, Konrad Deka +1 more

Abstract Associated to every finite abelian group G , there is a generalization of qubit Clifford group associated to G . We demonstrate that every G -Clifford gate can be decomposed into some distinguished elementary types: Fourier transforms, quadratic phase gates, and automorphism gates. Combined with earlier results on classical simulation of normalizer circuits, this implies a generalized Gottesman-Knill-type result. We additionally provide circuits for a universal quantum computing scheme based on local two-qudit G -Clifford gates and magic states.

Quantum Information and Computation•Mar 1, 2026•0 citations

Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?

Mark D Penney, Dax Enshan Koh, Robert W Spekkens

It is straightforward to compute the transition amplitudes of a quantum circuit using the sum-over-paths methodology when the gates in the circuit are balanced, where a balanced gate is one for which all non-zero transition amplitudes are of equal magnitude. Here we consider the question of whether, for such circuits, the relative phases of different discrete-time paths through the configuration space can be defined in terms of a classical action, as they are for continuous-time paths. We show how to do so for certain kinds of quantum circuits, namely, Clifford circuits where the elementary systems are continuous-variable systems or discrete systems of odd-prime dimension. These types of circuit are distinguished by having phase-space representations that serve to define their classical counterparts. For discrete systems, the phase-space coordinates are also discrete variables. We show that for each gate in the generating set, one can associate a symplectomorphism on the phase-space and to each of these one can associate a generating function, defined on two copies of the configuration space. For discrete systems, the latter association is achieved using tools from algebraic geometry. Finally, we show that if the action functional for a discrete-time path through a sequence of gates is defined using the sum of the corresponding generating functions, then it yields the correct relative phases for the path-sum expression. These results are likely to be relevant for quantizing physical theories where time is fundamentally discrete, characterizing the classical limit of discrete-time quantum dynamics, and proving complexity results for quantum circuits.

arXiv:1604.07452•New Journal of Physics•Feb 21, 2017•10 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
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ℏ\ensuremath{\hbar}\ensuremathℏ. The largest power of \ensuremathℏ\ensuremath{\hbar}\ensuremathℏ 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ℏ0{\ensuremath{\hbar}}^{0}\ensuremathℏ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ℏ1{\ensuremath{\hbar}}^{1}\ensuremathℏ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ℏ1{\ensuremath{\hbar}}^{1}\ensuremathℏ1.
We develop a path integral representation for the dynamics of quantum systems with a finite-dimensional Hilbert space, formulated entirely within a discrete phase space. Starting from the discrete Wigner function on Zd×Zd{\mathbb{Z}_d} \times {\mathbb{Z}_d}Zd​×Zd​ (ddd an odd prime) and the associated Weyl transform built from generalized displacement operators, we derive an exact kernel that propagates the discrete Wigner function in time and, by iterating its composition law through a short-time approximation, obtain a sum-over-paths expression weighted by a discrete phase-space action -- the natural finite-dimensional counterpart of Marinov's functional. For Hamiltonians linear in the phase-space coordinates and at times strictly commensurate with the lattice, the fluctuation sum collapses to a deterministic shift, realizing the discrete analog of classical Hamiltonian flow. Applying the formalism to one and to two interacting qutrits (d=3d=3d=3), we show that the full entanglement dynamics -- captured by a closed-form linear entropy valid for all times -- requires the coherent contribution of all fluctuation sectors; the boundary-term (mean-field) sector alone fails to reproduce it. For a non-stabilizer Hamiltonian, where the short-time kernel is only approximate, the time-sliced path integral converges to the exact dynamics, including the dynamical generation of Wigner negativity. We discuss implications for the semiclassical simulation of many-body spin systems and for the characterization of non-classicality through Wigner negativity.
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.
Abstract The standard stabilizer formalism provides a setting to show that quantum computations restricted to operations within the Clifford group are classically efficiently simulable: this is the content of the well-known Gottesman–Knill theorem. This work analyzes the mathematical structure behind this theorem to find possible generalizations and derivation of constraints required for constructing a non-trivial generalized Clifford group. We prove that if the closure of the stabilizing set is dense in the set of SU(d) transformations, then the associated Clifford group is trivial, consisting only of local gates and permutations of subsystems. This result demonstrates the close relationship between the density of the stabilizing set and the simplicity of the corresponding Clifford group. We apply the analysis to investigate stabilization with binary observables for qubits and find that the formalism is equivalent to the standard stabilization for a low number of qubits. Based on the observed patterns, we conjecture that a large class of generalized stabilizer states are equivalent to the standard ones. Our results provide better insights into the structure of Gottesman–Knill-type results, consequently allowing us to draw a sharper line between quantum and classical computation.
Abstract Associated to every finite abelian group G , there is a generalization of qubit Clifford group associated to G . We demonstrate that every G -Clifford gate can be decomposed into some distinguished elementary types: Fourier transforms, quadratic phase gates, and automorphism gates. Combined with earlier results on classical simulation of normalizer circuits, this implies a generalized Gottesman-Knill-type result. We additionally provide circuits for a universal quantum computing scheme based on local two-qudit G -Clifford gates and magic states.
It is straightforward to compute the transition amplitudes of a quantum circuit using the sum-over-paths methodology when the gates in the circuit are balanced, where a balanced gate is one for which all non-zero transition amplitudes are of equal magnitude. Here we consider the question of whether, for such circuits, the relative phases of different discrete-time paths through the configuration space can be defined in terms of a classical action, as they are for continuous-time paths. We show how to do so for certain kinds of quantum circuits, namely, Clifford circuits where the elementary systems are continuous-variable systems or discrete systems of odd-prime dimension. These types of circuit are distinguished by having phase-space representations that serve to define their classical counterparts. For discrete systems, the phase-space coordinates are also discrete variables. We show that for each gate in the generating set, one can associate a symplectomorphism on the phase-space and to each of these one can associate a generating function, defined on two copies of the configuration space. For discrete systems, the latter association is achieved using tools from algebraic geometry. Finally, we show that if the action functional for a discrete-time path through a sequence of gates is defined using the sum of the corresponding generating functions, then it yields the correct relative phases for the path-sum expression. These results are likely to be relevant for quantizing physical theories where time is fundamentally discrete, characterizing the classical limit of discrete-time quantum dynamics, and proving complexity results for quantum circuits.
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.