  Negativity of the Wigner function is arguably one of the most striking
non-classical features of quantum states. Beyond its fundamental relevance, it
is also a necessary resource for quantum speedup with continuous variables. As
quantum technologies emerge, the need to identify and characterize the
resources which provide an advantage over existing classical technologies
becomes more pressing. Here we derive witnesses for Wigner negativity of
single-mode and multimode quantum states, based on fidelities with Fock states,
which can be reliably measured using standard detection setups. They possess a
threshold expectation value indicating whether the measured state has a
negative Wigner function. Moreover, the amount of violation provides an
operational quantification of Wigner negativity. We phrase the problem of
finding the threshold values for our witnesses as an infinite-dimensional
linear optimisation problem. By relaxing and restricting the corresponding
linear programs, we derive two converging hierarchies of semidefinite programs,
which provide numerical sequences of increasingly tighter upper and lower
bounds for the threshold values. We further show that our witnesses form a
complete family - each Wigner negative state is detected by at least one
witness - thus providing a reliable method for experimentally witnessing Wigner
negativity of quantum states from few measurements. From a foundational
perspective, our findings provide insights on the set of positive Wigner
functions which still lacks a proper characterisation.
