Generating samples from the output distribution of a quantum circuit is a ubiquitous task used as a building block of many quantum algorithms. Here we show how to accomplish this task on a noisy quantum processor lacking full-blown error correction for a special class of quantum circuits dominated by Clifford gates. Our approach is based on coherent Pauli checks (CPCs) that detect errors in a Clifford circuit by verifying commutation rules between random Pauli-type check operators and the considered circuit. Our main contributions are as follows. First, we derive a simple formula for the probability that a Clifford circuit protected by CPCs contains a logical error. In the limit of a large number of checks, the logical error probability is shown to approach the value ≈7ϵn/5, where n is the number of qubits and ϵ is the depolarizing error rate. Our formula agrees nearly perfectly with the numerical simulation results. Second, we show that CPCs are well suited for quantum processors with a limited qubit connectivity. For example, the difference between all-to-all and linear qubit connectivity is only a 3× increase in the number of cnot gates required to implement CPCs. Third, we describe simplified one-sided CPCs, which are well suited for mitigating measurement errors in the single-shot settings. Finally, we report an experimental demonstration of CPCs with up to 10 logical qubits and more than 100 logical cnot gates. Our experimental results show that CPCs provide a marked improvement in the logical error probability for the considered task of sampling the output distribution of quantum circuits.