  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 ${\approx}7\epsilon n/5$, where $n$ is the number
of qubits and $\epsilon$ 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 3X 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.
