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

arXiv:2602.23848

MAFFT-inspired Quantum Shift-based Sequence Alignment and its Efficient Simulation on Decision Diagrams

Yusuke Kimura, Yutaka Takita

quant-phSubmitted Feb 27, 2026• Announced Mar 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Multiple sequence alignment (MSA) is a core operation for comparing genome sequences and is widely used in bio-informatics. MAFFT, a practical MSA tool, repeatedly shifts a pair of sequences and computes a distance. Because the number of sequence pairs grows quadratically with the number of sequences, this procedure can become a bottleneck. We propose Quantum Shift-based Sequence Alignment (QShift-SA), which implements this ``shift-wise score computation'' as a gate-based quantum circuit and searches over shift amounts and sequence pairs using Grover algorithm. QShift-SA constructs an oracle circuit that compute the Hamming distance (the number of mismatches) between two sequences with data encoding, controlled shift, comparison, and addition. This oracle can search for candidates with small distances. QShift-SA does not aim to replace the full MSA workflow; instead, it targets the screening steps that often dominate the runtime in classical MAFFT as stated above. We evaluate circuit resources (number of qubits, gate count, and depth) and benchmark simulation time across multiple quantum circuit simulators. We find that a decision diagram (DD)-based quantum circuit simulator runs more than 1,000$\times$ faster than state-vector and MPS simulators and can handle larger circuits.

Comments
11 pages

Related papers

Multi-sequence alignment using the Quantum Approximate Optimization Algorithm

Sebastian Yde Madsen, Frederik K. Marqversen, S. E. Rasmussen +1 more

The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.

arXiv:2308.12103•Aug 23, 2023•1 citation

Approximating Decision Diagrams for Quantum Circuit Simulation

Stefan Hillmich, Alwin Zulehner, Richard Kueng +2 more

Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.

ACM Transactions on Quantum Computing•Apr 25, 2022•14 citations

Efficient quantum circuit simulation.

John P. Hayes, Igor L. Markov, George F. Viamontes

Quantum-mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, while the securest forms of communication rely on quantum data encoding. When they involve a finite number of basis states, these phenomena can be modeled as quantum circuits, the quantum analogue of conventional or classical logic circuits. Simulation of quantum circuits can therefore be used as a tool to evaluate issues in the design of quantum information processors. Unfortunately, simulating such phenomena efficiently is exceedingly difficult. The matrices representing quantum operators (gates) and vectors modeling quantum states grow exponentially with the number of quantum bits. The information represented by quantum states and operators often exhibits structure that can be exploited when simulating certain classes of quantum circuits. We study the development of simulation methods that run on classical computers and take advantage of such repetitions and redundancies. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). A QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data. We develop a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluate their complexity. These algorithms have been implemented in a general-purpose simulator program for quantum-mechanical applications called QuIDDPro. Through extensive experiments conducted on representative quantum simulation applications, including Grover's search algorithm, error characterization, and reversible circuits, we demonstrate that QuIDDPro is faster than other existing quantum-mechanical simulators such as the National Institute of Standards and Technology's QCSim program, and is far more memory-efficient. Using QuIDDPro, we explore the advantages of quantum computation over classical computation, simulate quantum errors and error correction, and study the impact of numerical precision on the fidelity of simulations. We also develop several novel algorithms for testing quantum circuit equivalence and compare them empirically. The QuIDDPro software is equipped with a user-friendly interface and is distributed with numerous example scripts. It has been used as a laboratory supplement for quantum computing courses at several universities.

•Jan 1, 2007•15 citations

An algorithm for DNA read alignment on quantum accelerators

Aritra Sarkar, Zaid Al-Ars, Carmen G. Almudéver +1 more

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX simulator framework. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.

arXiv:1909.05563•Sep 12, 2019•15 citations

A Linear Time Quantum Algorithm for Pairwise Sequence Alignment

Md. Rabiul Islam Khan, Shadman Shahriar, Shaikh Farhan Rafid

Sequence Alignment is the process of aligning biological sequences in order to identify similarities between multiple sequences. In this paper, a Quantum Algorithm for finding the optimal alignment between DNA sequences has been demonstrated which works by mapping the sequence alignment problem into a path-searching problem through a 2D graph. The transition, which converges to a fixed path on the graph, is based on a proposed oracle for profit calculation. By implementing Grover's search algorithm, our proposed approach is able to align a pair of sequences and figure out the optimal alignment within linear time, which hasn't been attained by any classical deterministic algorithm. In addition to that, the proposed algorithm is capable of quadratic speeding up to any unstructured search problem by finding out the optimal paths accurately in a deterministic manner, in contrast to existing randomized algorithms that frequently sort out the sub-optimal alignments, therefore, don't always guarantee of finding out the optimal solutions.

arXiv:2307.04479•Jul 10, 2023•0 citations

A Quantum Dot Plot Generation Algorithm for Pairwise Sequence Alignment

Joseph Clapis

