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:quant-ph/0405070 · Physical Review A

Discrete Wigner functions and quantum computational speedup

Ernesto F. Galvão

Published Apr 1, 2005• 122 citations
arXivHTMLPDF

Abstract

Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] have recently defined a class of discrete Wigner functions $W$ to represent quantum states in a finite Hilbert space dimension $d$. I characterize the set ${C}_{d}$ of states having non-negative $W$ simultaneously in all definitions of $W$ in this class. For $d\ensuremath{\leqslant}5$ I show ${C}_{d}$ is the convex hull of stabilizer states. This supports the conjecture that negativity of $W$ is necessary for exponential speedup in pure-state quantum computation.

DOI
10.1103/physreva.71.042302

Related papers

Classicality in discrete Wigner functions

Cecilia Cormick, Ernesto F. Galvão, Daniel Gottesman +2 more

Gibbons et al., [Phys. Rev. A 70, 062101 (2004)] have recently defined discrete Wigner functions $W$ to represent quantum states in a Hilbert space with finite dimension. We show that such a class of Wigner functions $W$ can be defined so that the only pure states having non-negative $W$ for all such functions are stabilizer states, as conjectured by Galv\~ao, [Phys. Rev. A 71, 042302 (2005)]. We also show that the unitaries preserving non-negativity of $W$ for all definitions of $W$ in the class form a subgroup of the Clifford group. This means pure states with non-negative $W$ and their associated unitary dynamics are classical in the sense of admitting an efficient classical simulation scheme using the stabilizer formalism.

arXiv:quant-ph/0506222•Physical Review A•Jan 3, 2006•129 citations

Extrema of discrete Wigner functions and applications

Andrea Casaccino, Ernesto F. Galvão, Simone Severini B

We study the class of discrete Wigner functions proposed by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to describe quantum states using a discrete phase space based on finite fields. We find the extrema of such functions for small Hilbert-space dimensions and present a quantum-information application: a construction of quantum random-access codes. These are constructed using the complete set of phase-space point operators to find encoding states and to obtain the codes' average success rates for Hilbert-space dimensions 2, 3, 4, 5, 7, and 8.

arXiv:0805.3466•Physical Review A•Aug 7, 2008•35 citations

Non-negative discrete Wigner functions

Gross, D

We show that, on a Hilbert space of odd dimension, the only pure states to possess a non-negative Wigner function are stabilizer states. The Clifford group is identified as the set of unitary operations which preserve positivity. The result can be seen as a discrete version of Hudson's Theorem. Hudson established that for continuous variable systems, the Wigner function of a pure state has no negative values if and only if the state is Gaussian. Turning to mixed states, it might be surmised that only convex combinations of stabilizer states give rise to non-negative Wigner distributions. We refute this conjecture by means of a counter-example. Further, we give an axiomatic characterization which completely fixes the definition of the Wigner function and compare two approaches to stabilizer states for Hilbert spaces of prime-power dimensions. In the course of the discussion, we derive explicit formulas for the number of stabilizer codes defined on such systems.

•Feb 1, 2006•1 citation

Interference in discrete Wigner functions

Cecilia Cormick, Juan Pablo Paz

We analyze some features of the class of discrete Wigner functions that was recently introduced by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to represent quantum states of systems with power-of-prime dimensional Hilbert spaces. We consider ``cat'' states obtained as coherent superpositions of states with positive Wigner function; for such states we show that the oscillations of the discrete Wigner function typically spread over the entire discrete phase space (including the regions where the two interfering states are localized). This is a generic property, which is in sharp contrast with the usual attributes of Wigner functions that make them useful candidates to display the existence of quantum coherence through oscillations. However, it is possible to find subsets of cat states with a natural phase-space representation, in which the oscillatory regions remain localized. We show that this can be done for interesting families of stabilizer states used in quantum error-correcting codes, and illustrate this by analyzing the phase-space representation of the five-qubit error-correcting code.

arXiv:quant-ph/0608200•Physical Review A•Dec 22, 2006•7 citations

Negative quasi-probability as a resource for quantum computation

Victor Veitch, Christopher Ferrie, David Gross +1 more

