Skip to content
Preprint

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

Nov 2026 · 0 citations · 44 references
Physics

Abstract

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 $0\leq a<a+M\leq2^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 $n\geq3$; its exact maxima for $n=1$ and $n=2$ are $1$ and $3$, respectively. A worst-case lower bound of $\Omega(n)$ establishes asymptotic optimality in the register width. In addition, the gate complexity admits an instance-dependent bound $O(\log_2 M+\epsilon)$, where $\epsilon$ 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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.