Efficient contact tracing and testing are fundamental tools to contain the transmission of SARS-CoV-2. We used multi-agent simulations to estimate the daily testing capacity required to find and isolate a number of infected agents sufficient to break the chain of transmission of SARS-CoV-2, so decreasing the risk of new waves of infections. Depending on the non-pharmaceutical mitigation policies in place, the size of secondary infection clusters allowed or the percentage of asymptomatic and paucisymptomatic (i.e., subclinical) infections, we estimated that the daily testing capacity required to contain the disease varies between 0.7 and 9.1 tests per thousand agents in the population. However, we also found that if contact tracing and testing efficacy dropped below 60% (e.g. due to false negatives or reduced tracing capability), the number of new daily infections did not always decrease and could even increase exponentially, irrespective of the testing capacity. Under these conditions, we show that population-level information about geographical distribution and travel behaviour could inform sampling policies to aid a successful containment, while avoiding concerns about government-controlled mass surveillance.