A central problem in quantum information is to determine the minimal physical resources that are required for quantum computational speedup and, in particular, for fault-tolerant quantum computation.We establish a remarkable connection between the potential for quantum speed-up and the onset of negative values in a distinguished quasi-probability representation, a discrete analogue of the Wigner function for quantum systems of odd dimension.This connection allows us to resolve an open question on the existence of bound states for magic state distillation: we prove that there exist mixed states outside the convex hull of stabilizer states that cannot be distilled to non-stabilizer target states using stabilizer operations.We also provide an efficient simulation protocol for Clifford circuits that extends to a large class of mixed states, including bound universal states.

arXiv:1201.1256•New Journal of Physics•Nov 8, 2012•383 citations

Investigating quantum coherence from discrete Wigner function

Lin Yin, Ming‐Da Huang, Yu Ya-Fei +1 more

Quantum coherence is an essential ingredient in quantum information processing and plays an important role in quantum computation. Therefore, it is a hot issue about how to quantify the coherence of quantum states in theoretical framework. The coherence effect of a state is usually described by the off-diagonal elements of its density matrix with respect to a particular reference basis. Recently, based on the established notions from quantitative theory of entanglement, a resource theory of coherence quantification has been proposed[1,2]. In the theory framework, a proper measure of coherence should satisfy three criteria: the coherence should be zero for all incoherent state; the coherence should not increase under mixing quantum states; the coherence should not increase under incoherent operations. Then, a number of coherence measures have been suggested, such as l1 norm of coherence and the relative entropy of coherence[2]. Wigner function is known as an important tool to study the non-classical property of quantum states for continuous-variable quantum systems. It has been generalized to finite-dimensional Hilbert spaces, and named as discrete Wigner function[9-16]. The magic property of quantum states, which promotes stabilizer computation to universal quantum computation, can be generally measured by the absolute sum of the negative items (negativity sum) in the discrete Wigner function of the observed quantum states. In this paper we investigate quantum coherence from the view of discrete Wigner function. From the definition of the discrete Wigner function of the quantum systems with odd prime dimensions, for a given density matrix we analyze in phase space the performance of its diagonal and off-diagonal items. We find that, the discrete Wigner function of a quantum state contains two aspects: the true quantum coherence and the classical mixture, where the part of classical mixture can be excluded by only considering the discrete Wigner function of the diagonal items of the density matrix. Thus, we propose a possible measure method for quantum coherence from the discrete Wigner function of the off-diagonal items of the density matrix. We show that the proposed measure method satisfies the criteria (C1) and (C2) of coherence measure perfectly. For the criteria (C3), we give a numerical proof in three-dimensional quantum system. Meanwhile, we compare the proposed coherence measure with l1 norm coherence, and get an inequality relationship between them. Finally, an inequality is obtained to discuss the relation between quantum coherence and the negativity sum of discrete Wigner function, which shows that the quantum coherence is only necessary but not sufficient for quantum computation speed-up.

