microsoft
IncrementByInteger should not scale O(N^2)
Problem
Semantically, IncrementByInteger is a special case of AddI, where the first argument is a classical integer. For the user, it is hence rather surprising that the specialized version is much slower (O(N^2) general rotations compared to O(N) T-gates, with N the width of the target register).
Desired solution
Replacing the current implementation of IncrementByInteger with one using the general adder would be a good short-term solution. In the longer term, a more optimized implementation taking advantage of the classical nature of one argument would be preferable.
Alternative
In case the use of N additional qubits in the proposed short-term solution is a concern, the docs for IncrementByInteger should be improved to point out the unfavorable scaling and point users to the general adders for much better scaling.
