Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging

The Fredkin and Toffoli gates are at the heart of the original proposal of reversible classical computation, having found widespread use in many quantum algorithms such as the swap test and Grover search, to name only two. This made it imperative early on to pursue their efficient unitary decomposition in terms of the lower level gate sets and connectivity constraints native to different physical platforms. Recently, we developed a ZX-calculus-based circuit optimization technique capable of producing several CNOT-count-optimal logically equivalent circuits with different entanglement structures. In this talk, we will describe how we applied our automated method to decompose Fredkin and Toffoli gates under all-to-all and linear qubit connectivities, the latter with two different routings for control and target qubits. Besides achieving the lowest CNOT-counts in the literature for all of these configurations, we introduce several circuits and demonstrate their effectiveness at mitigating coherent errors via equivalent circuit averaging. For that, we quantify the robustness of the procedure in terms of the diamond distance to the target unitary by considering biased-CNOT gate models recently proposed to capture correlated errors in transmon-based hardware, before validating our method experimentally. Importantly, we also consider the case where the three qubits on which the Toffoli or Fredkin gates act are not adjacent, proposing a novel scheme to reorder the qubits that saves one CNOT for every swap. Our results highlight the importance of considering different entanglement structures and connectivity constraints when designing efficient quantum circuits.