Acta Physica Sinica•Jan 1, 2017•2 citations
Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] have recently defined a class of discrete Wigner functions WWW to represent quantum states in a finite Hilbert space dimension ddd. I characterize the set Cd{C}_{d}Cd​ of states having non-negative WWW simultaneously in all definitions of WWW in this class. For d\ensuremath⩽5d\ensuremath{\leqslant}5d\ensuremath⩽5 I show Cd{C}_{d}Cd​ is the convex hull of stabilizer states. This supports the conjecture that negativity of WWW is necessary for exponential speedup in pure-state quantum computation.
Gibbons et al., [Phys. Rev. A 70, 062101 (2004)] have recently defined discrete Wigner functions WWW to represent quantum states in a Hilbert space with finite dimension. We show that such a class of Wigner functions WWW can be defined so that the only pure states having non-negative WWW for all such functions are stabilizer states, as conjectured by Galv\~ao, [Phys. Rev. A 71, 042302 (2005)]. We also show that the unitaries preserving non-negativity of WWW for all definitions of WWW in the class form a subgroup of the Clifford group. This means pure states with non-negative WWW and their associated unitary dynamics are classical in the sense of admitting an efficient classical simulation scheme using the stabilizer formalism.
We study the class of discrete Wigner functions proposed by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to describe quantum states using a discrete phase space based on finite fields. We find the extrema of such functions for small Hilbert-space dimensions and present a quantum-information application: a construction of quantum random-access codes. These are constructed using the complete set of phase-space point operators to find encoding states and to obtain the codes' average success rates for Hilbert-space dimensions 2, 3, 4, 5, 7, and 8.
We show that, on a Hilbert space of odd dimension, the only pure states to possess a non-negative Wigner function are stabilizer states. The Clifford group is identified as the set of unitary operations which preserve positivity. The result can be seen as a discrete version of Hudson's Theorem. Hudson established that for continuous variable systems, the Wigner function of a pure state has no negative values if and only if the state is Gaussian. Turning to mixed states, it might be surmised that only convex combinations of stabilizer states give rise to non-negative Wigner distributions. We refute this conjecture by means of a counter-example. Further, we give an axiomatic characterization which completely fixes the definition of the Wigner function and compare two approaches to stabilizer states for Hilbert spaces of prime-power dimensions. In the course of the discussion, we derive explicit formulas for the number of stabilizer codes defined on such systems.
We analyze some features of the class of discrete Wigner functions that was recently introduced by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to represent quantum states of systems with power-of-prime dimensional Hilbert spaces. We consider ``cat'' states obtained as coherent superpositions of states with positive Wigner function; for such states we show that the oscillations of the discrete Wigner function typically spread over the entire discrete phase space (including the regions where the two interfering states are localized). This is a generic property, which is in sharp contrast with the usual attributes of Wigner functions that make them useful candidates to display the existence of quantum coherence through oscillations. However, it is possible to find subsets of cat states with a natural phase-space representation, in which the oscillatory regions remain localized. We show that this can be done for interesting families of stabilizer states used in quantum error-correcting codes, and illustrate this by analyzing the phase-space representation of the five-qubit error-correcting code.
A central problem in quantum information is to determine the minimal physical resources that are required for quantum computational speedup and, in particular, for fault-tolerant quantum computation.We establish a remarkable connection between the potential for quantum speed-up and the onset of negative values in a distinguished quasi-probability representation, a discrete analogue of the Wigner function for quantum systems of odd dimension.This connection allows us to resolve an open question on the existence of bound states for magic state distillation: we prove that there exist mixed states outside the convex hull of stabilizer states that cannot be distilled to non-stabilizer target states using stabilizer operations.We also provide an efficient simulation protocol for Clifford circuits that extends to a large class of mixed states, including bound universal states.
Quantum coherence is an essential ingredient in quantum information processing and plays an important role in quantum computation. Therefore, it is a hot issue about how to quantify the coherence of quantum states in theoretical framework. The coherence effect of a state is usually described by the off-diagonal elements of its density matrix with respect to a particular reference basis. Recently, based on the established notions from quantitative theory of entanglement, a resource theory of coherence quantification has been proposed[1,2]. In the theory framework, a proper measure of coherence should satisfy three criteria: the coherence should be zero for all incoherent state; the coherence should not increase under mixing quantum states; the coherence should not increase under incoherent operations. Then, a number of coherence measures have been suggested, such as l1 norm of coherence and the relative entropy of coherence[2]. Wigner function is known as an important tool to study the non-classical property of quantum states for continuous-variable quantum systems. It has been generalized to finite-dimensional Hilbert spaces, and named as discrete Wigner function[9-16]. The magic property of quantum states, which promotes stabilizer computation to universal quantum computation, can be generally measured by the absolute sum of the negative items (negativity sum) in the discrete Wigner function of the observed quantum states. In this paper we investigate quantum coherence from the view of discrete Wigner function. From the definition of the discrete Wigner function of the quantum systems with odd prime dimensions, for a given density matrix we analyze in phase space the performance of its diagonal and off-diagonal items. We find that, the discrete Wigner function of a quantum state contains two aspects: the true quantum coherence and the classical mixture, where the part of classical mixture can be excluded by only considering the discrete Wigner function of the diagonal items of the density matrix. Thus, we propose a possible measure method for quantum coherence from the discrete Wigner function of the off-diagonal items of the density matrix. We show that the proposed measure method satisfies the criteria (C1) and (C2) of coherence measure perfectly. For the criteria (C3), we give a numerical proof in three-dimensional quantum system. Meanwhile, we compare the proposed coherence measure with l1 norm coherence, and get an inequality relationship between them. Finally, an inequality is obtained to discuss the relation between quantum coherence and the negativity sum of discrete Wigner function, which shows that the quantum coherence is only necessary but not sufficient for quantum computation speed-up.