Positive Wigner functions render classical simulation of quantum computation efficient.

Area of Science:

• Quantum Information Science
• Computational Quantum Physics
• Quantum Computing Theory

Background:

• The Gottesman-Knill theorem demonstrates efficient classical simulation of quantum circuits using Clifford gates and stabilizer states.
• Wigner functions provide a phase-space representation of quantum states, with negativity often linked to quantum computational power.

Purpose of the Study:

• To identify a broader class of quantum circuits, beyond Clifford circuits, that are amenable to efficient classical simulation.
• To explore the role of Wigner function properties in determining the classical simulability of quantum computations.

Main Methods:

• Development of a simulation algorithm applicable to both continuous-variable and discrete-variable (odd prime dimensions) quantum systems.
• Analysis of quantum operations and initial states representable by positive Wigner functions.

Main Results:

• Demonstration that quantum circuits with positive Wigner functions (initial states and operations) can be efficiently simulated classically.
• Generalization of the Gottesman-Knill theorem to include systems beyond Clifford operations, provided Wigner functions remain positive.
• Algorithm enables efficient sampling from output distributions, even with sampling imperfections.

Conclusions:

• The positivity of the Wigner function is a key indicator of classical efficient simulability for quantum circuits.
• Negativity in the Wigner function is identified as a crucial resource for achieving universal quantum computation and simulation.
• This work provides a new perspective on the boundary between classical and quantum computational complexity.