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.

Pattern matching with swaps is a well-known non-standard variant of the string matching problem in which adjacent characters of the pattern may be swapped, under the constraint that each character participates in at most one swap. This problem has received considerable attention in the stringology literature due to its applications in areas such as computational biology, error-tolerant text processing, and pattern discovery. In this paper we investigate the problem in the quantum computing model. Building upon the recently introduced framework of quantum bit-parallelism, which provides a systematic way to translate classical bit-parallel string matching algorithms into quantum circuits, we develop the first quantum algorithm for swap matching based on this paradigm. Our approach adapts the classical cross-sampling technique for swap matching into a reversible quantum procedure that simulates the evolution of two interacting automata configurations using quantum registers and bitwise quantum operations. While the resulting quantum circuit preserves the near-linear behavior of its classical counterpart in terms of circuit depth, its integration with Grover’s search enables a quadratic speedup. By embedding the verification procedure within a quantum search framework and carefully controlling the size of the search space, we obtain a quantum algorithm that solves the swap matching problem in \(\tilde{O}(\sqrt {n})\) time. This result extends the applicability of quantum bit-parallelism to non-standard string matching problems and provides further evidence that a broad class of classical text searching techniques can be systematically lifted to the quantum setting while preserving their structural efficiency.

We introduce a structure-aware hybrid classical–quantum framework for discrete binary tomography from very few projections that enables practical quantum speedups through an explicit reduction of the problem’s combinatorial complexity. Rather than directly applying quantum algorithms to the full reconstruction task, we reshape the reconstruction problem by combining continuous relaxation and constraint propagation to deterministically fix the majority of pixel values, thereby isolating a small uncertain core. This core captures the residual combinatorial structure and has size k = O(n) for n × n images, reducing the effective search space from \(2^{n^2}\) to 2k, where k = O(n) and typically k ≪ n2 in practice. This reduced formulation is inherently compatible with quantum search. In particular, the refinement phase can be mapped to a search over {0, 1}k, enabling quadratic speedups via Grover’s algorithm, as well as more refined quantum backtracking strategies such as Montanaro’s algorithm. Experimental results on four projections from binary images up to 512 × 512 pixels show that the classical component alone achieves near-linear scaling and high reconstruction accuracy (above \(99.5\%\)), significantly outperforming DART and remaining competitive with ILP approaches. Importantly, the combinatorial refinement is both sparse and selective, activating primarily on difficult instances and exploring only a small fraction of the reduced search space. These findings demonstrate that the proposed decomposition acts as an effective structure-extraction layer, bridging classical reconstruction and quantum search, and providing a concrete pathway toward scalable and practically relevant quantum-enhanced discrete tomography.

Grover’s algorithm provides a quadratic speedup for unstructured search and represents one of the most fundamental primitives of quantum computation. However, its practical performance can be sensitive to the precise choice of the iteration count, which depends on the number of marked elements. This sensitivity becomes more pronounced when the density of solutions increases, where even small inaccuracies in estimating the number of marked states may lead to overshooting of the target subspace and a corresponding drop in success probability. In this work we introduce a density-aware parametrization of Grover search in which the phase rotations of the Grover operator are computed explicitly as a function of the solution density. The resulting construction can be interpreted as a density-dependent instantiation of Høyer’s arbitrary-phase amplitude amplification framework. The resulting operator performs a controlled rotation in the two–dimensional search subspace and naturally interpolates between sparse and dense regimes of the search space. We provide a theoretical analysis of the resulting dynamics and show that the proposed parametrization stabilizes the amplification process across a wide range of solution densities. Numerical simulations demonstrate that the method maintains near–optimal success probability for densities where the standard Grover algorithm becomes unstable, while also exhibiting improved robustness with respect to errors in estimating the number of marked states. These results suggest that density-aware phase parametrizations offer a simple yet effective strategy for extending the practical applicability of Grover-style quantum search procedures.

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.

