Optimally delegated diagonal and magnitude approximation of single qubit rotations within a quantum circuit

Transpiling arbitrary quantum circuits using a finite universal gate set requires gates outside of the gate set to be approximated. [arXiv:2203.10064] show that "magnitude approximation" of single qubit Pauli rotations up to residual rotations before and after the result is less expensive in terms of sequence length than standard "diagonal approximation". When three Pauli rotations appear consecutively in a quantum circuit, the central one can be approximated using magnitude approximation and the residuals can be absorbed into its neighbors. In this work, we consider the problem of delegation of magnitude vs. diagonal approximation of rotations within a large quantum circuit. Despite the configuration space scaling exponentially with circuit volume, we develop an algorithm which finds the optimal solution in linear time. This is done by mapping the problem to a classical 1d Ising model with a spatially varying field. We benchmark our algorithm on random quantum circuits with rotations and Clifford gates and achieve savings of 26% compared with the choice of all diagonal approximations.