The Quantum Pairwise Sequence Alignment (QPSA) algorithm offers exponential speedups in data alignment tasks. However, it relies on an open problem of efficiently encoding the classical data being aligned into quantum superposition. Previous works suggest the use of specialized nonlinear Kerr media to implement a black-box oracle that achieves the superposition. We provide an alternative, explicit construction of this oracle called the Quantum Dot Plot (QDP), which is compatible with universal gate machines. We evaluate QDP's operational complexity via analysis of the quantum machine instructions generated by the Q# and Qiskit software frameworks for various sample circuits. Our analysis confirms that the data encoding scheme is exponentially difficult, precluding QDP's (and thus, QPSA's) employment on general-purpose quantum computers. Nevertheless, we find utility in estimating the circuit depth and run time of both QDP and QPSA for IBM's superconducting architecture and AQT's trapped ion architecture for direct comparison and overall practicality purposes.

arXiv:2107.11346•Jul 23, 2021•5 citations
Multiple sequence alignment (MSA) is a core operation for comparing genome sequences and is widely used in bio-informatics. MAFFT, a practical MSA tool, repeatedly shifts a pair of sequences and computes a distance. Because the number of sequence pairs grows quadratically with the number of sequences, this procedure can become a bottleneck.
We propose Quantum Shift-based Sequence Alignment (QShift-SA), which implements this ``shift-wise score computation'' as a gate-based quantum circuit and searches over shift amounts and sequence pairs using Grover algorithm. QShift-SA constructs an oracle circuit that compute the Hamming distance (the number of mismatches) between two sequences with data encoding, controlled shift, comparison, and addition. This oracle can search for candidates with small distances. QShift-SA does not aim to replace the full MSA workflow; instead, it targets the screening steps that often dominate the runtime in classical MAFFT as stated above.
We evaluate circuit resources (number of qubits, gate count, and depth) and benchmark simulation time across multiple quantum circuit simulators. We find that a decision diagram (DD)-based quantum circuit simulator runs more than 1,000×\times× faster than state-vector and MPS simulators and can handle larger circuits.
The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.
Quantum-mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, while the securest forms of communication rely on quantum data encoding. When they involve a finite number of basis states, these phenomena can be modeled as quantum circuits, the quantum analogue of conventional or classical logic circuits. Simulation of quantum circuits can therefore be used as a tool to evaluate issues in the design of quantum information processors. Unfortunately, simulating such phenomena efficiently is exceedingly difficult. The matrices representing quantum operators (gates) and vectors modeling quantum states grow exponentially with the number of quantum bits. The information represented by quantum states and operators often exhibits structure that can be exploited when simulating certain classes of quantum circuits. We study the development of simulation methods that run on classical computers and take advantage of such repetitions and redundancies. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). A QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data. We develop a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluate their complexity. These algorithms have been implemented in a general-purpose simulator program for quantum-mechanical applications called QuIDDPro. Through extensive experiments conducted on representative quantum simulation applications, including Grover's search algorithm, error characterization, and reversible circuits, we demonstrate that QuIDDPro is faster than other existing quantum-mechanical simulators such as the National Institute of Standards and Technology's QCSim program, and is far more memory-efficient. Using QuIDDPro, we explore the advantages of quantum computation over classical computation, simulate quantum errors and error correction, and study the impact of numerical precision on the fidelity of simulations. We also develop several novel algorithms for testing quantum circuit equivalence and compare them empirically. The QuIDDPro software is equipped with a user-friendly interface and is distributed with numerous example scripts. It has been used as a laboratory supplement for quantum computing courses at several universities.
With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX simulator framework. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.
Sequence Alignment is the process of aligning biological sequences in order to identify similarities between multiple sequences. In this paper, a Quantum Algorithm for finding the optimal alignment between DNA sequences has been demonstrated which works by mapping the sequence alignment problem into a path-searching problem through a 2D graph. The transition, which converges to a fixed path on the graph, is based on a proposed oracle for profit calculation. By implementing Grover's search algorithm, our proposed approach is able to align a pair of sequences and figure out the optimal alignment within linear time, which hasn't been attained by any classical deterministic algorithm. In addition to that, the proposed algorithm is capable of quadratic speeding up to any unstructured search problem by finding out the optimal paths accurately in a deterministic manner, in contrast to existing randomized algorithms that frequently sort out the sub-optimal alignments, therefore, don't always guarantee of finding out the optimal solutions.
The Quantum Pairwise Sequence Alignment (QPSA) algorithm offers exponential speedups in data alignment tasks. However, it relies on an open problem of efficiently encoding the classical data being aligned into quantum superposition. Previous works suggest the use of specialized nonlinear Kerr media to implement a black-box oracle that achieves the superposition. We provide an alternative, explicit construction of this oracle called the Quantum Dot Plot (QDP), which is compatible with universal gate machines. We evaluate QDP's operational complexity via analysis of the quantum machine instructions generated by the Q# and Qiskit software frameworks for various sample circuits. Our analysis confirms that the data encoding scheme is exponentially difficult, precluding QDP's (and thus, QPSA's) employment on general-purpose quantum computers. Nevertheless, we find utility in estimating the circuit depth and run time of both QDP and QPSA for IBM's superconducting architecture and AQT's trapped ion architecture for direct comparison and overall practicality purposes.