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

An inspectable Grover algorithm-based amplitude-amplification workflow for k-mer discovery and motif scanning with genomic coordinate traceability

Akshay Uttarkar, Vidya Niranjan

Published Oct 13, 2026• 0 citations
Publisher

Abstract

Abstract Motif discovery and motif scanning remain core primitives in genomics, but both tasks face combinatorial growth as k-mer length increases and as mismatch-tolerant searches expand the candidate space. In this work, we present MotifQu, a Python package and command-line tool that maps two common motif-analysis workflows—(i) scanning a genome for a user-specified consensus motif and (ii) de novo discovery of recurrent k-mers above a user-defined count threshold—onto Grover-style amplitude amplification circuits executed reproducibly via Qiskit Aer statevector simulation. We evaluate MotifQu on the SARS-CoV-2 reference contig (29,903 bp) and S. cerevisiae S288C reference genome, where the classical census identifies strongly non-uniform motif frequencies dominated by A/T-rich 5-mers and returns explicit coordinate lists across the full genome span. We further execute the same logical 10-qubit search on IBM hardware showing that while end- to-end execution is feasible, transpilation-induced circuit depth and entangling-gate volume produce a diffuse measurement distribution whose probabilities remain close to the uniform 1/1024 scale, limiting observable amplitude concentration under current NISQ constraints. Finally, we demonstrate the full discovery workflow on the S. cerevisiae S288C reference genome (12,157,105 bp) to illustrate search results (ranked motifs, probability summaries, circuit diagrams, and position plots) and to highlight the regime where a large, marked set reduces the sharpness of Grover amplification.

DOI
10.64898/2026.10.09.758025

Related papers

A foundational quantum framework for multi-pattern string matching in k-mer detection

Christos Papalitsas, Ioannis Mouratidis, Michail Patsakis +3 more

Motivation: The exponential growth of publicly available genomic data has created unprecedented opportunities for sequence-based discovery. Locating specific k-mers is fundamental to diverse applications, including metagenomic classification, pathogen and cancer detection, and variant calling yet efficient identification of multiple k-mer patterns across large sequencing data and massive databases remains a significant computational challenge. Method: We implement two quantum algorithms for DNA multi-pattern string matching for k-mer detection, leveraging Grover's amplitude amplification under the idealized quantum random access memory (QRAM) framework. The first algorithm uses an enumerate-m oracle that sequentially checks a loaded text substring against all m patterns achieving O (√S) query complexity for S text positions but requiring O (m · L) work per oracle call. The second algorithm employs nested Grover search with an outer loop over text positions and an inner loop over pattern space, reducing oracle complexity to O(L) while performing O (√S · √m) in total. These asymptotic gains highlight the potential advantages that could be unlocked by future large-scale, low-noise QRAM architectures, positioning our results as a promising proof-of-concept foundation. Results: This work introduces two quantum implementations of multi-pattern string matching tailored for k-mer detection. Leveraging quantum parallelism and Grover-inspired search primitives, our methods accelerate dictionary-based pattern matching, particularly in contexts involving large sequences, such as genomic data, and extensive pattern sets. Conclusion: While implementation challenges such as QRAM overhead remain, this study demonstrates both the promise and current limitations of quantum-enhanced string matching, establishing a foundational step toward quantum readiness in bioinformatics. Availability and Implementation: To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder.

Frontiers in Bioinformatics•Jun 12, 2026•0 citations

CQ-Migrate: A Hardware-Aware Feasibility Framework for NISQ Workloads with Multi-Run Validation onTuna-17

Ravikumar Sreepada, Mahendar Gajula, Sarath Chandra Maturi

Abstract Classical-to-quantum workload migration is not a direct code-translation task because theoretical speedup, reversible mapping, circuit resources, device noise, compilation, queueing, and classical--quantum orchestration must be considered together. This work presents CQ-Migrate, a structured decision framework for determining whether a workload should remain classical, be decomposed into a hybrid workflow, or be evaluated on a quantum processing unit. Grover search is used as an empirical case study. A true two-qubit Grover circuit was validated locally, executed on the Quantum Inspire QX emulator, and then evaluated on the 17-qubit Tuna-17 superconducting processor. Four marked states were tested with five independent hardware runs per state and 1024 shots per run, totaling 20,480 hardware shots. The emulator returned the marked state in 100% of 4096 shots. Tuna-17 produced 19,076 correct measurements, corresponding to an aggregate success probability of 93.14% (95% Wilson interval: 92.79--93.48%). State-wise mean success ranged from 91.82% to 94.30%; run-level differences across marked states were statistically detectable (one-way ANOVA \((F=5.99)\), \((p=0.0062)\); Kruskal--Wallis \((H=10.88)\), \((p=0.0124)\)). The study also reports complete provider job provenance and reinterprets earlier archived IBM executions as a backend-variability control rather than a Grover validation. The results support evidence-driven, hardware-aware migration decisions without claiming practical quantum speedup for the small instance studied.

