Pattern Matching Using Sliding Windows on Quantum Computers

Quantum hardware is progressing rapidly, but many high-performance algorithms are not yet feasible due to data embedding overhead and the limitations of NISQ devices. Quantum pattern matching algorithms, which on average outperform classical methods [26], rely on binary quantum embeddings and are not practical until we have larger qubit counts and fault-tolerant quantum computers. Although recent progress has reduced the overhead of amplitude encoding, there is still a lack of intermediate pattern matching algorithms that are efficient in terms of qubit usage. In this work, we introduce a sliding window template matching approach and explore suitable quantum primitives, including the standard and destructive swap tests, as well as the classical shadow method and the usage of a quantum artificial neuron, all of which have been performed, and evaluate their performance on NISQ devices. We integrate the swap test into a hybrid quantum support vector machine (QSVM) with a sliding window approach, improving noise resilience in quantum image template matching. We also illustrate, that our proposed methods are hardware-efficient, easy to implement, and suitable for near-term quantum devices.