Hello, I'm Yusuke Kimura from the Quantum Applications CPJ at the Quantum Laboratory.
I have been focusing on genome analysis as one of the application areas for quantum computers. Recently, we implemented part of Multiple Sequence Alignment (MSA)—one of the important techniques in genome analysis—as a quantum circuit, and simulated it efficiently using our decision diagram (DD)-based quantum circuit simulator. The work has been published on arXiv. In this article, I'll introduce the contents of the paper in an easy manner.
Comparing DNA sequences with Shifting
Let's start with the basics of genome sequence comparison.
This research focuses on DNA sequences. DNA can be represented as a string composed of four types of bases: A (adenine), T (thymine), G (guanine), and C (cytosine). For example, "ATGCAACT" corresponds directly to a single DNA sequence. In genome analysis, measuring the similarity between such DNA sequences is a fundamental operation.
One of the simplest comparison methods is the Hamming distance. This is a distance that compares two strings of the same length position by position and counts how many characters differ. For example, if you compare two DNA sequences character by character and find three positions that differ, the Hamming distance is 3.
The Hamming distance is simple and fast, but it is vulnerable to "shifts" in sequences.
For example, if there is a single-character insertion or deletion in one of the sequences, all subsequent characters get shifted by one position. In this case, even if the sequences actually contain highly similar regions, comparing them at the same positions makes many mismatches.
Here's a visual example:
Sequence 1: A T G C A A C T Sequence 2: T G C A A C T T
Sequence 2 is very similar to Sequence 1, but its starting position is shifted by one. In such a case, simply fixing the positions and comparing them fails to capture the similarity well.
To address this, we can shift one of the sequences little by little and compare them, investigating "which shift gives the best overlap." This idea also appears in MAFFT, a practical MSA tool. This is not the same as fully gap-aware alignment, but it serves as an important preprocessing step for finding "candidates worth examining in detail" from a large collection of sequences.
The flow of multiple sequence alignment, and which part this research targets
So far, we have discussed how to compare a pair of sequences. Next, let's clarify how this is used within the entire multiple sequence alignment (MSA) workflow, and which part of it this research applies quantum computing to.
Practical MSA generally proceeds through the following three steps:
- Distance matrix construction: Compute a rough distance (or similarity) for all sequence pairs
- Guide tree construction: Based on the distance matrix, construct a tree structure that groups closely related sequences together
- Progressive alignment: Perform operations along the guide tree to obtain the final result
We apply quantum computation to the first step: distance matrix construction.
A key point is that only pairs with small distances is important for determining the shape of the guide tree. In other words, there is no need to compute every element of the distance matrix in detail; it is sufficient to efficiently find candidates with small distances. In this research, we exploit this property and take the approach of using Grover search to pick up "sequence pairs (and their shift amounts) with small distances." The aim of this research is to skip computations for the other pairs with large distances.
Implementing distance computation into a quantum circuit
Now, let's look at the structure of the quantum circuit that combines shift comparison with Grover search.
The candidates we want to search for are pairs of DNA sequences with small distances, which can be roughly described by the following three components:
- The first sequence
- The second sequence
- How much to shift
In classical computation, it is natural to examine sequence pairs and shift amounts one by one. In quantum computation, on the other hand, these candidates can be handled as a superposition state. We then mark the candidates with small distances and use Grover search to amplify the probability of observing those candidates. This achieves the process described in the previous section—"only finding sequence pairs with small distances"—in a quantum way.
I believe that cutting out the problem into a small piece like this is important when applying quantum algorithms to real problems. Rather than trying to quantize an entire complex workflow at once, it becomes easier to implement and evaluate by clarifying "which part is well-suited to quantum search" and "what the inputs and outputs of that part are."
Bottlenecks in circuit size
For quantum algorithms, it is not enough to say "the number of searches may be reduced to roughly the square root thanks to Grover." In practice, the cost of loading data into a quantum state and the depth of the circuit that computes distances also matter.
In the paper, we implemented the circuit in Qiskit and evaluated the number of gates required for a single Grover iteration.
As a result, we found that the shift circuit is the dominant cost for small problems, but as the number of sequences grows, the state preparation that loads multiple sequences into quantum registers becomes dominant.
| (data length, count) | (4,4) | (8,4) | (8,8) | (16,16) |
|---|---|---|---|---|
| State preparation | 250 | 474 | 1,730 | 18,852 |
| Distance computation | 619 | 1,501 | 1,501 | 3,523 |
| shift | 416 | 1,056 | 1,056 | 2,592 |
| compare | 104 | 208 | 208 | 416 |
| adder | 96 | 234 | 234 | 512 |
| Grover diffusion | 300 | 475 | 960 | 1,926 |
This result tells us where we should improve in the future. Even if we optimize only the distance computation circuit, the overall speedup will be limited if the bottleneck has shifted to state preparation. To bring quantum algorithms closer to real problems, the design needs to include not only the distance computation part but also how data is loaded—that is, state preparation.
Why use a quantum circuit simulator for verification
From here, I'll talk about "how we ran" the designed quantum circuit. But before that, let me briefly explain what a quantum circuit simulator is.
A quantum circuit simulator is software that emulates the behavior of a quantum computer on a classical computer. When given a quantum circuit as input, it reproduces—through numerical computation—the quantum state and measurement results that would be obtained when executing the circuit on a quantum computer.
So why did we use a simulator rather than real hardware? There are two main reasons. First, current quantum computer hardware still has significant constraints in terms of qubit count and noise, making it difficult to stably run circuits of the scale handled in this research as-is. Second, during the algorithm development stage, there are many situations where one wants to carefully examine circuit behavior in an ideal, low-noise environment, and a simulator allows for more reproducible evaluation. We used a simulator to confirm that, the circuit produces results consistent with classical methods with high probability.
Acceleration with a DD-based simulator
What we found particularly interesting in this research was that the proposed quantum circuit was a good match for the decision diagram (DD)-based quantum circuit simulator.
There are several methods for simulating quantum circuits on classical computers. Representative ones include the state vector based, the MPS (Matrix Product State)-based, and the DD-based. The state vector is the standard method, but the required memory grows exponentially as the number of qubits increases. The MPS is powerful for circuits with small entanglement but tends to become heavy when there are many operations across various qubits. The DD, on the other hand, represents the same structures appearing in quantum states as shared nodes in a graph, which can be significantly lighter than holding the state vector explicitly. I introduced the mechanism of DD-based simulators in detail in a previous blog post (Japanese), or please directly refer to the paper.
In this work, we compared the state vector, MPS and DD-based ones for the our proposed quantum circuit . As a result, the DD ran fast across a wide range of settings.
For example, in a 27-qubit setting, DD finished in 0.89 seconds. In contrast, the state vector took 93.89 seconds, and the MPS took 422.40 seconds. In a 39-qubit setting, the DD finished in 0.48 seconds, while the MPS took 3000.47 seconds.
This difference shows the compatibility between the circuit structure and the simulation method. The circuit in this work contains many regular operations such as shifts, comparisons, distance computations, and Grover search. This allowed decision diagrams to share common substructures easily, enabling more efficient simulation than others.
The lesson here is that in quantum algorithm research, "which simulator to use for verification" is also important. A good simulator broadens the scope of exploration in quantum algorithm development. Our results show that decision diagram-based simulators can be a promising option for genome analysis.
Summary
This research does not aim to replace the entire multiple sequence alignment with a quantum computer. Instead, it focuses on the "distance matrix construction" step within MSA and implements shift-aware candidate search as a quantum circuit. We used Grover search to efficiently pick up only the "pairs with small distances" that influence the guide tree building. Furthermore, we showed that by using a DD-based simulator, quantum circuits that are difficult to handle with the state vector or MPS can be simulated efficiently.
When applying quantum algorithms to real problems, I believe it is important to clarify, one by one: (1) which part to quantize, (2) where the bottleneck shifts to, and (3) which simulator to use for verification. I hope this research will be a useful reference for researchers and students who want to apply quantum algorithms to the life sciences and bioinformatics.
