An Efficient Quantum Algorithm for Preparing Uniform Superpositions over Arbitrary Integer Intervals

We consider exact preparation of the uniform quantum state supported on an arbitrary nonempty interval of integer labels in an n-qubit register. For every 0leq a<a+Mleq2^n, we give an ancilla-free circuit using only one-qubit gates and singly controlled one-qubit gates. In the logical gate model specified in the paper, the direct construction has exact worst-case gate count 5n-9 for ngeq3; its exact maxima for n=1 and n=2 are 1 and 3, respectively. A worst-case lower bound of Ω(n) establishes asymptotic optimality in the register width. In addition, the gate complexity admits an instance-dependent bound O(log_2 M+ε), where ε is an offset-dependent parameter defined in terms of binary Hamming weights. We also derive a reflected construction and a classical procedure that selects the lower-count exact circuit. The direct construction admits an O(n) logical-depth upper bound. We also treat bitwise-XOR images of intervals and arithmetic progressions with power-of-two spacing.