•Nov 9, 2026•0 citations

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 citations

Compositional Execution Motifs for Quantum-HPC Systems

Nishant Saurabh, Pradeep Kumar Mantha, Shantenu Jha +1 more

Although quantum hardware has made significant progress, constraints such as limited qubit counts and noise still hinder its practical impact on scientific and industrial challenges. Integrating multiple quantum processing units (QPUs) with HPC resources (e.g., GPUs and CPUs) is a promising approach. However, quantum–HPC integration introduces new complexities, including resource orchestration, workload partitioning, and quantum-classical coordination. This paper identifies emerging quantum workflow execution patterns, illustrating the interaction between quantum and classical components in hybrid quantum workflow applications. We classify these execution patterns into six basic motifs centered on simple quantum-classical interactions (e.g., circuit execution) and introduce two compositional motifs as orchestration of one or more basic motifs. The variational quantum algorithm (VQA) compositional motif captures new parallelism strategies by concurrently running classical solvers and quantum circuit evaluations. The generative quantum algorithm (GQA) compositional motif describes how GPU-accelerated AI models can generate or refine quantum circuits, which are then executed on QPUs. Characterizing these basic and compositional motifs provides a structured path toward scalable quantum–HPC middleware solutions, informing design at the task, workload orchestration, and application levels.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•0 citations

Performance Analysis of Grover’s Algorithm Under Noise: A Simulation-Driven Study with Error Mitigation and Hybrid Bloom–Grover Search

Souvik Ghosh, Amrita Kundu, Samya Muhuri

Classical database join operations are a significant performance bottleneck in data-intensive applications, typically requiring quadratic time proportional to the size of the input. Quantum search algorithms, such as Grover’s algorithm, promise asymptotic speedups for unstructured search and can be adapted to accelerate equality-based joins. In this paper, we present a systematic simulation study of a Grover-based quantum join primitive and a hybrid classical-quantum join scheme, comparing them with a baseline classical nested-loop join. Parameterised Grover circuits have been implemented for marked-item search, together with resource estimation (qubit count, circuit depth, and gate counts), using the Qiskit Aer simulator. The classical join is modelled as a nested-loop equality join over two arrays, while the hybrid scheme uses a classical Bloom filter to reduce the candidate space, followed by a Grover search over the remaining items. To approximate near term hardware, we incorporate depolarizing gate noise and readout noise via Aer noise models and investigate two mitigation techniques: readout error calibration and zero noise extrapolation. Our simulations, conducted in a Python environment without GPU acceleration, demonstrate that the Grover based and hybrid joins exhibit the expected sub-quadratic scaling in runtime compared to the classical nested-loop join for problem sizes up to N = 215. We additionally observe that realistic noise significantly degrades the raw success probability of the quantum join, while combining readout mitigation with zero noise extrapolation partially restores accuracy. These results provide a resource-aware and noise-aware baseline for evaluating quantum-accelerated joins on future fault-tolerant or high-fidelity noisy intermediate-scale quantum (NISQ) devices.

International Conference on Next-Gen Quantum and Advanced Computing: Algorithms, Security, and Beyond (NQComp)•Mar 5, 2026•0 citations

A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem

Laurin Demmler, Maximilian Hess

