I want to decompose a Toffoli gate into CNOTs and arbitrary single-qubit gates. I want to minimize the number of CNOTs. I have a locality constraint: because the Toffoli is occurring in a linear array, the two controls are not adjacent to each other (so no CNOTs directly between the controls).
What is the minimum number of CNOTs required to perform this task? What is an example of a circuit which achieves this minimum?
To be specific, this is the layout I have in mind:
1 ---@--- | 2 ---X--- | 3 ---@---
Each control is adjacent to the target, but the controls are not adjacent to each other.