PaperlayerView exact revision on arXiv

Source-linked AI summary

Positive Wigner functions render classical simulation of quantum computation efficient

A. Mari, J. Eisert

arXiv:1208.3660v2quant-ph

TL;DR

The paper asks when general continuous- or discrete-variable quantum circuits can be efficiently classically simulated, including mixed states and non-unitary gates. It constructs a classical stochastic sampling procedure and shows that positive-Wigner-function circuit elements permit efficient sampling, with errors scaling favorably under approximate implementation.

  • Problem

    The problem is to classically simulate general non-adaptive quantum circuits efficiently in the number of constituents n and circuit depth t, including mixed initial states and non-unitary gates.

  • Method

    The paper represents the simulation as a classical stochastic process whose sampled outcomes are equivalent to quantum-circuit outcomes, using the shared phase-space formalism for discrete and continuous systems.

  • Results

    For any n and t, circuits with positive Wigner-function elements can be sampled classically in poly(n, t) time, and approximate implementations yield output error bounded by ε poly(n, t).

  • Takeaways & Limitations

    The result treats Wigner-function negativity as a computational resource and generalizes the Gottesman-Knill theorem to continuous and discrete systems on the same footing.

  • Takeaways & Limitations

    Positive Wigner functions do not exclude universality when circuit elements are individually arbitrarily close to positive or identity operations, including encoded schemes.

Abstract

from arXiv · show

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 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 simulatable 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.

DISCRETE AND CONTINUOUS PHASE SPACES

The paper develops a unified phase-space framework for discrete systems of odd prime dimension and continuous-variable systems. Weyl operators and a shared notation represent both settings.

  • DISCRETE AND CONTINUOUS PHASE SPACES: For odd-prime discrete systems, a single-system phase space is the lattice Z_d × Z_d.The local dimension d is assumed to be an odd prime to avoid technicalities, though arbitrary odd dimensions can be treated similarly.
  • DISCRETE AND CONTINUOUS PHASE SPACES: Continuous-variable systems use phase space R^2 for one mode, with canonical position and momentum quadratures Q and P.Their Weyl operators use standard arithmetic and yield the familiar displacement operator of quantum optics.
  • DISCRETE AND CONTINUOUS PHASE SPACES: A common notation is introduced so discrete and continuous phase-space representations can be handled on the same footing.Table I provides symbols valid in both settings, with size(r) accounting for local subsystems in sums or integrals.
  • DISCRETE AND CONTINUOUS PHASE SPACES: The Wigner function maps operators to real functions on discrete or continuous phase space using Weyl operators and parity.For n systems, the discrete domain is Z_d^2n, while the continuous domain is R^2n.

Properties of the Wigner function

The Wigner function is a normalized phase-space analogue that may be negative. Positivity characterizes Gaussian and stabilizer pure states but extends beyond their convex mixtures for mixed states.

  • Properties of the Wigner function: The Wigner function of a state is normalized and need not be positive throughout phase space.Its possible negativity distinguishes it from an ordinary classical phase-space distribution.
  • Properties of the Wigner function: For continuous systems, Hudson’s theorem restricts pure states with positive Wigner functions to Gaussian states.For odd-dimensional discrete systems, the corresponding pure states are stabilizer states.
  • Properties of the Wigner function: Clifford operations in discrete systems and Gaussian operations in continuous systems preserve the Gaussian or stabilizer form of positive Wigner functions.These operations admit descriptions through positive Gaussian Wigner functions.
  • Properties of the Wigner function: Mixed states with positive Wigner functions include convex combinations of Gaussian and stabilizer states, but the full positive class is larger.Some positive-Wigner mixed states cannot be represented as such convex combinations, and the same broader phenomenon occurs for operations.
  • Properties of the Wigner function: The paper treats positivity of states, operations, and measurements as a broader setting than Gaussianity and connects Wigner negativity with computational resource.The method is explicitly independent of Gaussianity properties.

Operations having positive Wigner functions

Quantum operations are represented through Choi matrices and their Wigner functions. Positivity makes the operation’s phase-space representation stochastic, enabling the sampling construction.

  • Operations having positive Wigner functions: A completely positive map is assigned a Choi matrix, whose positive Wigner function defines an operation with positive Wigner representation.The Choi matrix is positive because the map is completely positive.
  • Operations having positive Wigner functions: Partial transposition and partial trace connect applying an operation to a state with the operation’s Choi matrix.The phase-space formulation preserves this relationship.
  • Operations having positive Wigner functions: For trace-preserving operations, a positive Choi representation yields a classical stochastic matrix in phase space.This stochastic interpretation is the key property used by the classical sampling algorithm.
  • Operations having positive Wigner functions: Continuous-variable operations can also have non-trace-class Choi matrices, including the identity operation, represented in the sense of distributions.The identity operation has corresponding discrete and continuous phase-space representations.
  • Operations having positive Wigner functions: Clifford and Gaussian unitaries are important positive-Wigner operations because they map Weyl operators to Weyl operators under conjugation.The covered setting also includes convex combinations of Clifford/Gaussian operations.

Measurements with positive Wigner functions

Measurements are represented by the Wigner functions of their POVM elements. When these functions are positive, they define conditional outcome probabilities over phase-space points.

  • Measurements with positive Wigner functions: A general single-system measurement is described by POVM elements whose Wigner functions are defined on discrete or continuous phase space.The POVM elements satisfy a completeness relation.
  • Measurements with positive Wigner functions: For a state ρ, the probability of outcome k is obtained from the trace of ρ with the corresponding measurement operator.The construction applies to measurements on individual tensor factors.
  • Measurements with positive Wigner functions: If the scaled Wigner functions c^2W_Mk are positive, they can be interpreted as probabilities for outcome k at each phase-space point r.This conditional-probability interpretation is crucial to the simulation algorithm.

