Scalable Quantum State Preparation for Encoding Genomic Data with Matrix Product States

This paper presents a scalable method for encoding genomic data, specifically the bacteriophage $\Phi X174$ genome, into quantum states using Matrix Product States, demonstrating the trade-offs between circuit complexity and reconstruction error while validating the approach on both high-performance computing systems and current quantum hardware.

The Gist

Imagine you have a massive library of DNA instructions (genomes) written in a language of four letters: A, T, C, and G. Now, imagine you want to move this library into a brand-new, super-fast type of computer called a quantum computer.

The problem is that quantum computers speak a very different language. They don't read "A, T, C, G"; they read "quantum states," which are like complex, invisible waves of probability. Getting the DNA data from our world into the quantum computer's world without losing any information or breaking the computer is like trying to fit a giant, heavy elephant into a tiny, fragile teacup without spilling a drop of tea.

This paper presents a new, smarter way to do that "packing."

The Problem: The "Elephant in the Teacup"

Usually, loading data into a quantum computer is like trying to shove a whole library into a single room. If you try to do it all at once, the room gets too crowded, the walls (the computer's hardware) start shaking, and the data gets corrupted. This is because current quantum computers are "noisy"—they are easily disturbed, so they can only handle simple, short instructions (circuits) before they break down.

The Solution: The "Matrix Product State" (MPS) Method

The authors propose a method called Matrix Product States (MPS). Think of this not as shoving the whole elephant in at once, but as carefully disassembling the elephant into a series of small, manageable Lego bricks.

Here is how their method works, using a simple analogy:

1. Breaking it Down (The MPS): Instead of looking at the whole genome as one giant block, the method breaks the DNA sequence into a chain of small, connected pieces. Each piece is slightly entangled with its neighbor, like a chain of paperclips. This is the "Matrix Product State." It's a way of describing the data that is naturally friendly to quantum computers.
2. Building the Ladder (The Circuit): The authors figured out how to build a specific set of instructions (a quantum circuit) that takes a blank slate (a state of all zeros) and builds up that chain of paperclips, one by one.
   • Imagine you are building a tower. You start with a flat floor (the zero state).
   • You add a layer of blocks (gates) that connect the first and second floor.
   • Then you add another layer connecting the second and third.
   • You keep going until the tower looks exactly like the DNA sequence you wanted to encode.
3. The "Reverse Engineering" Trick: To figure out exactly how to build this tower, the authors used a clever trick. Instead of trying to guess how to build the tower from the ground up, they started with the finished tower (the DNA data) and asked, "How do I take this apart to get back to a flat floor?"
   • They solved the "take-apart" puzzle first.
   • Then, they simply ran the instructions in reverse.
   • This reverse process is the perfect recipe for building the tower from scratch on the quantum computer.

What They Tested

They tested this method on the genome of a tiny virus called ΦX174 (a bacteriophage).

• The Result: They successfully encoded this virus's entire genetic code into a quantum state using just 15 qubits (the quantum equivalent of bits).
• The Trade-off: They found that you can make the "packing" tighter or looser.
  • If you want a perfect copy (100% accuracy), you need a slightly more complex set of instructions.
  • If you are okay with a tiny bit of error (like a blurry photo instead of a sharp one), you can use a much simpler, shorter set of instructions. This is crucial because shorter instructions are less likely to break on today's noisy quantum computers.

Why This Matters (According to the Paper)

The paper claims this method is scalable. This means it works well whether you are encoding a tiny virus or a larger gene.

• Efficiency: They compared their method to standard tools (like IBM's Qiskit) and found their method required fewer steps (gates) to get the same result.
• Real-World Potential: They showed that with current or near-future technology, it is possible to encode important biological data, such as the gene for the SARS-CoV-2 spike protein or parts of the human immune system, into a quantum computer.
• Future Use: They mention that once the data is loaded this way, it can be used for specific tasks like Quantum Sequence Alignment (QSA). This is a way to compare DNA sequences much faster than classical computers can, which is a key step in analyzing how viruses evolve or how genes vary between people.

The Bottom Line

Think of this paper as a new moving company for the digital age. Before, moving your DNA data into a quantum computer was like trying to move a house by throwing it through a window. This new method provides a specialized truck and a step-by-step packing guide (the MPS circuit) that allows you to move the data safely, efficiently, and in a way that fits the unique shape of the quantum computer's "house."

They have proven that this moving truck works for small houses (viruses) and is ready to handle larger ones (genes) as the trucks (quantum hardware) get better.

Technical Summary

Technical Summary: Scalable Quantum State Preparation for Encoding Genomic Data with Matrix Product States

Problem Statement
As quantum hardware advances, a critical bottleneck in quantum bioinformatics is the efficient loading of classical genomic data into quantum states. Many promising quantum algorithms, such as Quantum Sequence Alignment (QSA) and Quantum Approximate Optimisation Algorithm (QAOA) for pangenome graph resolution, require data to be encoded into superposition states before execution. However, constructing quantum circuits to prepare these states is challenging due to hardware noise, which limits circuit depth. Existing methods, such as Cosine-Sine Decomposition (deterministic) or Genetic Algorithms for State Preparation (GASP, probabilistic), face scalability issues or computational inefficiencies. Furthermore, while Tensor Networks (specifically Matrix Product States or MPS) are widely used to simulate quantum circuits, there is a lack of scalable methods to prepare MPS representations of arbitrary data (like genomic sequences) using quantum circuits.

Methodology
The authors propose a scalable method to generate quantum circuits that prepare arbitrary normalized quantum state vectors, specifically tailored for genomic data, by utilizing the Matrix Product State (MPS) formalism.

1. Data Encoding: Genomic reads are mapped to quantum state vectors. A genome read of length $L$ is decomposed into position and base registers. Using a $k$-mer encoding (where $k=1$ for single bases), the state is represented as a superposition of position and nucleotide type. For example, the bacteriophage $\Phi$X174 genome (5,386 base pairs) is encoded into a 15-qubit state.
2. MPS Representation: The target state vector is converted into a left-canonical MPS. This involves iteratively applying Singular Value Decomposition (SVD) to reshape the state tensor, resulting in a chain of matrices $A^{\sigma_i}$ where the internal dimensions (bond dimensions, $\chi$) represent entanglement between sites.
3. Circuit Construction (Inverse Problem): Instead of evolving the zero state to the target, the algorithm solves the inverse problem: evolving the target state to the zero state $|0\rangle$.
   • The MPS is truncated to a bond dimension of $\chi=2$ to construct a single layer of two-qubit unitary gates ($U_{\sigma_k, \sigma_{k-1}}$) and a final single-qubit gate.
   • An iterative procedure is employed: The current target state is truncated to $\chi=2$, a circuit $C_q$ is generated to map this truncated state to $|0\rangle$, and the inverse circuit $C_q^\dagger$ is applied to the original target state.
   • This process repeats, accumulating layers of unitaries, until the fidelity between the evolved state and $|0\rangle$ meets a predefined threshold. The final circuit is the inverse of this accumulated sequence, evolving $|0\rangle$ to the target state.
4. Transpilation: Because the generated circuits consist of sequential layers of nearest-neighbor two-qubit gates, they are linear and can be efficiently transpiled to any hardware topology without complex qubit routing.

Key Contributions

• Scalable Circuit Generation: The paper presents a deterministic method to generate quantum circuits for arbitrary normalized states with gate counts scaling as $O(n \cdot \chi_{max}^2)$, where $n$ is the number of qubits and $\chi_{max}$ is the maximum bond dimension.
• Genomic Application: This is the first application of MPS state preparation techniques specifically for encoding genome sequence reads. The authors demonstrate the encoding of the $\Phi$X174 genome (15 qubits) and the SARS-CoV2 spike protein gene (14 qubits).
• Trade-off Analysis: The study systematically analyzes the trade-offs between MPS bond dimension, reconstruction error, and circuit complexity. It demonstrates that high-fidelity encoding of genomic data is possible with manageable bond dimensions (e.g., $\chi=98$ for $\Phi$X174 yields a reconstruction error of $10^{-6}$).
• Hardware Validation: The method was tested on High-Performance Computing (HPC) clusters and simulated on IBM quantum hardware emulators (8, 9, and 10 qubits), confirming the viability of the approach on current and near-future devices.

Results

• Efficiency: The MPS method outperforms standard tools like IBM Qiskit in terms of gate count for equivalent algorithmic fidelities. For the $\Phi$X174 genome, the gate count scales approximately as $2^n$ (where $n$ is qubits), but since $n \approx \log_2(L)$, the operations scale linearly with the genome read length $L$.
• Fidelity vs. Complexity: Simulations show that reducing the bond dimension significantly increases reconstruction error (e.g., halving the bond dimension for $\Phi$X174 increases error to ~20%). However, the method allows for tunable fidelity; circuits can be generated for specific fidelity thresholds (e.g., 75%, 90%, 99%) to match hardware constraints.
• Hardware Emulator Performance: Tests on IBM emulators revealed a complex interplay between algorithmic fidelity and hardware fidelity. While increasing gate count improves algorithmic fidelity, hardware noise eventually degrades the total fidelity. The optimal point exists where the circuit depth is supported by the hardware's noise tolerance.
• Scalability Estimates: The authors estimate that by the end of 2025, current hardware capabilities may allow for the encoding and sequencing of the SARS-CoV2 spike gene (14 qubits) and potentially the full $\Phi$X174 genome (15 qubits) on physical quantum computers.

Significance and Claims
The paper claims that this method provides a viable and efficient pathway for "application-ready" quantum bioinformatics. By enabling the loading of genomic data into quantum states with controllable error and manageable circuit depth, the authors argue that complex workflows like Quantum Sequence Alignment and pangenome graph tangle resolution can be implemented on near-term quantum hardware.

The authors emphasize that while the gate count scales exponentially with the number of qubits ($2^n$), the logarithmic relationship between qubits and genome length ($n \approx \log L$) means the method scales linearly with the actual biological data size. They conclude that this approach overcomes the data-loading bottleneck, allowing for the execution of fully quantum bioinformatics pipelines for tasks such as phylogenetic tree construction and pangenome analysis, provided that hardware noise levels are managed through appropriate fidelity thresholds. The work does not claim to solve all biological problems immediately but establishes the necessary infrastructure for encoding data to enable these future algorithms.