We study the problem of matching a determinate pattern against an indeterminate text of the same length n, where each text position is a set of possible characters drawn from an alphabet Σ of size σ. We study this matching problem under the order-preserving and parameterized matching setting. For that, we encode character sets by bit expressions using sum-free sequences. This encoding enables constant-time character comparisons and avoids explicit set operations. We present an optimal 𝒪(n) time algorithm for order-preserving matching and an 𝒪(n+(σ_p^x ⋅ σ_p^y) √{σ_p^x + σ_p^y}) time algorithm for parameterized matching, where σ_p^x and σ_p^y denote the number of distinct parameterized symbols in the pattern and the text, respectively. The proposed techniques significantly reduce overhead while maintaining exactness, offering practical performance improvements for pattern matching under uncertainty. Additionally, we extend the parameterized matching framework to allow mismatches, for which we present an algorithm with time complexity 𝒪(σ² n log n + n σ² √σ log(n σ)).

Elastic-degenerate (ED) strings generalize classic strings by allowing each position to store a set of up to$h$strings of arbitrary lengths [2]. An ED string is a restricted version of a regular expression whose expressiveness still causes a combinatorial explosion of possible resolutions (i.e., the members of its language), making classical pattern matching and indexing techniques either inefficient or inapplicable. A position in an ED string is called solid if it stores a single symbol, otherwise elastic. We introduce the Min/Max wavelet tree (MM-WT), a variant of the wavelet tree supporting semantics-aware rank and select on ED strings. Each leaf stores two arrays per symbol$c, \min _{c}$and$\max _{c}$, giving for each position the minimum and maximum symbol count across all alternatives. Prefix sums bound the number of occurrences in any resolution of a prefix, so sm-rank$(c, i)$returns an interval$\left[r_{\min}, r_{\max}\right]$of possible ranks, and sm-select$(c, j)$returns an interval for the$j$-th occurrence of$c$. On classic strings, min and max collapse to the same counts and the structure becomes a standard wavelet tree. The structure uses the same space as a subset wavelet tree [1] internally, plus$\mathcal{O}(n \sigma \log h)$bits for the min/max arrays, and supports both queries in$\mathcal{O}(\log \sigma)$time.

We introduce Attractor Matching, a new framework for structural string comparison built upon the theory of string attractors. Given a pattern$x$of length$m$and one of its attractors$\Gamma_{x}$, the problem asks for all substrings$y[i. . i+m-1]$of a text$y$such that$\Gamma_{x}$is also an attractor of$y[i. . i+m-1]$. Unlike classical notions of string matching, which rely on character equality or distance measures, attractor matching focuses on the structural properties that govern repetitiveness and compressibility. Our contribution is fourfold. First, we adapt the IsAttractor algorithm of Béal et al. by combining the DAWG with the slidingwindow technique of Blumer, enabling online attractor verification as the window advances over the text. Second, we reformulate the verification procedure on the Compressed DAWG (CDAWG), obtaining a more compact representation that preserves correctness. Third, we employ the sliding-window CDAWG method of Inenaga et al., which allows efficient attractor matching on sliding-window maintained CDAWGs with incremental updates. Finally, we introduce a relaxed variant, Attractor Matching with Mismatches, where the pattern attractor may be extended by at most$\rho$additional positions, enabling structurally tolerant matching. This paradigm bridges compression and similarity, opening new directions for structure-aware pattern matching.

Ancillary qubits are an essential resource in quantum programs, yet their management often introduces artificial long-range dependencies that obscure opportunities for parallel execution. In many programming models, uncomputation is treated as a global cleanup phase appended after the forward computation, causing temporary data to remain live far beyond its semantic relevance and inflating both circuit width and scheduling constraints. Building on the lifetime-guided uncomputation discipline introduced in the quantum programming language Qutes, this paper identifies and formalizes a new form of parallelism emerging from the semantic structure of quantum programs. By precisely tracking the semantic lifetime of temporary variables, subcomputations associated with ancillas can be restored locally once their influence terminates. This mechanism exposes a form of structural parallelism that arises not from qubit disjointness or quantum superposition, but from the reduction of semantic dependencies in the program. We formalize this phenomenon through the notion of temporary regions in the circuit dependence graph and show that lifetime-guided reclamation induces a contraction of these regions, collapsing temporary subcomputations into locally closed structures. As a consequence, circuits compiled under this discipline reduce peak width through systematic ancilla reuse and improve space–time volume without increasing asymptotic depth, illustrating how high-level language semantics can reshape the structural properties of quantum circuits.

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.

Abstract Quantum computing offers transformative capabilities by exploiting quantum mechanical principles to solve problems that are intractable for classical systems, particularly in areas like cryptography, optimization, and data analysis. However, most current quantum programming languages operate at a low level, requiring in-depth expertise in quantum mechanics and circuit theory, which presents a barrier to wider adoption. In this work, we introduce Qutes, a high-level quantum programming language that simplifies the development of quantum algorithms while preserving the flexibility needed for advanced applications. Qutes abstracts low-level quantum operations through intuitive syntax and high-level constructs, enabling developers to express complex algorithms without detailed circuit knowledge. Built atop Qiskit, Qutes transpiles seamlessly into executable code, ensuring compatibility with real quantum hardware. We present the architecture, language design, and hybrid classical-quantum integration of Qutes, and demonstrate its use through implementations of canonical quantum algorithms. Our results highlight Qutes’ potential to democratize quantum programming by lowering the entry threshold and accelerating prototyping for researchers and developers alike.

Quantum computing leverages the principles of quantum mechanics to perform computations far beyond the capabilities of classical systems, particularly in fields such as cryptography and optimization. However, current quantum programming languages often require low-level implementation, posing significant barriers for many developers due to their steep learning curve and limited abstraction. In response, we introduce Qutes, a high-level quantum programming language designed to simplify quantum algorithm development while maintaining the flexibility required for advanced applications. By abstracting complex quantum operations and allowing intuitive expressions through high-level constructs, Qutes enables users to write efficient quantum programs without extensive knowledge of quantum mechanics or circuit design. Built upon Qiskit, Qutes translates its syntax directly into executable quantum code, facilitating seamless integration with quantum hardware. This paper provides an overview of the language's architecture, core functionalities, and its ability to unify classical and quantum operations within a single framework. Additionally, we demonstrate Qutes' application in key quantum algorithms, showcasing its potential to make quantum programming more accessible and practical for a wider range of developers and researchers.

Grover's algorithm offers a celebrated quadratic speedup for unstructured search problems, positioning it among the foundational tools of quantum computing. However, its effectiveness critically deteriorates when the number of valid solutions exceeds half of the total search space. In this work, we address this limitation by introducing a novel and efficient technique based on a virtual expansion of the input domain. Our approach extends the range of applicability of Grover's algorithm to high-density solution spaces, including those where the number of solutions is greater than N/2, without increasing the actual circuit depth or memory footprint. The core idea consists in appending one auxiliary qubit to the input register and modifying the oracle to mark only those solutions where the auxiliary qubit is in a fixed state. This effectively reduces the solution density in the extended space, restoring the geometric conditions required for successful amplitude amplification. We further analyze an extension of this strategy involving log n auxiliary qubits, which allows for tunable robustness at a moderate increase in computational cost. The proposed method is simple to implement on existing quantum hardware and maintains Grover's optimal asymptotic complexity in the expanded regime. Both theoretical analysis and empirical simulations confirm that our approach reliably outperforms the standard algorithm in scenarios with high solution density, thus broadening the practical utility of quantum search.