# Quantum jumbled pattern matching

arXiv: https://arxiv.org/abs/2203.00164 · HTML: https://mlsanity.com/paper/2203.00164/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2022.

## Built on by (most cited first, 1 of 1)

- [Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection](https://mlsanity.com/paper/2601.09577/) (2026)

## Abstract (arXiv)

Let S1, S2 ∈ Sigma^* strings, we say that S1 em jumble match S2 if they are permutations of each other. Given a text T of size N and a string S ∈ Sigma^*, the problem of Jumbled Pattern Matching (JPM) is to determine all substrings in T jumbled matching S. In classical computing, a widespread conjecture is that JPM requires Omega(N2-ε) preprocessing time and space for O(1) query time, or Omega(N1-δ) query time in the online version, with ε, δ >0. In this paper, we present a quantum algorithm for the online JPM in O(√N) time.