Depth Optimization of FLT-Based Quantum Inversion Circuit

Works on quantum computing and cryptanalysis have increased significantly in the past few years. Various constructions of quantum arithmetic circuits as one of the primary elements in the field have also been proposed. However, there have only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor’s algorithm for Elliptic Curve Discrete Logarithm Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat’s Little Theorem (FLT)-based inversion circuit for the binary finite field. In particular, we propose to follow a complete waterfall approach to translate the Itoh-Tsujii’s variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (i.e., CNOT count) as well as slightly reducing the $T$ depth, which contributes to a reduced overall depth and gate count. Furthermore, we concretely verify our method and compare it with the previous work in Qiskit, a quantum computer simulation environment, by constructing both our method and the previous work from scratch and performing the resource analysis. Additionally, we propose employing the relative-phase Toffoli gate by Gidney as opposed to the standard Toffoli implementation, which yields a significantly lower $T$ depth while further reducing the overall depth. Our approach can serve as an alternative for a time-efficient implementation.