Approximate implementations of diagonal unitary matrices with one ancillary qubit and application to first-quantized Hamiltonian simulation

In many quantum algorithms, including Hamiltonian simulation, efficient quantum circuit implementation of diagonal unitary matrices is an important issue. For small unitary diagonal matrices, a method based on Walsh operators is known and allows an exact implementation. On the other hand, as the matrix size increases, the required resources for the exact one increase linearly regarding the matrix size, so an efficient approximate implementation is indispensable.

In this work, we specify the approximation using piecewise polynomials when the diagonal unitary matrix is generated by a known underlying function. In addition to restating some previous methods, we propose a novel method. By introducing a coarse-graining parameter, calculated from the underlying function and the desired error bound, we evaluate the explicit gate counts for different methods as functions of some norms of the given function, grid parameter and error bound. It helps us to figure out the efficient quantum circuits in practical settings of different grid parameters and error bounds beyond an asymptotic speedup when the error bound goes to zero. Moreover, we apply our methods to implement the real-time evolution operator for the potential part in first-quantized Hamiltonian simulation and estimate the resources (gate count and ancillary qubits) regarding the error bound, etc. It indicates that the error coming from the approximation of the potential function is not negligible compared to the error from the Trotter-Suzuki formula.