Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)

Quantum LCS in Practice: Circuits, Optimizations, and Evaluation

Riccardo Cantone, G. Falci, Simone Faro, Luigi Giannelli, Arianna Pavone, Damiano Trovato, Caterina Viola

Published Jul 11, 2026• 0 citations
Publisher

Abstract

We present a full-scale implementation and experimental evaluation of a quantum algorithm for the Longest Common Substring (LCS) problem in the circuit model, bridging the gap between recent theoretical advances and practical realization. Building upon a previously proposed \(\tilde{O}(\sqrt {n})\)-depth quantum circuit, we develop a modular implementation in Qiskit that supports non-binary alphabets and incorporates several key enhancements, including a deterministic BBHT-inspired Grover search, domain expansion via ancillary qubits to stabilize amplitude amplification, and circuit-level optimizations that reduce overhead. Our approach is validated through an extensive experimental campaign over a binary alphabet augmented with two termination symbols and length 16 demonstrating an overall accuracy of 98.4%. The results show that errors are both rare and small, with a consistent conservative bias toward underestimation, and that the algorithm maintains high performance across a wide range of input configurations. We further analyze the behavior of the algorithm under realistic noise models, showing a progressive degradation of accuracy and identifying a structural asymmetry in the error patterns induced by the oracle. These findings provide concrete evidence that circuit-based quantum algorithms for string processing can achieve reliable behavior in ideal settings, while highlighting key challenges for their deployment on noisy quantum devices.

DOI
10.1145/3806645.3816161

Related papers

Quantum algorithms for longest common and palindromic substrings in the circuit model

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ) . While these results are remarkable in the quantum query model , their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation . Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.

Theoretical Computer Science•Dec 21, 2025•1 citation

Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and $\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a $\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in $\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time, respectively.

arXiv:2309.01250•Sep 3, 2023•3 citations

Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings

Tzu-Ching Lee, Han-Hsuan Lin

