A promising route towards the demonstration of near-term quantum advantage (or supremacy) over classical systems relies on running tailored quantum algorithms on noisy intermediate-scale quantum machines. These algorithms typically involve sampling from probability distributions that—under plausi…