Amplitude Amplification offers a provable speedup for search problems, which is leveraged in combinatorial optimization by Grover Adaptive Search (GAS). The protocol demands deep circuits that are challenging with regards to NISQ capabilities. We propose a nested Amplitude Amplification protocol for the binary knapsack problem that splits the decision tree at a tunable depth, performing a partial amplification on the first variables before executing a global GAS on the full search space. The partial amplification is implemented by an Inner Iteration Finder that selects the rotation count maximizing marked-subspace amplitude. The resulting biased superposition serves as the initial state for the outer Amplitude Amplification. Using the Quantum Tree Generator for feasible-state preparation and an efficient classical amplitude-tracking scheme, we simulate the protocol on knapsack instances of sizes intractable by statevector simulation. Our results show that the nested approach reduces the cost of improving an incumbent solution compared to baseline GAS, particularly for a specific subset of knapsack instances. As combinatorial problems in domains such as semiconductor supply-chain planning grow in scale, methods that reduce circuit cost are an important step toward eventual quantum advantage for such applications.

quant-pharXiv:2604.05776•Apr 8, 2026•1 citation
Abstract Motif discovery and motif scanning remain core primitives in genomics, but both tasks face combinatorial growth as k-mer length increases and as mismatch-tolerant searches expand the candidate space. In this work, we present MotifQu, a Python package and command-line tool that maps two common motif-analysis workflows—(i) scanning a genome for a user-specified consensus motif and (ii) de novo discovery of recurrent k-mers above a user-defined count threshold—onto Grover-style amplitude amplification circuits executed reproducibly via Qiskit Aer statevector simulation. We evaluate MotifQu on the SARS-CoV-2 reference contig (29,903 bp) and S. cerevisiae S288C reference genome, where the classical census identifies strongly non-uniform motif frequencies dominated by A/T-rich 5-mers and returns explicit coordinate lists across the full genome span. We further execute the same logical 10-qubit search on IBM hardware showing that while end- to-end execution is feasible, transpilation-induced circuit depth and entangling-gate volume produce a diffuse measurement distribution whose probabilities remain close to the uniform 1/1024 scale, limiting observable amplitude concentration under current NISQ constraints. Finally, we demonstrate the full discovery workflow on the S. cerevisiae S288C reference genome (12,157,105 bp) to illustrate search results (ranked motifs, probability summaries, circuit diagrams, and position plots) and to highlight the regime where a large, marked set reduces the sharpness of Grover amplification.
Motivation: The exponential growth of publicly available genomic data has created unprecedented opportunities for sequence-based discovery. Locating specific k-mers is fundamental to diverse applications, including metagenomic classification, pathogen and cancer detection, and variant calling yet efficient identification of multiple k-mer patterns across large sequencing data and massive databases remains a significant computational challenge. Method: We implement two quantum algorithms for DNA multi-pattern string matching for k-mer detection, leveraging Grover's amplitude amplification under the idealized quantum random access memory (QRAM) framework. The first algorithm uses an enumerate-m oracle that sequentially checks a loaded text substring against all m patterns achieving O (√S) query complexity for S text positions but requiring O (m · L) work per oracle call. The second algorithm employs nested Grover search with an outer loop over text positions and an inner loop over pattern space, reducing oracle complexity to O(L) while performing O (√S · √m) in total. These asymptotic gains highlight the potential advantages that could be unlocked by future large-scale, low-noise QRAM architectures, positioning our results as a promising proof-of-concept foundation. Results: This work introduces two quantum implementations of multi-pattern string matching tailored for k-mer detection. Leveraging quantum parallelism and Grover-inspired search primitives, our methods accelerate dictionary-based pattern matching, particularly in contexts involving large sequences, such as genomic data, and extensive pattern sets. Conclusion: While implementation challenges such as QRAM overhead remain, this study demonstrates both the promise and current limitations of quantum-enhanced string matching, establishing a foundational step toward quantum readiness in bioinformatics. Availability and Implementation: To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder.
Abstract Classical-to-quantum workload migration is not a direct code-translation task because theoretical speedup, reversible mapping, circuit resources, device noise, compilation, queueing, and classical--quantum orchestration must be considered together. This work presents CQ-Migrate, a structured decision framework for determining whether a workload should remain classical, be decomposed into a hybrid workflow, or be evaluated on a quantum processing unit. Grover search is used as an empirical case study. A true two-qubit Grover circuit was validated locally, executed on the Quantum Inspire QX emulator, and then evaluated on the 17-qubit Tuna-17 superconducting processor. Four marked states were tested with five independent hardware runs per state and 1024 shots per run, totaling 20,480 hardware shots. The emulator returned the marked state in 100% of 4096 shots. Tuna-17 produced 19,076 correct measurements, corresponding to an aggregate success probability of 93.14% (95% Wilson interval: 92.79--93.48%). State-wise mean success ranged from 91.82% to 94.30%; run-level differences across marked states were statistically detectable (one-way ANOVA (F=5.99)(F=5.99)(F=5.99), (p=0.0062)(p=0.0062)(p=0.0062); Kruskal--Wallis (H=10.88)(H=10.88)(H=10.88), (p=0.0124)(p=0.0124)(p=0.0124)). The study also reports complete provider job provenance and reinterprets earlier archived IBM executions as a backend-variability control rather than a Grover validation. The results support evidence-driven, hardware-aware migration decisions without claiming practical quantum speedup for the small instance studied.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Although quantum hardware has made significant progress, constraints such as limited qubit counts and noise still hinder its practical impact on scientific and industrial challenges. Integrating multiple quantum processing units (QPUs) with HPC resources (e.g., GPUs and CPUs) is a promising approach. However, quantum–HPC integration introduces new complexities, including resource orchestration, workload partitioning, and quantum-classical coordination. This paper identifies emerging quantum workflow execution patterns, illustrating the interaction between quantum and classical components in hybrid quantum workflow applications. We classify these execution patterns into six basic motifs centered on simple quantum-classical interactions (e.g., circuit execution) and introduce two compositional motifs as orchestration of one or more basic motifs. The variational quantum algorithm (VQA) compositional motif captures new parallelism strategies by concurrently running classical solvers and quantum circuit evaluations. The generative quantum algorithm (GQA) compositional motif describes how GPU-accelerated AI models can generate or refine quantum circuits, which are then executed on QPUs. Characterizing these basic and compositional motifs provides a structured path toward scalable quantum–HPC middleware solutions, informing design at the task, workload orchestration, and application levels.
Classical database join operations are a significant performance bottleneck in data-intensive applications, typically requiring quadratic time proportional to the size of the input. Quantum search algorithms, such as Grover’s algorithm, promise asymptotic speedups for unstructured search and can be adapted to accelerate equality-based joins. In this paper, we present a systematic simulation study of a Grover-based quantum join primitive and a hybrid classical-quantum join scheme, comparing them with a baseline classical nested-loop join. Parameterised Grover circuits have been implemented for marked-item search, together with resource estimation (qubit count, circuit depth, and gate counts), using the Qiskit Aer simulator. The classical join is modelled as a nested-loop equality join over two arrays, while the hybrid scheme uses a classical Bloom filter to reduce the candidate space, followed by a Grover search over the remaining items. To approximate near term hardware, we incorporate depolarizing gate noise and readout noise via Aer noise models and investigate two mitigation techniques: readout error calibration and zero noise extrapolation. Our simulations, conducted in a Python environment without GPU acceleration, demonstrate that the Grover based and hybrid joins exhibit the expected sub-quadratic scaling in runtime compared to the classical nested-loop join for problem sizes up to N = 215. We additionally observe that realistic noise significantly degrades the raw success probability of the quantum join, while combining readout mitigation with zero noise extrapolation partially restores accuracy. These results provide a resource-aware and noise-aware baseline for evaluating quantum-accelerated joins on future fault-tolerant or high-fidelity noisy intermediate-scale quantum (NISQ) devices.
Amplitude Amplification offers a provable speedup for search problems, which is leveraged in combinatorial optimization by Grover Adaptive Search (GAS). The protocol demands deep circuits that are challenging with regards to NISQ capabilities. We propose a nested Amplitude Amplification protocol for the binary knapsack problem that splits the decision tree at a tunable depth, performing a partial amplification on the first variables before executing a global GAS on the full search space. The partial amplification is implemented by an Inner Iteration Finder that selects the rotation count maximizing marked-subspace amplitude. The resulting biased superposition serves as the initial state for the outer Amplitude Amplification. Using the Quantum Tree Generator for feasible-state preparation and an efficient classical amplitude-tracking scheme, we simulate the protocol on knapsack instances of sizes intractable by statevector simulation. Our results show that the nested approach reduces the cost of improving an incumbent solution compared to baseline GAS, particularly for a specific subset of knapsack instances. As combinatorial problems in domains such as semiconductor supply-chain planning grow in scale, methods that reduce circuit cost are an important step toward eventual quantum advantage for such applications.