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•1 citation

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•13 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•2 citations

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•14 citations

Generalized Clifford groups and simulation of associated quantum circuits

Stephen R. L. Clark, Richard Jozsa, Noah Linden

Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup $G$ of $U(d)$. In particular we seek $G$ such that $G\otimes G$ has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case $d = 2$ we exhaustively treat all finite irreducible subgroups of $U(2)$ and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the $n^{\rm th}$ root of $Z$ for $n \in \N$.

arXiv:quant-ph/0701103•Quantum Information and Computation•Jan 1, 2008•29 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.
Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup GGG of U(d)U(d)U(d). In particular we seek GGG such that G⊗GG\otimes GG⊗G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2d = 2d=2 we exhaustively treat all finite irreducible subgroups of U(2)U(2)U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the nthn^{\rm th}nth root of ZZZ for n∈Nn \in \Nn∈N.