Recently I've been wondering how high NISQ machines will be able to "count". What I mean by that is, given the most optimized increment circuit you can make, how many times can you physically apply that circuit to qubits in a secret initial state before there's a more than 50% chance that the output is the wrong value.
To that end, I need a good increment circuit that would actually run on a NISQ machine! E.g. this means respecting locality constrains, and costing the circuit based on how many 2-qubit operations are performed (since those are the noisiest). For simplicity, I will say that the gate set is "any single qubit operation + local CNOTs on a grid".
It seems clear to me that a NISQ machine should be able to apply a 3-qubit incrementer at least 8 times (so it wraps back to 0 and loses count), but I think wrapping a 4-qubit counter is much more challenging. Thus this question's focus on that size specifically.
A 4-qubit incrementer is a circuit which effects the state permutation $|k\rangle \rightarrow |k + 1\pmod{16}\rangle$. The value $k$ must be stored as a 2s complement binary integer in four qubits. If the value is under superposition, it must still be coherent after applying the incrementer (i.e. no entangling with other qubits except as temporary workspace). You may place the qubits wherever you want on the grid.