Improved quantum circuits for division

Abstract:Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve improvements in the asymptotic T-count and CNOT-count from $O(n^2)$ to $O(nm)$, and in the asymptotic T-depth from $O(n^2)$ to $O(n \log m)$, where $n$ and $m$ are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.

arXiv:2603.18110 [quant-ph]

(or arXiv:2603.18110v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2603.18110 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.