  We introduce informationally complete measurements whose outcomes are
entanglement witnesses and so answer the question of how many witnesses need to
be measured to decide whether an arbitrary state is entangled or not: as many
as the dimension of the state space. The optimized witness-based measurement
can provide exponential improvement with respect to witness efficiency in
high-dimensional Hilbert spaces, at the price of a reduction in the tomographic
efficiency. We describe a systematic construction, and illustrate the matter at
the example of two qubits.
