Quantum Circuit Based Longest Common Substring

Abstract

The Longest Common Substring (LCS) poses classical challenges in computer science, pivotal for string processing. Classically, the problem is tackled with linear time algorithms leveraging suffix trees. Recent breakthroughs in the quantum domain have unveiled sublinear solutions for LCS, demanding 𝒪 ̃ (𝑛2/3 ) quantum queries. Yet, these strides are tailored for the quantum query model, which treats input as a black box accessible via an oracle. In contrast, in this paper we delve into these challenges within the circuit model of computation. Here, circuit size gauges structural complexity, while depth identifies execution time on a quantum platform. As the query model complexity sets a baseline, any direct quantum circuit implementation yields a depth and size of at least Ω ̃(𝑛2/3) for LCS. The main result of this paper is the introduction of a quantum algorithm for LCS in the circuit model, which, despite its 𝒪 ̃(𝑛3/2) size, achieves a groundbreaking 𝒪 ̃(√𝑛) depth, surpassing prior solutions. Notably, our algorithm is streamlined and readily translatable into quantum protocols. Furthermore, we demonstrate its practicality through a quantum circuit implementation operating in 𝒪(√𝑛 log5(𝑛)) time-steps.