The scheme of quantum computation with magic states, and in particular the role of the Wigner function as an indicator of quantumness, motivate the question of when Clifford-covariant Wigner functions exist, and when Wigner functions exist that represent Pauli measurements positively. This question has been settled affirmatively for all odd dimensions. Here, we discuss the case of even dimension, for Wigner functions obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurement cannot be positively represented by them in any even dimension whenever the number of qudits is n >= 2.
The scheme of quantum computation with magic states, and in particular the role of the Wigner function as an indicator of quantumness, motivate the question of when Clifford-covariant Wigner functions exist, and when Wigner functions exist that represent Pauli measurements positively. This question has been settled affirmatively for all odd dimensions. Here, we discuss the case of even dimension, for Wigner functions obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurement cannot be positively represented by them in any even dimension whenever the number of qudits is n >= 2.
A web of cohomological facts relates quantum error correction, measurement-based quantum computation, symmetry protected topological order and contextuality. Here we extend this web to quantum computation with magic states. In this computational scheme, the negativity of certain quasiprobability functions is an indicator for quantumness. However, when constructing quasiprobability functions to which this statement applies, a marked difference arises between the cases of even and odd local Hilbert space dimension. At a technical level, establishing negativity as an indicator of quantumness in quantum computation with magic states relies on two properties of the Wigner function: their covariance with respect to the Clifford group and positive representation of Pauli measurements. In odd dimension, Gross' Wigner function – an adaptation of the original Wigner function to odd-finite-dimensional Hilbert spaces – possesses these properties. In even dimension, Gross' Wigner function doesn't exist. Here we discuss the broader class of Wigner functions that, like Gross', are obtained from operator bases. We find that such Clifford-covariant Wigner functions do not exist in any even dimension, and furthermore, Pauli measurements cannot be positively represented by them in any even dimension whenever the number of qudits is n ≥ 2. We establish that the obstructions to the existence of such Wigner functions are cohomological.
An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd. The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space. The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.
The Wigner function provides a useful quasiprobability representation of quantum mechanics, with applications in various branches of physics. Many nice properties of the Wigner function are intimately connected with the high symmetry of the underlying operator basis composed of phase point operators: any pair of phase point operators can be transformed to any other pair by a unitary symmetry transformation. We prove that, in the discrete scenario, this permutation symmetry is equivalent to the symmetry group being a unitary 2 design. Such a highly symmetric representation can only appear in odd prime power dimensions besides dimensions 2 and 8. It suffices to single out a unique discrete Wigner function among all possible quasiprobability representations. In the course of our study, we show that this discrete Wigner function is uniquely determined by Clifford covariance, while no Wigner function is Clifford covariant in any even prime power dimension.
Magic -- the resource enabling quantum computational advantage beyond stabilizer circuits -- has a clean phase-space characterization in odd prime dimensions that qubits notoriously lack. We study C(rho), the l_1 distance from a state's discrete Wigner function to the stabilizer polytope, and determine its exact geometry. For a single qubit with Bloch vector r we prove the closed form C = max(0, ||r||_1 - 1)/2, so the maximum is (sqrt(3)-1)/2, attained at the eight face states. For products of single-qubit states, C(rho_1 x ... x rho_n) <= prod_i (1 + C(rho_i)) - 1, with equality whenever every factor has Bloch sign product r_x r_y r_z <= 0; this includes the exact tensor powers ((1+sqrt(3))/2)^n - 1 and the exact maximum of C over fully separable n-qubit states.
Because no discrete Wigner function for qubits is Clifford covariant, any such measure is frame dependent, and we identify which of its features are not. For a single qubit there are exactly two valid frames up to phase-space translation and C is identical on both. Pauli-covariant two-qubit frames number 2048 up to translation, and across them the ratio C(rho_Rx)/C(rho_Ry) takes the values 1/2, 1 and 2. In every one of these frames some stabilizer state has negative Wigner entries, a consequence of the Mermin-Peres square, so the two-qubit bound Gamma >= 1 + C/2 against the robustness of magic Gamma is frame independent.
Within the Wootters frame we prove integer values 1, 2, 1 of the tightness ratio kappa := (Gamma-1)/C for three families in the two-qubit repetition codespace, with explicit certificates. For n-qubit GHZ phase states we prove Gamma = |sin phi| + |cos phi| for all n and C >= 2^(floor(n/2)-1) (|sin phi| + |cos phi| - 1), tight for n = 2 and, by exact linear programming, for n = 3, 4, so kappa decays exponentially. Finally, C is not a magic monotone, so it cannot replace Gamma in distillation bounds.
We present the generalization of the CNC formalism, based on closed and noncontextual sets of Pauli observables, to the setting of odd-prime-dimensional qudits. By introducing new CNC-type phase space point operators, we construct a quasiprobability representation for quantum computation which is covariant with respect to the Clifford group and positivity preserving under Pauli measurements, and whose nonnegative sector strictly contains the subtheory of quantum theory described by nonnegative Wigner functions. This allows for a broader class of magic state quantum circuits to be efficiently classically simulated than those covered by the stabilizer formalism and Wigner function methods.
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.