We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tildeΩ(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $Ω(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.

arXiv:2411.02421•Oct 21, 2024•0 citations

Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching

Ce Jin, Jakob Nogler

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.

arXiv:2211.15945•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•23 citations

A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

Tzu-Ching Lee, Han-Hsuan Lin

We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs $\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$ time, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a $Ω(n/\log^2n)$ lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.

arXiv:2310.00966•Oct 2, 2023•0 citations

Noise-Aware Evaluation and Adaptive Optimization Level Selection for Quantum Circuits in NISQ Systems

Mahesh Babu Chittem, Varsha Sambhaje

Quantum circuit optimization plays a critical role in improving the performance of algorithms executed on noisy intermediate-scale quantum (NISQ) devices. While modern quantum compilers provide multiple optimization levels, selecting an appropriate optimization strategy remains a non-trivial task due to the complex interplay between circuit structure and hardware noise. In this work, we present a comprehensive noise-aware evaluation of quantum circuit optimization strategies using a diverse set of 33 circuits, including Quantum Fourier Transform (QFT), Grover's search, Variational Quantum Eigensolver (VQE), and randomly generated circuits. We analyze the impact of different transpiler optimization levels on circuit depth, entanglement (CNOT count), and output fidelity under a realistic depolarizing noise model. Our experimental results reveal that no single optimization level consistently yields the best performance across all circuit types. While aggressive optimization is beneficial for structured circuits such as QFT and VQE, moderate optimization levels often provide a better trade-off between circuit complexity and fidelity for unstructured or randomly generated circuits. These findings highlight that optimization-level selection is inherently dependent on circuit characteristics and cannot be effectively addressed using static or heuristic approaches alone. To address this challenge, we further propose a lightweight learning-based model that predicts the optimal optimization level based on circuit features. The model achieves an accuracy of 93.9% across the evaluated dataset, demonstrating that simple machine learning techniques can effectively approximate optimal compiler decisions without requiring exhaustive evaluation. Overall, this work provides practical insights into optimization behavior in NISQ systems and introduces a scalable approach for adaptive optimization selection, contributing toward more efficient quantum software development.

IEEE International Conference on Quantum Software (QSW)•Jul 1, 2026•0 citations
We present a full-scale implementation and experimental evaluation of a quantum algorithm for the Longest Common Substring (LCS) problem in the circuit model, bridging the gap between recent theoretical advances and practical realization. Building upon a previously proposed (\tilde{O}(\sqrt {n}))-depth quantum circuit, we develop a modular implementation in Qiskit that supports non-binary alphabets and incorporates several key enhancements, including a deterministic BBHT-inspired Grover search, domain expansion via ancillary qubits to stabilize amplitude amplification, and circuit-level optimizations that reduce overhead. Our approach is validated through an extensive experimental campaign over a binary alphabet augmented with two termination symbols and length 16 demonstrating an overall accuracy of 98.4%. The results show that errors are both rare and small, with a consistent conservative bias toward underestimation, and that the algorithm maintains high performance across a wide range of input configurations. We further analyze the behavior of the algorithm under realistic noise models, showing a progressive degradation of accuracy and identifying a structural asymmetry in the error patterns induced by the oracle. These findings provide concrete evidence that circuit-based quantum algorithms for string processing can achieve reliable behavior in ideal settings, while highlighting key challenges for their deployment on noisy quantum devices.
The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ) . While these results are remarkable in the quantum query model , their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation . Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.
Longest Common Substring and Longest Palindromic Substring in O~(n)\tilde{\mathcal{O}}(\sqrt{n})O~(n​) Time
The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring O~(n5/6)\tilde{\mathcal{O}}(n^{5/6})O~(n5/6) and O~(n)\tilde{\mathcal{O}}(\sqrt{n})O~(n​) queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a O~(n)\tilde{\mathcal{O}}(\sqrt{n})O~(n​) quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in O(nlog⁡5(n))\mathcal{O}(\sqrt{n}\log^5(n))O(n​log5(n)) and O(nlog⁡4(n))\mathcal{O}(\sqrt{n}\log^4(n))O(n​log4(n)) time, respectively.
We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs O~(n2/3/d1/6−o(1)⋅polylog(n~))\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))O~(n2/3/d1/6−o(1)⋅polylog(n~)) time, while the query lower bound for the problem is Ω~(n2/3/d1/6)\tildeΩ(n^{2/3}/d^{1/6})Ω~(n2/3/d1/6), where nnn and n~\tilde{n}n~ are the encoded and decoded length of the inputs, respectively, and ddd is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a Ω(n/log⁡2n)Ω(n/\log^2n)Ω(n/log2n) lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of PARITY\mathsf{PARITY}PARITY to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.
We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs O~(n5/6)⋅O(polylog(n~))\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))O~(n5/6)⋅O(polylog(n~)) time, where nnn and n~\tilde{n}n~ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a Ω(n/log⁡2n)Ω(n/\log^2n)Ω(n/log2n) lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of PARITY\mathsf{PARITY}PARITY to the problem.
Quantum circuit optimization plays a critical role in improving the performance of algorithms executed on noisy intermediate-scale quantum (NISQ) devices. While modern quantum compilers provide multiple optimization levels, selecting an appropriate optimization strategy remains a non-trivial task due to the complex interplay between circuit structure and hardware noise. In this work, we present a comprehensive noise-aware evaluation of quantum circuit optimization strategies using a diverse set of 33 circuits, including Quantum Fourier Transform (QFT), Grover's search, Variational Quantum Eigensolver (VQE), and randomly generated circuits. We analyze the impact of different transpiler optimization levels on circuit depth, entanglement (CNOT count), and output fidelity under a realistic depolarizing noise model. Our experimental results reveal that no single optimization level consistently yields the best performance across all circuit types. While aggressive optimization is beneficial for structured circuits such as QFT and VQE, moderate optimization levels often provide a better trade-off between circuit complexity and fidelity for unstructured or randomly generated circuits. These findings highlight that optimization-level selection is inherently dependent on circuit characteristics and cannot be effectively addressed using static or heuristic approaches alone. To address this challenge, we further propose a lightweight learning-based model that predicts the optimal optimization level based on circuit features. The model achieves an accuracy of 93.9% across the evaluated dataset, demonstrating that simple machine learning techniques can effectively approximate optimal compiler decisions without requiring exhaustive evaluation. Overall, this work provides practical insights into optimization behavior in NISQ systems and introduces a scalable approach for adaptive optimization selection, contributing toward more efficient quantum software development.