  With the advance of quantum information technology, the question of how to
most efficiently test quantum circuits is becoming of increasing relevance.
Here we introduce the statistics of lengths of measurement sequences that
allows one to certify entanglement across a given bi-partition of a multi-qubit
system over the possible sequence of measurements of random unknown states, and
identify the best measurement strategies in the sense of the (on average)
shortest measurement sequence of (multi-qubit) Pauli measurements. The approach
is based on the algorithm of truncated moment sequences that allows one to deal
naturally with incomplete information, i.e. information that does not fully
specify the quantum state. We find that the set of measurements corresponding
to diagonal matrix elements of the moment matrix of the state are particularly
efficient. For symmetric states their number grows only like the third power of
the number $N$ of qubits. Their efficiency grows rapidly with $N$, leaving
already for $N=4$ less than a fraction $10^{-6}$ of randomly chosen entangled
states undetected.