STATEMENT OF THE PROBLEM

The paper formulates classical simulation as sampling output strings from non-adaptive quantum circuits with product inputs, local channels, and local measurements. Efficiency is required to scale polynomially with circuit depth and number of constituents.

  • Circuit model: The circuit begins with an initial product state across n constituents.
  • Circuit model: A sequence of trace-preserving channels is applied, with each channel acting on at most m subsystems.
  • Circuit model: Each subsystem is finally measured using a local projective positive operator-valued measure.
  • Simulation objective: The classical algorithm should run in polynomial time in the number of constituents n and circuit depth t.
  • Simulation objective: The simulation task is to sample outcome lists from approximately the same distribution as the quantum circuit.

Phase space representation

The circuit is rewritten in phase space as a sequential composition of Wigner functions for the product input, gates, and local measurements. This representation is formally equivalent to the operator description.

  • State representation: The product input state has a factorized Wigner function over its subsystems.
  • Operation representation: Each gate is represented by the Wigner function of its Choi matrix after partial transposition.
  • Measurement representation: Measurement outcomes are represented by local POVM Wigner functions evaluated at the corresponding subsystem phase-space coordinates.
  • Circuit representation: Sequential application of the phase-space rules yields an expression for the circuit’s outcome probabilities.
  • Circuit representation: The phase-space description is formally equivalent to the operator representation and initially imposes no resource-positivity assumption.

EFFICIENT CLASSICAL SIMULATION

When input states, gates, and measurements have positive Wigner representations, the quantum circuit becomes a classical stochastic process. The resulting sampler runs in polynomial time in n and t and can accommodate adaptive later steps.

  • Positivity assumptions: Positive Wigner functions for input states, gates, and POVMs allow all algorithmic functions to be interpreted as probability distributions.
  • Efficiency: For any n and t, the output distribution can be sampled classically in poly(n, t) time.
  • Sampling procedure: The algorithm samples an initial phase-space point from the input Wigner function.
  • Sampling procedure: At each gate step, it samples a new phase-space point from the gate-associated distribution.
  • Efficiency: Locality makes gate updates efficient because only at most m subsystem coordinates are resampled while complementary coordinates remain invariant.
  • Scope: The method cannot be applied when the required Wigner-function positivity condition fails, although adaptive later steps can be handled.

ROBUSTNESS TO SAMPLING ERRORS

The sampling algorithm is robust to imperfect representations of states, operations, and measurements. Under bounded local and gate-distribution errors, it efficiently samples an output distribution close to the ideal one.

  • Error model: The robustness analysis replaces ideal states, gates, and POVM elements with imperfect versions arising from approximate Wigner-function sampling.
  • Error model: Gate sampling errors are represented by differences between ideal stochastic matrices Q(k) and approximations Q′(k).
  • Guarantee: If each local state error and each gate-matrix error is bounded by ε, the approximate circuit can be sampled in poly(n, t) time.
  • Guarantee: The resulting output distributions satisfy ∥P − P′∥∞ < ε poly(n, t).
  • Analysis: The bound is derived by repeatedly applying the triangle inequality and norm inequalities to accumulated sampling errors.

SUMMARY AND OUTLOOK

Universal quantum computation can be implemented with circuit elements whose Wigner functions are arbitrarily close to positive, but accumulated errors eventually become unbounded in unbounded computations. The work therefore identifies quantifying Wigner-function negativity as an important direction for a resource theory.

  • SUMMARY AND OUTLOOK: For every ε > 0, universal quantum circuits can use positive-Wigner initial states and gates, measurements, and other elements arbitrarily close to positive.The construction is given for d = 3 and uses local gates supported on a constant number of sites.
  • SUMMARY AND OUTLOOK: Diluting gates and encoding outputs allows universal circuits to use gates and POVMs arbitrarily close to the identity operation.The same observation is also connected to encoded cluster-state constructions.
  • SUMMARY AND OUTLOOK: Although implementation errors may grow slowly, they grow beyond all bounds in an unbounded computation using imperfect gates.
  • SUMMARY AND OUTLOOK: The authors identify meaningful quantification of Wigner-function negativity as a fruitful target for a resource theory.They compare this prospective development with resource theories in entanglement and statistical physics.
  • SUMMARY AND OUTLOOK: The work concludes that positive-Wigner circuit elements permit efficient sampling, generalizing Gottesman–Knill sampling to continuous and discrete systems on the same footing.The conclusion also states that approximate gate implementation remains efficiently sampleable when errors scale favorably.

Preparation of random variables with given Wigner functions

The sampling procedure generates phase-space points from non-negative Wigner functions using standard distribution-sampling methods. Uniform random variables are transformed so that the resulting points follow the target Wigner function.

  • Preparation of random variables with given Wigner functions: Standard rejection sampling or inverse-transform sampling can draw phase-space points from given non-negative Wigner functions.The discussion applies explicitly to continuous phase spaces, with analogous reasoning for discrete systems.
  • Preparation of random variables with given Wigner functions: The target Wigner function is represented through its cumulative distribution function over phase-space coordinates.
  • Preparation of random variables with given Wigner functions: Given uniformly distributed random variables, the construction produces phase-space variables distributed according to Wρ.
Loading 1208.3660v2…