Text searching is a fundamental problem in computer science, and it finds applications in several scientific fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n . This paper introduces the quantum path parallelism approach, that is, a general strategy based on quantum computation, which is easily adapted to a variety of nonstandard text-searching problems. Our method translates a text-searching problem into an automata-based string-recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favorable conditions, our algorithm solves an approximate search problem in O ( n m log ( n ) ) -time, yielding a quadratic speed-up over classical solutions. In other cases, such a speed-up is achieved only for short patterns, i.e. whenever m = O ( log ( n ) ) . We show the flexibility of our method, giving explicit adaptations to some specific approximate string matching problems.

Similarity is an excellent example of a domain-general source of information. Even when we do not have specific knowledge of a domain, we can use similarity as a default method to reason about it Similarity also plays a significant role in psychological accounts of problem solving, memory, prediction, and categorisation. However, despite the strong presence of similarity judgments in our reasoning, a general conceptual model of similarity has yet to be agreed upon. In this paper, we propose an alternative, unifying solution in this challenge in concept research based on the recent Eliasmith's theory of biological cognition. Specifically we introduce the Semantic Pointer Model of Similarity (SPMS) which describes concepts in terms of processes involving a recently postulated class of mental representations called semantic pointers. We discuss how such model is in accordance with the main guidelines of most traditional models known in literature, on the one hand, and gives a solution to most of the criticisms against these models, on the other. We also present some preliminary experimental evaluation in order to support our theory and verify whether similarities derived by human judgments can be compatible with the SPMS.

Resolving linguistic ambiguities is a task frequently called for in human communication. In many cases, such task cannot be solved without additional information about an associated context, which can be often captured from the visual scene referred by the sentence. This type of inference is crucial in several aspects of language, communication in the first place, and in the grounding of language in perception. This paper focuses on the contextual effects of visual scenes on semantics, investigated using neural computational simulation. Specifically, here we address the problem of selecting the interpretation of sentences with an ambiguous prepositional phrase, matching the context provided by visual perception. More formally, provided with a sentence, admitting two or more candidate resolutions for a prepositional phrase attachment, and an image that depicts the content of the sentence, it is required to choose the correct resolution depending on the image's content. From the neuro-computational point of view, our model is based on Nengo, the implementation of Neural Engineering Framework (NEF), whose basic semantic component is the so-called Semantic Pointer Architecture (SPA), a biologically plausible way of representing concepts by dynamic neural assemblies. We evaluated the ability of our model in resolving linguistic ambiguities on the LAVA (Language and Vision Ambiguities) dataset, a corpus of sentences with a wide range of ambiguities, associated with visual scenes.

Unbalanced translocations are among the most frequent chromosomal alterations, accounted for 30% of all losses of heterozygosity, a major genetic event causing inactivation of tumor suppressor genes. Despite of their central role in genomic sequence analysis, little attention has been devoted to the problem of matching sequences allowing for this kind of chromosomal alteration. In this paper we investigate the approximate string matching problem when the edit operations are non-overlapping unbalanced translocations of adjacent factors. In particular, we first present a 𝒪(nm³)-time and 𝒪(m²)-space algorithm based on the dynamic-programming approach. Then we improve our first result by designing a second solution which makes use of the Directed Acyclic Word Graph of the pattern. In particular, we show that under the assumptions of equiprobability and independence of characters, our algorithm has a 𝒪(nlog²_{σ} m) average time complexity, for an alphabet of size σ, still maintaining the 𝒪(nm³)-time and the 𝒪(m²)-space complexity in the worst case. To the best of our knowledge this is the first solution in literature for the approximate string matching problem allowing for unbalanced translocations of factors.

The swap matching problem consists in finding all occurrences of a pattern x of length m in a text y of length n, allowing for disjoint local swaps of characters in the pattern. In 2003, Amir et al. solved the problem in O(nlogmlogσ) worst-case time complexity, where σ is the size of the alphabet. In recent years, much research has focused on practical solutions and efficient algorithms have been devised by means of the bit-parallel simulation of non-deterministic automata. In this paper, we present a new efficient algorithm for the swap matching problem based on character comparison and structured as a generalization of the Skip-Search algorithm for the exact string matching problem. Although our solution has a quadratic worst-case time complexity, it shows a sub-linear behaviour on average. According to experimental results, our algorithm obtains in most practical cases the best running times, when compared against the most effective solutions. The gain in speed-up, in terms of running times, is up to 48%. This makes the new algorithm one of the most efficient solutions in practical cases.