A quantum algorithm for string matching

Abstract

Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N . Our algorithm has a time complexity of $$\tilde{O}(\sqrt{N})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>̃</mml:mo> </mml:mrow> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msqrt> <mml:mrow> <mml:mi>N</mml:mi> </mml:mrow> </mml:msqrt> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , while the space complexity remains modest at O ( N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.

Topics & Concepts