Delta-Based Rare Pattern Discovery with Quantum Speedup

Detecting rare and structurally meaningful patterns in time series is challenging, particularly when such patterns do not repeat exactly but exhibit variability due to noise or intrinsic dynamics. We introduce a novel framework for rare pattern discovery based on a combinatorial notion of approximate similarity over discretized signals. Our approach represents substrings through their local variations and defines pattern rarity in terms of the number of substrings that exhibit a similar evolution, using a tolerant Hamming distance over discrete differences. This delta-based representation captures structural behaviors such as bursts, trends, and oscillations, while providing robustness to noise and invariance to absolute signal levels, making it particularly suitable for real-world data such as astrophysical time series. We show that the resulting optimization problem is inherently quadratic in the classical setting, as it requires global pairwise comparisons between substrings and does not admit efficient incremental evaluation. To address this limitation, we propose a quantum approach that combines approximate counting and minimum finding, reducing the complexity from O(n2k) to O(nk) and achieving a quadratic speedup in the sequence length. Our results identify a natural regime in which combinatorial pattern discovery aligns with the strengths of quantum algorithms, opening new directions for the analysis of complex temporal signals.