Minimum number of CNOTs for a 4-qubit increment on a planar grid

Question

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.

Answer 1

Here is the best circuit I've found. It uses 14 CNOTs.

Note that this circuit is not using a linear layout! It is placed on the grid like this:

0-A-1
  |
  3
  |
  2

Where 'A' is an ancilla initialized in the |0> state and '0','1','2','3' are the qubits making up the register (with '0' being the least significant bit).

I verified this circuit in Quirk using the channel-state duality and a known-good inverse.

If one had access to the sqrt-of-CNOT operation, the number of 2-qubit operations could be brought down to 13 by merging two CNOTs and three Ts in the bottom area into a controlled-S.

If CNOTs had an error rate of 0.5%, and all other sources of error were negligible, you could apply this circuit nearly ten times before reaching a 50% failure rate. Implying a plausible NISQ machine could "almost count to ten".