Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm

Abstract

The Gottesman-Knill theorem established that stabilizer states and operations can be efficiently simulated classically. For qudits with 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. We show that the efficiency of both algorithms is due to the harmonic evolution in the symplectic structure of discrete phase space. The differences between the Wigner function algorithm and Aaronson-Gottesman are likely due only to the fact that the Weyl-Heisenberg group is not in $SU(d)$ for $d=2$ and that qubits have state-independent contextuality. This may provide a guide for extending the discrete Wigner function approach to qubits.

References in corpus (6)

• Hidden Variables and the Two Theorems of John Bell
• Fast simulation of stabilizer circuits using a graph state representation
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
• Semiclassical Formulation of Gottesman-Knill and Universal Quantum Computation

Cited by in corpus (10)

• Deeply inelastic scattering structure functions on a hybrid quantum computer
• Symmetric Informationally Complete Measurements Identify the Irreducible Difference between Classical and Quantum Systems
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Exponential learning advantages with conjugate states and minimal quantum memory
• Measurement Contextuality and Planck's Constant
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Grand Unification of All Discrete Wigner Functions on $d\times d$ Phase Space
• Noncontextual Pauli Hamiltonians