Classical-to-Quantum Sequence Encoding in Genomics

###### Abstract

DNA sequencing allows for the determination of the genetic code of an
organism, and therefore is an indispensable tool that has applications in
Medicine, Life Sciences, Evolutionary Biology, Food Sciences and Technology,
and Agriculture. In this paper, we present several novel methods of performing
classical-to-quantum data encoding inspired by various mathematical fields,
and we demonstrate these ideas within Bioinformatics. In particular, we
introduce algorithms that draw inspiration from diverse fields such as
Electrical and Electronic Engineering, Information Theory, Differential
Geometry, and Neural Network architectures. We provide a complete overview of
the existing data encoding schemes and show how to use them in Genomics. The
algorithms provided utilise lossless compression, wavelet-based encoding, and
information entropy. Moreover, we propose a contemporary method for testing
encoded DNA sequences using Quantum Boltzmann Machines. To evaluate the
effectiveness of our algorithms, we discuss a potential dataset that serves as
a sandbox environment for testing against real-world scenarios. Our research
contributes to developing classical-to-quantum data encoding methods in the
science of Bioinformatics by introducing innovative algorithms that utilise
diverse fields and advanced techniques. Our findings offer insights into the
potential of Quantum Computing in Bioinformatics and have implications for
future research in this area.
_Keywords_ : Data Encoding, DNA Sequencing, Quantum Computing

###### List of Figures

  1. 1 A simplified unravelled DNA sequence.
  2. 2 Single and two-qubit quantum gates.
  3. 3 Quantum DevOps lineage of the data lifecycle.
  4. 4 Hinton representation of quantum data for A using Amplitude Encoding, with $\rho$ being the state vector of the sequence A with $\text{Re}(\cdot)$ as the real part and $\text{Im}(\cdot)$ as the imaginary part.
  5. 5 City representation of quantum data for AG using ZZFeatureMap.
  6. 6 Bloch sphere representation of quantum data for ATG using IQPEmbedding.
  7. 7 DFT: $\mathcal{O}(k^{2})$; Wavelet Transform: $\mathcal{O}(k^{2})$; Run-length Encoding: $\mathcal{O}(k)$; Huffman Coding: $\mathcal{O}(k\log k)$; LZW: $\mathcal{O}(k^{2})$.
  8. 8 Graphical representation of the nitrogenous bases with their counts and codes along the edges respectively.
  9. 9 The results of CTTTTGGAAAA using QBWT on QasmSimulator with $1024$ shots.
  10. 10 Pauli representation of quantum data for ATC using Cosine Encoding.
  11. 11 City representation of quantum data for ATC using Cosine Encoding.
  12. 12 Graph of the Boltzmann distribution for various parameter values.
  13. 13 Architecture of a fully connected Boltzmann machine with $3$ visible units and $5$ hidden units.
  14. 14 Training and testing data distributions.

###### List of Tables

  1. 1 Modern DNA sequencing approaches
  2. 2 List of physical qubit implementations
  3. 3 Count of the nitrogenous bases in the M13 bacteriophage DNA sequence
  4. 4 Code determination for each nitrogenous base.
  5. 5 Advantages and disadvantages of our quantum encoding algorithms

##  I Introduction

Deoxyribonucleic Acid (DNA) is a molecule that contains the genetic
instructions used in the development and functioning of all living organisms.
Illustratively, we can describe it as a long, double-stranded molecule made up
of nucleotides, which are its composite building blocks. Each nucleotide in
DNA consists of the sugar molecule deoxyribose
[$\text{C}_{5}\text{H}_{10}\text{O}_{4}$], a phosphate group
[–$\text{PO}_{4}^{\;\;3-}$], and a nitrogenous base: Either Adenine
[$\text{C}_{5}\text{H}_{5}\text{N}_{5}$], Thymine
[$\text{C}_{5}\text{H}_{6}\text{N}_{2}\text{O}_{2}$], Cytosine
[$\text{C}_{4}\text{H}_{5}\text{N}_{3}\text{O}$], or Guanine
[$\text{C}_{5}\text{H}_{5}\text{N}_{5}\text{O}$], denoted by A, T, C, and G
respectively. The arrangement of these bases along the DNA molecule determines
the genetic code or sequence, which is unique to every individual organism.
Geometrically, DNA is described as a doubly / bi- helical, which contains two
complementary strands of nucleotides that are twisted together as presented in
the Figure 1. The nitrogenous bases of the two strands are held together by
Hydrogen bonds, with A always pairing with T and C always pairing with G. This
base pairing is often referred to as the base-pairing rule. DNA is found in
the nucleus of eukaryotic cells and the cytoplasm of prokaryotic cells. It
serves as the template for the synthesis of messenger RNA (mRNA) in a process
called transcription, which then serves as the template for protein synthesis
in a process called translation. DNA also undergoes replication to produce new
copies of itself, ensuring the genetic code is passed on to the next
generation of cells and organisms. In addition to its fundamental role in
genetics and heredity, DNA has numerous practical applications in Forensics,
Medicine, Agriculture, and Biotechnology.
The first complete DNA sequence of an organism was determined by the
Biochemist Frederick Sanger ($1918-2013$) and his colleagues in 1977. They
sequenced the genome of the bacteriophage Phi X 174 ($\phi$X 174) using the
Sanger sequencing method, which he and his collaborators had developed a few
years earlier Sanger .

Figure 1: A simplified unravelled DNA sequence.

Within Genomics, there exist two ubiquitous methods of DNA sequencing (for a
complete treatment of the history, see HistoryOfDNA ):

  1. 1.

Maxam-Gilbert Sequencing: Also known as “chemical sequencing” MaxamGilbert ,
it is a method for determining the sequence of nucleotides in a DNA molecule.
This method involves four steps:

    1. 1.1.

DNA Fragmentation: The DNA molecule is first broken into smaller fragments of
a specific size using chemical or enzymatic methods.

    2. 1.2.

Chemical Treatment: Each fragment is subjected to a specific chemical
treatment that causes DNA cleavage at specific nucleotide positions. There are
four chemical reactions, each of which cleaves the DNA at specific
nucleotides: Dimethyl Sulfate [$\text{C}_{2}\text{H}_{6}\text{O}_{4}\text{S}$]
cleaves at purines A and G, Hydrazine [$\text{N}_{2}\text{H}_{4}$] cleaves at
the G residues, Formic Acid [$\text{CH}_{2}\text{O}_{2}$] cleaves at the A
residues, and Piperidine [$\text{C}_{5}\text{H}_{11}\text{N}$] cleaves at the
G residues.

    3. 1.3.

Gel Electrophoresis: The fragments are then separated by size using
polyacrylamide gel electrophoresis (PAGE). The gel is then dried and exposed
to X-ray film or a phosphorimager to visualise the labelled fragments.

    4. 1.4.

Analysis: The sequence of the DNA molecule is determined by analysing the
pattern of fragments produced by the chemical treatments. By comparing the
patterns obtained from each chemical reaction, the location of the cleaved
nucleotide can be determined, allowing the sequence of the DNA fragment to be
determined.

We note that while this was a novel approach to sequencing DNA, it has several
drawbacks. For one, it is limited in that it can only effectively sequence
short DNA fragments. It is very resource-intensive in its time requirements to
carry out this procedure, the hazardousness and toxicity of the chemicals
involved, and the amount of material used.

  2. 2.

Sanger Sequencing: Also known as the “chain-termination” method Sanger  or
“Dideoxy Sequencing”. This technique was heavily influenced by, and therefore
built upon, the M-G Sequencing technique’s bedrock and tried to rectify some
of where it falls short. This method finds many applications in Genome
Sequencing, Gene Expression Analysis, and Genetic Disease Diagnosis.

Essentially, this technique is ubiquitously used to determine the sequence of
nucleotides. The method is based on the incorporation of modified nucleotides
called dideoxynucleotides (ddNTPs) into the growing DNA chain during DNA
synthesis. These ddNTPs lack a $3^{\prime}$-Hydroxyl [–OH] group, which is
required to form a phosphodiester bond with the next incoming nucleotide. As a
result, once a ddNTP is incorporated, no further nucleotides can be added to
the DNA chain, effectively terminating the chain elongation.

Sanger sequencing involves four separate reactions, each containing a
different ddNTP and all four regular deoxynucleotides (dNTPs), DNA polymerase,
a primer, and the template DNA. These reactions generate a series of DNA
fragments of different lengths that terminate at each occurrence of the ddNTP.
The fragments are then separated by size using gel electrophoresis, producing
a ladder of bands corresponding to the DNA sequence. The sequence can be read
by reading the positions of each band in the ladder.

Modern Sanger sequencing techniques typically use fluorescently-labelled
ddNTPs and automated capillary electrophoresis to speed up the sequencing
process and increase accuracy.

Some of the drawbacks of Sanger Sequencing are that it is very expensive to
conduct and relatively slow compared to more modern techniques.

Below we tabulate (1) some of the modern DNA sequencing methods.

Table 1: Modern DNA sequencing approaches Technique |  Description
---|---
Metagenomic Sequencing Riesenfeld  |  This method involves sequencing DNA from environmental samples, such as soil or water, to study microbial communities.
Single-cell Sequencing Macosko  |  This involves sequencing the DNA of individual cells. This technique finds usage in studying genetic heterogeneity and rare cell populations.
Next-Generation Sequencing (NGS) Metzker  |  This method includes a range of techniques such as Illumina dye sequencing – such as Deoxyribonucleoside Triphosphates (dNTP) mix [$\text{C}_{10}\text{H}_{16}\text{N}_{5}\text{O}_{12}\text{P}_{3}$], Ion Torrent sequencing, Pacific Bio (PacBio) sequencing, and Oxford Nanopore sequencing.
Third-Generation Sequencing (TGS) Li  |  This method includes techniques like single-molecule real-time (SMRT) sequencing and nanopore sequencing, which can generate long reads.
Target Sequencing Krauthammer  |  This method involves sequencing specific regions of the genome, such as exomes or panels of genes that are of interest.
Ancient DNA Sequencing Green  |  This method involves sequencing DNA from ancient specimens, such as fossils or mummified remains.

While the currently existing DNA sequencing techniques have achieved many
milestones and have contributed positively to scientific pursuits and enhanced
the lives of humanity, these methods suffer from many perils. These include:

  1. 1.

High Costs: Despite the rapid reduction in sequencing costs over the past few
years, DNA sequencing is still relatively expensive. Several estimates
indicate that genome sequencing is generally cheaper than testing a single
gene. These studies place the costs in the region of $\$399$-$\$999$ USD.

  2. 2.

Resource Intensive: DNA samples need to be prepared correctly to ensure
accurate sequencing results. For sequencing, the samples that are prepared can
be time-consuming and labour-intensive.

  3. 3.

Incomplete Sequencing: The process of sequencing DNA can be complex and
challenging, and errors may occur at various stages, leading to incomplete or
inaccurate sequencing results.

  4. 4.

Errors Arising from Sequencing: Sequencing techniques may produce errors,
leading to inaccuracies in the final sequence data. As an example, consider
certain regions of the genome that may be challenging to sequence accurately,
which lead to potential errors.

  5. 5.

Requiring Specialist Computing Skills: The analysis of the large amounts of
data generated by DNA sequencing can be challenging and requires specialised
expertise with software tools.

  6. 6.

Diversity amongst Individuals when Diagnosing: There can be significant
variations between individuals’ DNA sequences, which may make it challenging
to identify mutations that cause diseases or other genetic conditions.

  7. 7.

Genome Complexity: The genome can be complex, and some regions are challenging
to sequence due to their repetitive nature or high GC (Guanine-Cytosine)
content. This complexity can make it challenging to generate accurate sequence
data.

  8. 8.

Sequencing Length Limitations: Some sequencing methods are limited in the
length of DNA fragments that they can sequence, making it challenging to study
longer sequences.

Inspired by these pitfalls, we present an ambition to apply Quantum Sciences
to try and address these problems. Quantum Information Sciences (QIS), which
is the umbrella term that all-encompasses: Quantum Computing (QC), Quantum
Error Correction, Quantum Machine Learning, Post-Quantum Cryptography, Quantum
Metrology, and Quantum Sensing, has the potential to provide a speedup over
some classical computing techniques because it exploits the quantum properties
of nature, namely:

  1. 1.

Non-locality: When two or more, particles are intertwined in such a way that
measuring the state of one particle expeditiously affects the state of the
other particle, irrespective of the distance between the two particles.

  2. 2.

Wave-Particle Duality: The ability for a particle to exhibit both wave-like
and corpuscular properties which manifest based upon how they are observed.

  3. 3.

Superposition: The ability for an object, mostly confined to the subatomic
scales, to exist in multiple states simultaneously.

  4. 4.

Entanglement: More colloquially known as “spooky action at a distance”, it is
the correlation of two or more, particles such that the state of one particle
depends on the other, even when these particles may be separated by an
infinitely-large distance.

  5. 5.

Tunneling: The ability for particles to penetrate through barriers that would
be impossible in the realm of Classical Mechanics.

  6. 6.

Interference: The phenomenon that occurs when two or more states interact with
one another, which leads to the change in probabilities after measurement.

  7. 7.

Teleportation: The transmission and conveyance of information from one
particle to another without any observable motion of the particles.

Of particular interest in QC is the property of superposition, in which a
state $\ket{\psi}$ can be written as a linear combination of the basis states
$\ket{0}=\begin{pmatrix}1&0\end{pmatrix}^{T}$ and
$\ket{1}=\begin{pmatrix}0&1\end{pmatrix}^{T}$, as
$\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$, where $\alpha,\beta\in\mathbb{C}$ are
the complex probability amplitudes. Historically, QC has its roots in a $1982$
proposition by the Nobel laureate Richard Feynman ($1918-1988$), who begged
the question of whether a computer could harness the properties of quantum
mechanics to simulate quantum systems Feynman .
In the subsequent years that followed, David Deutsch ($1953-$) and Peter
Williston Shor ($1959-$) spearheaded this challenge, and the culmination of
the first QC algorithm, “Shor’s algorithm”, was published in $1994$, for the
prime factorisation of large numbers. This demonstrated that QC had the
potential to provide an exponential speed-up over classical computing in
certain tasks; thus, the world took notice. The fundamental unit of QC is the
qubit, a portmanteau of the words “quantum” and “bit”, which lives in a two-
dimensional vector space called the Bloch sphere. A qubit is the quantum
mechanical analogue of a classical bit, but instead of being in the “0” or “1”
state exclusively, it can simultaneously be in the $0$ and $1$ states, with
associated probabilities. Below, we tabulate (2) the various physical
implementations of qubits.

Table 2: List of physical qubit implementations Physical Implementation |  Advantages |  Disadvantages
---|---|---
Trapped Ion Qubits: Qubits that are formed by trapping ions using a Paul Trap. |  Highly stable. |  Difficult to upscale.
|  Can be precisely manipulated. |  Require expensive and complex equipment to implement.
Superconducting Qubits: Qubits made from superconducting circuits. |  Relatively easy to manufacture. |  Highly sensitive to noise and decoherence.
|  Can be easily upscaled. |  Require very low operational temperatures.
Photon Qubits: Qubits that use the phase angle or polarisation of individual photons to represent states. |  Easy to create. |  Difficult to store.
|  Easy to manipulate. |  Difficult to stimulate interaction with other qubits.
Quantum Dots: These are minute semiconductors that trap electrons and use their spin to represent qubits. |  Easily integrated with current semiconductor technology. |  Sensitive to noise and decoherence.

Mathematically, we will restrict our usage and implementation of QC for
classical-to-quantum data encoding to gate-based QC; and we note the
convention $\imath=\jmath=\sqrt{-1}$; $\imath$ being used in mathematical
formulae, and $\jmath$ being used in code output. In addition, we note the in-
vogue conventions of $I$ for the identity matrix, $X,Y,Z$ for the Pauli spin
matrices / gates, $H$ for the Hadamard gate, $S$ for the phase gate, $T$ for
the $\pi/8$ gate, $SWAP$ for the SWAP gate, $CNOT=CX$ for the controlled-NOT
gate, and $CU$ for the controlled-unitary gate, where $U$ is any unitary
transformation; videlicet $UU^{\dagger}=U^{\dagger}U=I$.
Within this archetype, quantum gates, analogous to classical logic gates,
serve as representations of matrix operations on states. All classical logic
gate results can be represented as well as additional results that arise due
to the various quantum phenomena. Below, in the Figure 2, we diagrammatically
encapsulate these gate operations.

Figure 2: Single and two-qubit quantum gates.

Reverting to the discussion on DNA sequencing, to the Physics Community, what
was particularly appealing was the determination of the double helix structure
of the DNA molecule because one of its co-discoverers, Francis Cricks
($1916-2004$), trained as a Physicist. Nowadays, with the advent of QIS, many
Physicists are interested, amongst other research tracks, in using this new
computational paradigm for a whole class of novel applications, including, and
certainly not limited to, DNA sequencing. Within this framework, there has
been a plethora of interest in recent times in applying techniques from QC for
the sequencing of DNA.
Kathuria et al Kathuria  presented two efficient inner product-based kernel
classifiers for cataloguing individuals as “normal” or “having a disease”
using functional genomic attributes as inputs. The classifiers presented used
binary-valued features, which allowed for highly efficient data encoding and
Hamming distance-based measurements

$d_{H}(s,s^{\prime})=\sum_{i=1}^{n}\left(s_{i}\neq
s^{\prime}_{i}\right)=\sum_{i=1}^{n}\begin{cases}1,\quad s_{i}\neq
s^{\prime}_{i},\\\
0,\quad\text{otherwise}.\end{cases}=\sum_{i=1}^{n}s_{i}\oplus s^{\prime}_{i},$
(1)

where $s_{i}$ and $s^{\prime}_{i}$ are the two DNA sequences, and $\oplus$
denotes the logical exclusive OR (XOR) operator. Using IBM’s quantum computer,
the algorithms were implemented. The classifiers required the same number of
qubits for training samples and had low gate complexity after the states were
prepared.
Boev et al Boev  presented a method using quantum and quantum-inspired
optimisation techniques to solve genome assembly tasks, with promising
experimental results on both simulated data and the $\phi$X 174 bacteriophage.
Their results suggested that the new generation of quantum annealing devices
could outperform existing techniques for De Novo genome assembly, videlicet
genome sequencing, where no reference sequences were available to refer to.
Sarkar et al Sarkar  presented QuASeR as a reference-free DNA sequence
reconstruction implementation via De Novo assembly on both gate-based and
quantum annealing platforms. Furthermore, four implementation steps with a
proof-of-concept example to target the genomics research were presented.
Nałȩcz-Charkiewicz and Nowak NN  presented a proof for a De Novo assembly
algorithm using a hybrid combination of CPU and the D-Wave quantum annealer
QPU for calculations that were benchmarked against the results of a classical
computer by using the Pearson correlation coefficient to detect overlaps
between DNA readings. The training data consisted of synthetic and real data
from a simulator, and this study was unique because actual organism genomes
were sequenced. Due to the low number of qubits available on NISQ-era quantum
computers nisq , this study demonstrated that hybrid approaches are imperative
in the field, and quantum annealers are a viable option for De Novo
sequencing.
Data Encoding or State preparation, within the context of QIS, is the process
of converting classical data into quantum states for further usage in an
algorithm. The method of data encoding occurs within the preprocessing stage.
By presenting an efficient encoding scheme, the entire DNA sequencing process
will become more streamlined and robust. Thus, enhancing existing quantum
sequencing methods or inspiring the development of a rich class of new
sequencing algorithms. The domain of this work lies within this process of the
quantum data lifecycle. Our foremost objective is to design novel classical-
to-quantum encoding schemes such that the data can be used further down the
line in the process.

Figure 3: Quantum DevOps lineage of the data lifecycle.

In this paper, we present novel classes of algorithms that are appropriate
from methods and ideas in Electrical and Electronic Engineering, Information
Theory, Differential Geometry, and Neural Network Architectures. In so doing,
we provide seven new algorithms for classical-to-quantum encoding and an
eighth algorithm that provides a proof-of-concept test for how effective an
algorithm is in undertaking the encoding. This paper is divided as follows:
In §II, we provide an overview of existing classical-to-quantum encoding
schemes that are ubiquitously adopted in the discipline, and which are
incorporated into several of the popular SDKs and frameworks.
In §III, we provide demonstrable examples of how the existing classical-to-
quantum data encoding schemes are used.
In §IV, we provide the first classes of new algorithms that use lossless
compression. In addition, we motivate why lossless compression-inspired
algorithms were chosen over lossy algorithms.
In §V, we provide a wavelet-inspired encoding scheme that, in many respects,
builds upon the Quantum Fourier Transform.
In §VI, we provide two algorithms based on the notion of information entropy.
The input to the first algorithm takes in just the DNA sequence to be encoded,
whereas, in the second algorithm, the DNA sequence to be encoded as well as a
reference DNA sequence, is ingested. Lastly, using the methods of
Computational Information Geometry, we present a third type of procedure.
In §VII, we provide a method for testing an encoded DNA sequence using Quantum
Boltzmann Machines.
In §VIII, we discuss a potential dataset that serves as a sandbox environment
to test these algorithms against.
In §IX, we provide conclusive remarks and contemplate the results produced.
Thereafter, an indication of some of the future avenues of research that will
be pursued in subsequent iterations of this work are transiently discussed.

##  II A Review of Existing Encoding Methods

Prior to providing an in-depth discussion of the existing techniques, it is
imperative that we clearly define “Rotations”. Rotation, in the context of
data encoding, is the process of applying a rotation operator / gate,
$R_{\xi}(\theta)$, for $\xi\in\left\\{X,Y,Z\right\\}$, with a phase angle
$\theta$ to quantum data. Mathematically, this is achieved as follows:

$R_{\xi}(\theta)\overset{\Delta}{=}\exp\left(-\imath\frac{\theta}{2}\xi\right)=\cos\left(\frac{\theta}{2}\right)\mathbb{I}_{3}-\imath\sin\left(\frac{\theta}{2}\right)\xi,$
(2)

with $\mathbb{I}_{3}$ is the $3\times 3$ identity matrix and $\xi$ in this
case represents $3\times 3$ single Pauli matrix.

Sierra-Sosa et al. sierra2023data  explore rotation schemes on classical data
during the preprocessing step of the QML pipeline. It was shown that rotations
could have a negative impact on the von Mises dataset, leading to substantial
whiskers on the box plots. This outcome is akin to other preprocessing
methods, where a chosen normalisation or discretisation can have an
unfavourable effect on the classifier’s ability to optimise a given dataset.
The existing encoding schemes belong to the following classes: Amplitude
Encoding and Second-order Pauli Feature Map Encoding. Below, we discuss each
of these classes and their respective components.

###  II.1 Amplitude Encoding

Amplitude encoding is a technique used for mapping classical p-dimensional
data points $x\in\mathbb{R}^{p}$ to quantum states $\ket{x}$ in the complex
Hilbert space $\mathbb{C}^{2n}$ with $n$ is the number of qubits
sierra2023data . The resulting quantum state is defined by the amplitudes of
$x$ in the computational basis states. The original classical data determine
these states using the expression below:

$x\mapsto\ket{x}=\sum_{i=1}^{2^{n}}x_{i}\ket{i},$ (3)

where $\ket{i}$ are the $n$-qubit computational basis states. We can apply
this technique using two classical preprocessing steps that are first carried
out. If the input vector $x$ is less than $2^{n}$ in dimension, it is padded
with zero features to create a vector of dimension $2^{n}$. The input vector
is normalised to ensure its amplitudes lie in the range $[0,1]$.
Next, the normalised input vector is transformed into the desired quantum
state $\ket{\psi(x)}$ through a series of uniformly controlled rotations on
the qubits. The rotation on a given qubit $q_{s}$ is controlled by all
possible states of the previous qubits $q_{1},q_{2},\ldots,q_{s-1}$ using
multiple controlled rotations. The rotation angle $\beta_{i}$ is determined by
the association of the vector $v_{i}$ representing the $i_{th}$ classical
sample with the amplitudes of the original state. The state $\ket{\psi}$ then
is defined by this equation:

$\ket{\psi}=R(v^{i},\beta)\ket{q_{1}\ldots q_{s-1}}\ket{q_{s}}.$ (4)

Below, we provide the instructions for the Amplitude Encoding algorithm:

Algorithm 1 Amplitude Encoding

input a $p$-dimensional classical data point $x\in\mathbb{R}^{p}$, a number
$n$ of qubits, and a set of vectors $v_{i}$ representing the classical samples

pad the input vector $x$ with zero features as necessary to create a vector of
dimension $2^{n}$

normalise the input vector $x$ to ensure that its amplitudes lie in the range
$[0,1]$

initialise the quantum state $\ket{0}^{n}$, where each qubit is in the state
$\ket{0}$

Algorithm 2 Amplitude Encoding \- Part $2$

for each qubit $q_{s}$ do

for each classical sample $i$ do

calculate the rotation angle $\beta_{i}$ based on the amplitudes of the
original state and the associated vector $v_{i}$

apply the rotation gate $R(v_{i},\beta_{i})$ on qubit $q_{s}$

end for

end for

return encoded states $\ket{\psi}$

Additionally, many studies have shown that QML algorithms exhibit a higher
degree of consistency and less variation when the data is encoded using
Amplitude Encoding compared to other data encoding methods, such as basis
encoding. In particular, the quantum support vector classifier (QSVC) models
display a striking absence of variance between data points; see sierra2023data
for a full elucidation.

###  II.2 Encoding via Second-order Pauli Feature Maps

The Pauli feature map is another technique for encoding classical data into
quantum states. We can achieve this method by preparing an initial quantum
system and then applying a repeated sequence of unitary operations that
involve Hadamard and Pauli gates sierra2023data :

$\mathcal{U}_{\Phi(x)}=U_{\Phi(x)}H^{\otimes n}U_{\Phi(x)}H^{\otimes n},$ (5)

where we have that $U_{\Phi(x)}$ can be written as below:

$U_{\Phi(x)}=\exp\left(\imath\sum_{S\subseteq\left[n\right]}\phi_{S}(x)\prod_{i\in
S}P_{i}\right),$ (6)

the Pauli gates $P_{i}$ can be either $I,X,Y,$ or $Z$ gate, and the index $S$
denotes subsets of the set $[n]$ with size $\leqslant k$, describes the degree
of connectivity between various qubits or datapoints. The circuit $\phi_{S}$
parameters are defined by a nonlinear function of the input data as shown in
Eq. (7) below.

$\phi_{S}(x)=\begin{cases}x_{0},\;\quad\quad\quad\quad\quad\quad\text{if}\;k=1,\\\
\prod_{j\in S}\left(\pi-x_{j}\right),\quad\text{otherwise}.\end{cases}$ (7)

These parameters separate the different data classes while ensuring an
efficient circuit implementation. Below, we delineate Algorithm 3 for the
Pauli feature map encoding.

Algorithm 3 Pauli Feature Map Encoding

input:

$-$ $n$: number of qubits or data points

$-$ $x$: input vector of length $n$

$-$ $k$: maximum size of the subsets $S$

initialise quantum circuit with $n$ qubits

apply a layer of Hadamard gates to all qubits

for each subset $S$ of $\left[n\right]$ with size $\leqslant k$ do

apply a Pauli gate $P_{i}$ to each qubit in $S$, where
$P_{i}\in\left\\{I,X,Y,Z\right\\}$

apply a controlled-Z gate between every pair of qubits in $S$.

apply a nonlinear function of the form $\phi_{S}(x_{i})$ to each qubit in $S$

end for

apply a layer of Hadamard gates to all qubits

return encoded states $\ket{\psi}$

The coefficients $\phi_{S}$ are chosen such that the feature map can
efficiently separate the different data classes. For the specific Pauli
feature map mentioned in the passage, $k$ is set to $2$, $P_{i}$ is set to $Z$
for each qubit $i$, and $ZZ$ for each pair of qubits $i$ and $j$. The
resulting circuit is the ZZFeatureMap in Qiskit and IQPEmbedding in PennyLane.

###  II.3 ZZFeatureMap

ZZFeatureMap is a type of variational quantum circuit in Qiskit that maps
classical data to quantum states ibm ; it applies a series of single-qubit
rotations and two-qubit entangling gates to encode the classical data into the
quantum state. These gates generate a set of entangled states that can be used
as input to a quantum machine learning model.
This feature can be used by defining the number of qubits in the circuit,
which is typically determined by the dimensionality of the input data, and
then selecting the hyperparameters for the circuit, such as the number of
layers, the types of single-qubit rotations, and the types of entangling
gates. Finally, we can construct the ZZFeatureMap circuit.

###  II.4 IQPEmbedding

IQPEmbedding is a feature in PennyLane that enables the efficient preparation
of quantum states for Quantum Phase Estimation (QPE) pennylane . The
IQPEmbedding circuit takes in a unitary target operator and maps it onto a set
of small, highly entangled qubits, allowing for efficient QPE. The
IQPEmbedding uses a special type of circuit called an “interferometer quantum
circuit with parameterised gates” and is commonly used in variational
algorithms like the VQE for state preparation.
We can use this feature by defining the unitary target operator and selecting
the circuit’s hyperparameters. Finally, we can construct the IQPEmbedding
circuit.

##  III Using the Existing Classical-to-Quantum Encoding Methods on Genomic
Data

###  III.1 Amplitude Encoding

We implemented the Amplitude Encoding technique using Qiskit to map DNA
sequences to quantum states. Specifically, we represented each base in the DNA
sequence using a two-bit string and concatenated these strings to form a
binary string representing the entire DNA sequence. We then used this binary
string as the classical data vector for the Amplitude Encoding. We applied the
rotation gates to the qubits and obtained the resulting quantum state vector.
The code is applied in order to map a classical data vector of dimension $2$,
representing the DNA sequence A, to a quantum state of $2$ qubits. In this
example, each base in the DNA sequence is represented using two bits:
$\textbf{A}=00$, $\textbf{C}=01$, $\textbf{G}=10$, and $\textbf{T}=11$. The
resulting quantum state is a superposition of all possible combinations of
this base, each with a corresponding amplitude; we used the statevector()
function from the Qiskit library to represent the resulting quantum state as a
vector of complex numbers.
The output statevector

$\begin{pmatrix}0.25-4.33012702\times 10^{-01}\jmath&0.5-7.85046229\times
10^{-17}\jmath\\\ 0.5-8.32667268\times 10^{-17}\jmath&0.25+4.33012702\times
10^{-01}\jmath\\\ \end{pmatrix},$

shows that the amplitudes of the quantum state are very small, which is
expected given the small number of qubits involved; the first element in the
first row represents the probability amplitude of the state $\ket{00}$, the
second element in the first row represents the state $\ket{01}$, the first
element in the second row represents the state $\ket{10}$, and the second
element in the second row represents the state $\ket{11}$. This function also
provides the dimensions of the quantum state, which is a tensor product of $2$
two-dimensional Hilbert spaces.
To better visualise this state, we used the Hinton visualisation, which
represents the quantum state as a 2D matrix where the size and colour of each
square correspond to the magnitude and phase of the amplitude of that state,
respectively, as shown in Figure 4.

Figure 4: Hinton representation of quantum data for A using Amplitude
Encoding, with $\rho$ being the state vector of the sequence A with
$\text{Re}(\cdot)$ as the real part and $\text{Im}(\cdot)$ as the imaginary
part.

###  III.2 Encoding via Second-order Pauli Feature Maps

In this technique, we represented the genomic data as a binary string, with
each nucleotide constituted by a pair of bits. For example, we can represent
the sequence as $\textbf{A}=00$, $\textbf{C}=01$, $\textbf{G}=10$, and
$\textbf{T}=11$. Then, this binary string was fed into the Pauli feature map
circuit, which applied a series of Pauli gates and nonlinear functions to
encode the data into a quantum state. The challenge here was the choice of
Pauli gate $P_{i}$ and $\phi_{S}$ coefficients and the dyadic choice of two
ways to apply the ZZFeatureMap and IQPEmbedding.

####  III.2.1 ZZFeatureMap

In this technique, the genomic data is converted into a binary representation
comparable to the other methods; in our case, the DNA sequence was encoded as
a binary string. Then, ZZFeatureMap was used to map this binary string to a
quantum state, where each bit in the string corresponds to a single qubit.
The code provided XI demonstrates how to encode a DNA sequence into a quantum
state vector using a feature map and a quantum circuit. In this example, the
DNA sequence is AG, which implies that the circuit has two qubits, one for
each nucleotide.
The circuit encodes the DNA sequence by applying gates based on the
nucleotides of each qubit. Specifically, gate X is applied to qubits that
correspond to nucleotides A or C, and gate $Z$ is applied to qubits that
correspond to nucleotides G or T.
After applying the ZZFeatureMap to the circuit, as explained in the previous
paragraph, the quantum state vector is obtained by executing the circuit on a
simulation backend. The resulting state vector is $\left\langle
0.+0.\jmath,1.+0.\jmath,-0.+0.\jmath,-0.+0.\jmath\right\rangle$, with
dimensions $\left(2,2\right)$.
To provide a more precise representation of the quantum state vector, we used
the function plot_state_city from the qiskit.visualization library, In this
case, the Figure 5 shows a dark square on the second row, second column,
indicating that the probability of measuring the qubits in the state $\ket{0}$
is $1.0$, which represents the encoded data for the DNA sequence AG.

Figure 5: City representation of quantum data for AG using ZZFeatureMap.

####  III.2.2 IQPEmbedding

This technique implements a quantum circuit to encode a DNA sequence and
obtain the corresponding state vector (XI). The DNA sequence ATG is taken as
input and converted to qubits by the AngleEmbedding circuit. In this circuit,
each nucleotide of the DNA sequence is mapped to a qubit position using the
nucleotide_map dictionary. The $R_{Y}$ gate is then applied to each qubit to
encode the nucleotide as a rotation angle.
After encoding the DNA sequence, the $CNOT$ layer is applied to perform
entanglement between the qubits. Finally, the state of the qubits is measured,
and the state vector is returned. The output is a state vector representing
the quantum state of the DNA sequence, with amplitudes for each possible
state, as shown in the next expression:

$\begin{pmatrix}1.83697020\times 10^{-16}+0\jmath&-2.24963967\times
10^{-32}+0\jmath&-1.22464680\times 10^{-16}+0\jmath\\\
1.00000000+0\jmath&0.00000000+0\jmath&0.00000000+0\jmath\\\
0.00000000+0\jmath&0.00000000+0\jmath&0.00000000+0\jmath\\\
0.00000000+0\jmath&0.00000000+0\jmath&0.00000000+0\jmath\\\ \end{pmatrix}.$

The Bloch sphere representation for each qubit is chosen to understand the
results better; the Bloch sphere is used as a visual tool to represent the
state of a single qubit and allows for a straightforward interpretation of
quantum data, so Figure 6 represent the Bloch sphere rendition of each qubit
in the final statevector and shows that this DNA sequence ATG is converted to
$\ket{011}$.

Figure 6: Bloch sphere representation of quantum data for ATG using
IQPEmbedding.

##  IV Lossless Compression-Inspired Encoding Schemes

In the world of data structures, compression minimises the data size to save
storage space or transmission time sayood . The modus operandi of any
compression algorithm involves the removal of redundant or irrelevant
information from the data without losing quintessential details. This is
attained by using various algorithms and techniques that identify patterns or
similarities in the data and encode them in a more methodical, and well-
ordered, manner. Data compression algorithms come in two varieties: Lossy and
lossless. Below, we provide a curtailed description of both.

  1. 1.

Lossy Compression: These algorithms forego some information to achieve a
higher compression rate. The compressed data cannot be decompressed to the
exact original form, but it is usually acceptable for practical purposes.
Examples of lossy compression algorithms include the famous protocols MP3
(MPEG-1/2 Audio Layer III), JPEG, and MPEG.

  2. 2.

Lossless Compression: Lossless compression algorithms reduce the data size
without sacrificing any information, videlicet there is no information loss.
This implies that the compressed data can be decompressed to the original form
without losing quality. Examples of lossless compression protocols include
ZIP, GZIP, and PNG.

Lossless compression algorithms work by identifying patterns in the data and
replacing them symbolically with shorter codes, known as entropy coding. Based
on the aforementioned descriptions, we identify the following, albeit obvious,
advantages that lossless compression has over lossy compression and,
therefore, resort to developing quantum versions of classical lossless
compression algorithms.

  1. 1.

There is no Information Loss: The compressed data can be decompressed to its
exact original form without any loss of quality. This makes lossless
compression suitable for applications where preserving all the information is
essential, such as DNA sequencing and encryption, where conserving the
original data is indispensable.

  2. 2.

No Perceptual Assumptions are Required: Lossless compression algorithms do not
require assumptions or presuppositions about what parts of the data are more
important than others. This makes lossless compression more suitable for data
that cannot be easily segmented into perceptually important and unimportant
parts, such as DNA sequencing, since it does not make sense to say that one
segment of DNA is more “important” than the other.

  3. 3.

Recyclability of Compressed Data: Lossless compression allows for the original
data to be reconstructed with no loss of information and, therefore, reused
and repurposed. This means that the compressed data can be used repeatedly
without any loss in quality, making it suitable for DNA sequencing since a
compactified sequence can be used repeatedly.

  4. 4.

Lossless Compression Algorithms Generally Have Lower Computational Complexity
as Compared to Lossy Compression Algorithms: We provide a graphical rendition
of some common lossless versus lossy compression algorithms and show how some
commonly occurring lossless compression algorithms have a lower computational
complexity as compared to the common lossy compression algorithms.

Figure 7: DFT: $\mathcal{O}(k^{2})$; Wavelet Transform: $\mathcal{O}(k^{2})$;
Run-length Encoding: $\mathcal{O}(k)$; Huffman Coding: $\mathcal{O}(k\log k)$;
LZW: $\mathcal{O}(k^{2})$.

In Figure 7, we observe that it will be fruitful to design classical-to-
quantum encoding schemes based on lossless compression algorithms since the
computational time complexities are ordered as follows: $\text{Run-length
Encoding}\leq\text{Huffman Encoding}\leq\text{LZW Encoding}=\text{Wavelet
Encoding}=\text{DFT Encoding}$. It is important to note that the plot for the
DFT Encoding is not displayed due to its resemblance to the graphs of other
cases. Consequently, this plot was positioned underneath others and, as a
result, was not made visible

###  IV.1 A Quantum-influenced Huffman Coding Stratagem

Huffman coding Huffman  apportions varying-length codes to symbols based on
their frequency of occurrence in the input data. At its core, Huffman coding
represents frequently occurring symbols in the input data with shorter bit
sequences and less frequently repeated symbols with longer bit sequences. In
so doing, the algorithm achieves a higher compression ratio than fixed-length
coding schemes that use the same number of bits to represent each symbol,
regardless of its recurrence.
Architecturally, the algorithm builds a binary tree of nodes, where each leaf
node represents a symbol, and its weight is equal to its frequency of
occurrence in the input data. The algorithm starts by creating a list of all
the symbols and their frequencies and then repeatedly combines the two least
frequent symbols into a new node until all the symbols are contained within
the tree. The bit sequence for each symbol is then determined by traversing
the tree from the root to the corresponding leaf node and assigning a $0$ or
$1$ bit for each left or right turn in the path. In this scheme, we can
optimise the number of qubits used in such a manner that the encoded DNA
sequence is lean.

input a DNA sequence $\mathcal{D}$

for each nitrogenous base $b$ in the DNA sequence $\mathcal{D}$ do

apply count$(b)=C_{b}$ to tally up the frequency of each base

apply rank_order$(C_{b})=R$ to rank the bases from lowest to highest

apply build_tree$(R)=\mathcal{T}$ to construct the root nodes of the Huffman
tree

apply cascade_sum$(\mathcal{T})=S$ to sum up the frequencies in pairs of two
from the leftmost side and going up until the apex is reached

apply gen_code$(S)=G_{b}$ to assign binary digits along the edges, $E$, of the
tree

if pos$(E)$ is left then

$\text{code}\longleftarrow 0$

else

$\text{code}\longleftarrow 1$

end if

calculate the number of bits  $n_{b}=C_{b}\times\;\text{card}(G_{b})$

apply bin_encode$(G_{b})=\ket{\phi_{b}}$ to convert the bit strings to qubits

calculate the encoded quantum state  $\ket{\psi}=\bigotimes\limits_{\text{all
bases}}\ket{\phi_{b}}$

end for

return encoded states $\ket{\psi}$, total bits required sum$(n_{b})$

Algorithm 4 QuantHuff$(\mathcal{D})$

In Algorithm 17 above, the code takes in a DNA sequence $\mathcal{D}$ as
input, and for each nitrogenous base in the sequence, it counts the frequency
of the base, ranks them according to frequency from lowest to highest from
left to right. The code then graphically constructs the tree and then sums the
frequency in pairs of two starting from the leftmost side, and building its
way up until it reaches the tip of the tree. The algorithm then assigns binary
bits ($0$ or $1$) to the tree based on the following criteria: If the edge is
to the left side, then it is allocated a $0$, and if it is to the right side,
it is allocated a $1$.
Thereafter, the number of bits required to encode each nitrogenous base is
calculated according to the simple formula of the product between the tally of
each base in the sequence with the cardinality of each encoded bitstring of
the respective base. Penultimately, the algorithm applies a simple binary
encoding function that converts a $0$ into a quantum state $\ket{0}$ and $1$
into a quantum state $\ket{1}$. Lastly, the algorithm calculates the encode
quantum state by taking the tensor product of each constituent base state. The
algorithm then outputs the encoded quantum state and the sum of the number of
bits to give the optimal number of bits required to encode the DNA sequence.
Consider, for example, the M13 filamentous bacteriophage universal reverse
primer DNA sequence m13 :
$\boldsymbol{5^{\prime}-\textbf{CAGGAAACAGCTATGACC}-3^{\prime}}$ commonly
encountered in cloning and PCR testing. Below we apply the encoding scheme,
not accounting for the prefix and suffix numbers and hyphens, respectively,
and provide a pictorial representation of the algorithm to obtain the encoded
quantum state $\ket{\psi}$.

Table 3: Count of the nitrogenous bases in the M13 bacteriophage DNA sequence Nitrogenous Base |  Count
---|---
C |  5
A |  7
G |  4
T |  2
Total |  $\boldsymbol{18}$

Figure 8: Graphical representation of the nitrogenous bases with their counts and codes along the edges respectively. Table 4: Code determination for each nitrogenous base. Nitrogenous Base |  Count |  Code |  Bits
---|---|---|---
C |  5 |  10 |  $5\times 2=10$
A |  7 |  11 |  $7\times 2=15$
G |  4 |  01 |  $4\times 2=8$
T |  2 |  00 |  $2\times 2=4$
Total |  $\boldsymbol{18}$ |  - |  $\boldsymbol{36}$

Thus, we now apply binary encoding to convert the bits into qubits, videlicet
$0\longrightarrow\ket{0},1\longrightarrow\ket{1}$, to obtain the encoded
quantum state for the M13 bacteriophage sequence:

$\displaystyle\textbf{CAGGAAACAGCTATGACC}\longrightarrow\ket{\psi}=$
$\displaystyle\;\ket{10}\otimes\ket{11}\otimes\ket{01}^{\otimes
2}\otimes\ket{11}^{\otimes 3}\otimes\ket{10}$
$\displaystyle\;\otimes\ket{11}\otimes\ket{01}\otimes\ket{10}\otimes\ket{00}\otimes\ket{11}$
$\displaystyle\;\otimes\ket{00}\otimes\ket{01}\otimes\ket{11}\otimes\ket{10}^{\otimes
2}.$

###  IV.2 Quantum-influenced Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) bw  is a reconstructible text
transformation that interchanges the characters in a string in such a manner
that it can be compressed without information loss. The BWT is based on the
concept of cyclic shifts, which involve shifting the characters of a string
from one position to the left and wrapping the last character to the beginning
of the string. In order to successfully carry out a BWT on a string, we first
append a special end-of-string marker to the string. Then, a matrix of all the
cyclic shifts of the string is constructed and sorted in alphabetical order.
The last column of this matrix is the BWT of the string.
The BWT can be used for compression by exploiting the fact that the last
column of the matrix is most often highly repetitive, with runs of identical
characters. These runs can be encoded more efficiently than individual
characters, resulting in data condensation. Within the Biosciences, the BWT is
in the construction of the Burrows-Wheeler Aligner (BWA) software invented by
Li and Durbin in the C++ language LiDurbin , which is an exhaustively used
tool for mapping DNA sequences to a reference genome. Owing to the fact that
DNA sequences contain large amounts of repetitive nitrogenous bases and,
therefore, repetitious information, the BWT can be used to exploit this
redundancy and compress the sequence without losing information.
This compression can reduce storage requirements and improve the speed of
sequence analysis. In addition, the BWT is used in De Novo genome assembly
KimuraKoike , Sequence Annotation Adjeroh , and Motif Finding (repeating
patterns in DNA) motif  for the construction of data structures. Taking
motivation from its immense success in various DNA sequencing applications, we
combine quantum computing in parallel with the BWT protocol for encoding.
Below, we present a novel classical-to-quantum encoding scheme that uses the
BWT.

Algorithm 5 QBWT$(\mathcal{D})$

input a DNA sequence $\mathcal{D}\in\mathbb{S}$

initialise a quantum state $\ket{\psi}=\ket{0}^{\otimes n}$

for each nitrogenous base in $\mathcal{D}$ do

apply cyc_perm$(\mathcal{D})=\mathcal{D}^{\prime}$ exhaustively, until there
are no repeats

apply arrange$(\mathcal{D}^{\prime})=\mathcal{D}^{\prime\prime}$ to
alphabetically arrange $\mathcal{D}^{\prime}$

apply extract$(\mathcal{D}^{\prime\prime})=\mathcal{D}^{\prime\prime\prime}$
to obtain the last nitrogenous bases, and index $j$ of the original DNA
sequence from $\mathcal{D}^{\prime\prime}$

apply the concat$(\mathcal{D}^{\prime\prime\prime},j)$ to link together the
terminal bases and index of the original DNA sequence

for each nitrogenous base $b\in\mathcal{D}^{\prime\prime\prime}$ do

apply the unitary transformation
$U_{b}=\exp\left[\frac{2\pi\imath\times\texttt{count}(b)}{n}\right]\times
R_{b}$

end for

end for

return encoded states $\ket{\psi}$

In Algorithm 5, we observe that the algorithm possesses quadratic time
complexity, $\mathcal{O}(k^{2})$. Upon analysis of Algorithm 5, we observe
that the first for loop is the steps for the classical BW transform, and the
second for loop is the quantum part. We also take heed of the following
notations: $\mathbb{S}$ denotes the space of all possible DNA sequences, $n$
is the number of qubits, the function cyc_perm$(\cdot)$ computes the number of
cyclic permutations of the DNA sequence, the function arrange$(\cdot)$
provides an alphabetically-ordered arrangement of all the permutations of the
DNA sequence, the extract$(\cdot)$ function draws out all the terminal
nitrogenous bases from the alphabetically-ordered permutations, the function
count$(b)$ counts the number of occurrences of nitrogenous base $b$ in
$D^{\prime\prime\prime}$ and $R_{b}$ is the rotation operator that maps
$\ket{0}\longrightarrow\ket{b}$.
The code XI provided implements the QBWT algorithm using the Qiskit library
for quantum computing ibm . The QBWT function takes a DNA sequence as input
and performs the classical BWT step using the arrange function to generate the
transformed sequence. It then initialises a quantum circuit with $n$ qubits
(where $n$ is the length of the sequence) and applies a series of quantum
rotations to each qubit based on the frequency of each base in the transformed
sequence. Finally, it measures all the qubits and returns the counts of each
measurement outcome.
This implementation of the QBWT algorithm provides a simple example of how we
can encode DNA sequences into quantum data. The results of the QBWT algorithm
are the counts of the measurement outcomes of the final quantum state after
the quantum phase estimation step. These counts represent the probabilities of
observing each possible outcome when measuring the state and can be
interpreted as an encoded representation of the input DNA sequence. The counts
represent the frequency of each combination of bases in the input DNA
sequence.
For example, if the input DNA sequence is ACTGACGTAGC, it has a length of
$10$, so the quantum circuit has ten qubits. The circuit first applies the
Burrows-Wheeler Transform (BWT) classically to the input sequence, which
produces a new string where each character corresponds to the last character
of one of the cyclic permutations of the input sequence, arranged in
alphabetical order.
In this case, the BWT of ACTGACGTAGC is CTTTTGGAAAA since the cyclic
permutations are ACTGACGTAGC, CTAGCAGTACG, GACGTAGCACT, TAGCACTGACG,
AGCACTGACGT, GTAGCACTGAC, ACGTAGCACTG, CACTGACGTA, TTTGGAAAAA, and AAAACTTTTG,
and the last character of each permutation, arranged alphabetically, is
CTTTTGGAAAA.
The circuit then applies the quantum phase estimation algorithm to the qubits,
where each qubit corresponds to one base in the input sequence. For each base
in the input sequence, the algorithm counts the number of occurrences of that
base in the BWT and uses that count to apply a rotation gate to the
corresponding qubit. The rotation angle is proportional to the count of the
base divided by the length of the input sequence and is given by the formula:
$\theta=2*\pi*count/n$, where $n$ is the length of the input sequence.
Finally, the circuit measures all of the qubits and returns the counts of each
measurement outcome, where each count corresponds to a binary string of length
$n$. In this case, as shown in Figure 9, we have $18$ different binary
strings, each representing a different state of the quantum circuit. The most
common state, measured $894$ times, is the all-zero state $0000000000$, which
corresponds to the case where none of the qubits is rotated. The least common
states, each measured only once, are $0000100100$, $0001010010$, $0011000000$,
and $0100000000$.

Figure 9: The results of CTTTTGGAAAA using QBWT on QasmSimulator with $1024$
shots.

##  V Wavelet-Inspired Encoding Schemes

Wavelets are mathematical functions that can be used to analyse and transform
signals in both the time and frequency domains. Ubiquitously, they are
encountered in the field of signal processing due to their ability to provide
more detailed information about a signal than traditional Fourier transforms.
The most common type of wavelet is the mother wavelet, which can be scaled and
translated in order to analyse signals at different frequencies and time
intervals. The wavelet transform involves taking the inner product of the
signal with the scaled and translated wavelet function. Mathematically, a
wavelet can be expressed in terms of its transform, known as the wavelet
transform. For a given mother wavelet $\Psi(t)$ and signal $f(t)$, the wavelet
transform is given by

$W(a;b)\overset{\Delta}{=}\frac{1}{\sqrt{|a|}}\int_{-\infty}^{+\infty}f(t)\Psi^{*}\left(\frac{t-b}{a}\right)dt,$
(8)

where $a$ is the scale factor, $b$ is the translation factor, and the ∗
operator denotes the complex conjugate. Whereas a Fourier transform is
stationary in time, and therefore can only account for localised signal
variations, wavelet transforms are dynamic in time, and thus can encapsulate
both localised, as well as globalised, changes in the signal. In addition, a
wavelet can simultaneously capture temporal and frequency information, whereas
a Fourier transform can only provide information about frequency.
Below, we present a wavelet-inspired encoding scheme that can handle DNA
sequence image data; in stark contrast to the other schemes presented which
attempt to encode the DNA sequences directly. This scheme can work well with
image data, processing, compression, and analysis. For an $M\times
N$-dimensional grayscale image data, we provide the Algorithm 6 for encoding
the classical data into quantum states:

Algorithm 6 CosineEncoding$(\mathcal{D})$

input an $\left(M\times N\right)$-dimensional grayscale image dataset
$\mathcal{D}\in\mathbb{R}^{M\times N}$

for each row index in $M$, and each column index in $N$ do

calculate the two-dimensional Discrete Cosine Transform of the image according
to  $\displaystyle F(\alpha,\beta)=$
$\displaystyle\;\frac{C_{\alpha}}{2}\frac{C_{\beta}}{2}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)\cos\left[\frac{\alpha\pi\left(2x+1\right)}{2M}\right]\cos\left[\frac{\beta\pi\left(2y+1\right)}{2N}\right],$
$\displaystyle C_{\alpha},C_{\beta}=$
$\displaystyle\;\begin{cases}\frac{1}{\sqrt{2}},\quad\alpha,\beta=0,\\\
1,\;\;\quad otherwise.\end{cases}$

find $F_{\max}=\underset{\alpha\in M,\beta\in N}{\max}||F(\alpha,\beta)||$

normalise each value according to
$\widehat{F}(\alpha,\beta)=\frac{F(\alpha,\beta)}{F_{\max}}$

for each element in $\widehat{F}{i}(\alpha,\beta)$ do

map $||\widehat{F}(\alpha,\beta)||\longrightarrow$ $a_{i},1\leq
i\leq\text{card}(\widehat{F}(\alpha,\beta))=n$ to form an $n$-qubit register

apply a QFT to each state in the n-qubit register:
$\text{QFT}_{n}\ket{p}=\frac{1}{\sqrt{n}}\sum_{q=0}^{n-1}\exp\left(\frac{2\pi\imath
pq}{n}\right)\ket{q}.$

end for

end for

return encoded $2^{n}$-dimensional dataset of quantum states
$\mathcal{D}^{\prime}\in\mathcal{H}$

In Algorithm 6, $f(x,y)\in\left[0,255\right]$ denotes the intensity of the
pixels for an 8-bit value, $\alpha,\beta$ are the positions, and
$C_{\alpha},C_{\beta}$ are the scale factors. We also observe that this
algorithm displays quadratic time complexity, $\mathcal{O}(k^{2})$. This
algorithm encodes a DNA sequence into a quantum state using a quantum circuit.
The input DNA sequence is converted into a quantum state by initialising each
base as a quantum state. If the base is A or G, it is initialised as the
$\ket{0}$ state, while if it is C or T, it is initialised as the $\ket{1}$
state. For G and T, an $X$ gate is applied before initialisation to convert
the $\ket{1}$ state to the $\ket{0}$ state.
The quantum Fourier transform is then applied to each qubit of the circuit,
transforming the quantum state into a superposition of all possible states.
This is achieved by applying a series of Hadamard and controlled-phase gates
to each qubit of the circuit. Finally, the qubits are measured to obtain
classical data, and the statevector of the circuit is obtained using the
StatevectorSimulator from the Qiskit Aer package. The statevector represents
the probability amplitudes of each possible system state.
For example, consider the DNA sequence ATC. The quantum state obtained after
encoding this sequence is given as the statevector

$\left\langle
0.+0.\jmath,-0.+0.\jmath,0.+0.\jmath,0.70710678+0.70710678\jmath,-0.+0.\jmath,0.+0.\jmath,0.+0.\jmath,0.-0.\jmath\right\rangle,$

this implies that a $70.7\%$ probability of the third qubit being in the state
$\ket{1}$ and a $50\%$ probability of the first qubit being in the state
$\ket{0}$.
The plot_state_paulivec function was used to visualise the quantum state as a
vector of probabilities along the Bloch sphere’s $I$, $X$, $Y$, and $Z$ axes,
as shown in Figure 10.

Figure 10: Pauli representation of quantum data for ATC using Cosine Encoding.

By representing the state vector of a multi-qubit system in the Pauli basis,
we can see how much of each Pauli matrix is present in the state. So in our
example, the state vector corresponds to the DNA sequence ATC, which has a
length of $3$. The resulting statevector has eight components since there are
three qubits, each of which can be in either the $\ket{0}$ or $\ket{1}$ state.
Plotting the state vector in the Pauli basis shows that the state mainly
comprises the $Z$ matrix, with some contribution from the $X$ matrix; this
tells us that the state is mainly in the $\ket{0}$ state for all three qubits,
with a small probability of being in the $\ket{1}$ state for the second qubit,
as we can see this in the Figure 11.

Figure 11: City representation of quantum data for ATC using Cosine Encoding.

##  VI Entropy-based Methods

In information theory, entropy is defined as the average amount of information
contained in each message or symbol in a message. This average is calculated
based on the probability distribution of the symbols in the message. The
entropy of a system is the greatest when all possible messages are equally
likely, and least when a message is certain to occur. Within ML, entropy is
used to measure the impurity of a dataset. The information gain is calculated
as the difference between the original dataset’s entropy and the predicted
values output from the model. ML algorithms based upon entropy methods try to
maximise the information gain, leading to a more pure (less uncertain) dataset
in the resulting groups.
Entropy-based methods for encoding are a natural consequence when comparing an
encoded DNA sequence to a reference DNA sequence. It is also reasonable to
assume that DNA sequences have a high degree of inherent randomness.
Thus, we provide a class of algorithms built upon entropy-based schemes below.

###  VI.1 Encoding Based on the Lowest Entropy, and Fixed DNA subsequence
Lengths

Algorithm 7 SEncode$(\mathcal{D},n)$

input a DNA sequence $\mathcal{D}\in\mathbb{S}$ of length $N,|\mathcal{D}|=N$
and the number of qubits $n$

initialise an $n$-qubit register in the $\ket{0}$ state, $\ket{0}^{\otimes n}$

for each nitrogenous base $b_{i}\in\mathcal{D}$ do

calculate the probability of occurrence of the bases
$p(b_{i})=\frac{\text{Number of occurrences of}\;b_{i}}{N},\quad
b_{i}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$

calculate the information entropy of the entire DNA sequence
$H(\mathcal{D})=-\sum_{i\in\mathcal{D}}p(b_{i})\log_{2}\left[p(b_{i})\right]$

calculate $K=\lceil\log_{2}(N)\rceil,M=\lceil\frac{N}{K}\rceil$

apply fragment$(\mathcal{D})$ to subdivide the DNA sequence into $M$ segments
each of size $K$ such that $\mathcal{D}=\bigcup_{i=1}^{M}\mathcal{D}_{i}$

for each fragmented DNA sequence do

calculate the probability of the nitrogenous base in the segment

calculate the entropy of each segment

calculate the maximum entropy from all segments
$H_{\max}=\max\left\\{H(\mathcal{D}_{1}),H(\mathcal{D}_{2}),\ldots,H(\mathcal{D}_{M})\right\\}$

normalise entropy in each segment
$\widehat{H}(\mathcal{D}_{i})=\frac{H(\mathcal{D}_{i})}{H_{\max}}$

apply the sort_low_high$(\widehat{H}(\mathcal{D}_{i}))=\mathscr{H}$ to order
the normalised entropies from lowest to highest

Algorithm 8 SEncode$(\mathcal{D},n)$ \- Part $2$

for each segmented DNA sequence $\mathcal{D}_{i}$ corresponding to
$\mathscr{H}$ do

synthesise quantum states $\ket{\psi_{i}}$ corresponding to each DNA segment

apply a unitary operator to map $\ket{0}\longrightarrow\ket{i}$
$U_{i}:\ket{0}\longrightarrow\ket{i}\otimes\ket{0}$

apply a Hadamard gate to each qubit in the first register to create a
superposition

end for

form the encoded state  $\ket{\psi}=\bigotimes\limits_{i=1}^{M}\ket{\psi_{i}}$

end for

end for

return encoded states $\ket{\psi}$

Algorithm 7 takes a DNA sequence $\mathcal{D}$ of length $N$ and the number of
qubits $n$ as input and produces an encoded quantum state $\ket{\psi}$ as
output. The encoding is done by mapping each segment of the DNA sequence into
a corresponding quantum state. The SEncode algorithm subdivides the DNA
sequence into $M$ segments, each of size $K$. The algorithm then calculates
the probability of occurrence of each nitrogenous base in the DNA sequence,
the entire DNA sequence’s information entropy, and each segment’s entropy. The
maximum entropy among all the segments is then used to normalise the entropy
in each segment. The normalised entropies are then sorted from lowest to
highest.
The algorithm synthesises a corresponding quantum state for each segment and
applies a unitary operator to map $\ket{0}$ to the corresponding segment
index. A Hadamard gate is applied to each qubit in the first register to
create a superposition. Finally, the algorithm forms the encoded quantum state
by taking the tensor product of all the synthesised quantum states.
For example, consider the DNA sequence $\mathcal{D}=$ ATCG, the number of
nitrogenous bases $N=4$, we assume that we want to encode the DNA sequence
into a $2$-qubit quantum state. The algorithm would first subdivide the DNA
sequence into two segments of size $2$: $\mathcal{D}_{1}=$ AT and
$\mathcal{D}_{2}=$ CG. The algorithm would then calculate the probability of
occurrence of each nitrogenous base, the information entropy of the entire DNA
sequence, and the entropy of each segment.
As an example, assume that the normalised entropy of $\mathcal{D}_{1}$ is
$0.5$, and the normalised entropy of $\mathcal{D}_{2}$ is $0.5$. The algorithm
would synthesise quantum states corresponding to each segment by applying a
unitary operator to map $\ket{0}$ to the corresponding segment index and
applying a Hadamard gate to each qubit in the first register to create a
superposition; we get the quantum states
$\ket{\psi_{1}}=\frac{1}{\sqrt{2}}\left(\ket{0}+\ket{1}\right)$ and
$\ket{\psi_{2}}=\frac{1}{\sqrt{2}}\left(\ket{0}-\ket{1}\right)$, corresponding
to the segments $\mathcal{D}_{1}=$ AT and $\mathcal{D}_{2}=$ CG, respectively.
Finally, the algorithm would form the encoded quantum state as
$\ket{\psi}=\ket{\psi_{1}}\otimes\ket{\psi_{2}}=\frac{1}{2}\left(\ket{00}+\ket{01}-\ket{10}-\ket{11}\right)$.

###  VI.2 Encoding Based on Reference Data

input a DNA sequence $\mathcal{D}$ and a reference DNA sequence
$\mathcal{D}_{\text{ref}}$ of the same length,
$|\mathcal{D}|=|\mathcal{D}_{\text{ref}}|=N$

for each nitrogenous base
$b_{i}\in\mathcal{D},b_{i}^{\text{ref}}\in\mathcal{D}_{\text{ref}}$ do

calculate the probability of occurrence of the bases  $\displaystyle
P(b_{i})=$ $\displaystyle\;\frac{\text{Number of occurrences
of}\;b_{i}}{N},\quad
b_{i}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$
$\displaystyle Q(b_{i}^{\text{ref}})=$ $\displaystyle\;\frac{\text{Number of
occurrences of}\;b_{i}^{\text{ref}}}{N},\quad
b_{i}^{\text{ref}}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$

calculate the KL divergence between the $\mathcal{D}$ and
$\mathcal{D}_{\text{ref}}$ probability distributions
$D_{KL}(P||Q)=\sum_{\text{all bases}}P(b)\log\left[\frac{P(b)}{Q(b)}\right]$

calculate the number of qubits required for some adjustable hyperparameter
$0\leq\alpha\leq 1$ $n=\alpha\times\lceil D_{KL}(P||Q)\rceil$

create the quantum state by mapping
$\ket{\psi}:\mathcal{D}\longrightarrow\mathcal{D}_{\text{ref}}$ in $n$-qubit
registers

end for

return encoded quantum state $\ket{\psi}$

Algorithm 9 NZ22$(\mathcal{D},\mathcal{D}_{\text{ref}})$

While this Algorithm 8 may be effective, we identify that the choice of the KL
metric has several flaws. We discuss them below:

  1. 1.

It does not account for overlaps between the DNA and DNA reference sequences
probability distributions.

  2. 2.

It is not symmetrical. This means that the order of the respective probability
distributions matter and, thus, significantly impact the results.

  3. 3.

Since we are mapping the DNA sequence to the computational basis
$\left\\{\ket{0},\ket{1}\right\\}$, it makes sense to have a divergence
measure that is in the range $\left[0,1\right]$. However, the KL metric is
$\left[0,\infty\right)$.

Let us consider a practical example to understand how this algorithm works;
suppose we have two DNA sequences, $\mathcal{D}$ and
$\mathcal{D}{\text{ref}}$, of length $N=1000$ nucleotides each. We want to
encode $\mathcal{D}$ into a quantum state using $\mathcal{D}{\text{ref}}$ as a
reference sequence. We apply the NZ22 algorithm as follows:
First, we calculate the probability of occurrence of each nitrogenous base in
$\mathcal{D}$ and $\mathcal{D}_{\text{ref}}$. For example, if we have $300$
Adenine (A) nucleotides in $\mathcal{D}$, the probability of occurrence of A
in $\mathcal{D}$ is $P(\textbf{A})=\frac{300}{1000}=0.3$. Similarly, if we
have $250$ Thymine (T) nucleotides in $\mathcal{D}_{\text{ref}}$, the
probability of occurrence of T in $\mathcal{D}_{\text{ref}}$ is
$Q(\textbf{T})=\frac{250}{1000}=0.25$. We calculate these probabilities for
all nitrogenous bases in both sequences.
Next, we calculate the KL divergence between the probability distributions of
$\mathcal{D}$ and $\mathcal{D}_{\text{ref}}$. The KL divergence measures how
different two probability distributions are from each other. In our example,
suppose we calculate $D_{KL}(P||Q)=0.05$, which indicates that the probability
distributions of $\mathcal{D}$ and $\mathcal{D}_{\text{ref}}$ are somewhat
different from each other.
We then calculate the number of qubits required to encode $\mathcal{D}$ into a
quantum state. We use an adjustable hyperparameter $0\leq\alpha\leq 1$ to
control the number of qubits. In our example, suppose we set $\alpha=1$. We
calculate the number of qubits required as $n=\alpha\times\lceil
D_{KL}(P||Q)\rceil=1\times\lceil 0.05\rceil=1$. This means we need one qubit
to encode $\mathcal{D}$ into a quantum state.
Finally, we create the quantum state by mapping the nucleotides of
$\mathcal{D}$ to the reference sequence $\mathcal{D}_{\text{ref}}$ using the
one qubit register. The mapping is done in such a way that if a nucleotide in
$\mathcal{D}$ matches a nucleotide in $\mathcal{D}_{\text{ref}}$, the qubit
state is set to $\ket{0}$, and if they don’t match, the qubit state is set to
$\ket{1}$. This creates an encoded quantum state $\ket{\psi}$ that represents
the differences between $\mathcal{D}$ and $\mathcal{D}_{\text{ref}}$. We
propose Algorithm 10 that uses the Bhattacharyya divergence measure Bhatt1 ;
Bhatt2  to overcome the drawbacks of the KL divergence alluded to above.

Algorithm 10 NZ23$(\mathcal{D},\mathcal{D}_{\text{ref}})$

Input a DNA sequence $\mathcal{D}$ and a reference DNA sequence
$\mathcal{D}_{\text{ref}}$ of the same length,
$|\mathcal{D}|=|\mathcal{D}_{\text{ref}}|=N$

for each nitrogenous base
$b_{i}\in\mathcal{D},b_{i}^{\text{ref}}\in\mathcal{D}_{\text{ref}}$ do

Calculate the probability of occurrence of the bases  $\displaystyle
P(b_{i})=$ $\displaystyle\;\frac{\text{Number of occurrences
of}\;b_{i}}{N},\quad
b_{i}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$
$\displaystyle Q(b_{i}^{\text{ref}})=$ $\displaystyle\;\frac{\text{Number of
occurrences of}\;b_{i}^{\text{ref}}}{N},\quad
b_{i}^{\text{ref}}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$

Calculate the Bhattacharyya divergence between the $\mathcal{D}$ and
$\mathcal{D}_{\text{ref}}$ probability distributions
$D_{B}(P||Q)=-\log\left[\sum_{\text{all bases}}\sqrt{P(b)\times Q(b)}\right]$

Calculate the number of qubits required for some adjustable hyperparameter
$0\leq\alpha\leq 1$ $n=\alpha\times\lceil D_{B}(P||Q)\rceil$

Apply Amplitude Encoding to obtain state $\ket{\psi}$ based on $n$ qubits

end for

return encoded states $\ket{\psi}$

Suppose we have a DNA sequence $\mathcal{D}$ of length $N=10$:
$\mathcal{D}=\textbf{TACAGTTGCA}$, We also have a reference DNA sequence
$\mathcal{D}_{\text{ref}}$ of the same length:
$\mathcal{D}_{\text{ref}}=\textbf{AGCTGACTCA}$

To encode this DNA sequence into a quantum state using NZ23, we follow the
steps outlined in Algorithm 10.

Firstly, we calculate the probability distributions of each base in the input
sequence and the reference sequence. For example, the probability of the base
T occurring in $\mathcal{D}$ is:

$P(\textbf{T})=\frac{\text{number of {T}'s in
}\mathcal{D}}{N}=\frac{3}{10}=0.3.$

Similarly, we can calculate the probability distribution of each base in the
reference sequence $Q(b_{i}^{\text{ref}})$.

Next, we calculate the Bhattacharyya divergence between the probability
distributions of $\mathcal{D}$ and $\mathcal{D}_{\text{ref}}$. This tells us
how different the two probability distributions are, which gives us an
estimate of how many qubits we need to encode the DNA sequence into a quantum
state.

For this example, the Bhattacharyya divergence is:

$D_{B}(P||Q)=-\log\sum_{b\;\in\;\left\\{\textbf{A},\textbf{C},\textbf{G},\textbf{T}\right\\}}\sqrt{P(b)\times
Q(b)}\approx 0.01.$

The next step is determining the qubits needed to encode the DNA sequence.
This is determined by a hyperparameter $\alpha$ between 0 and 1 and can be
adjusted to trade-off between accuracy and computational resources. For this
example, let’s set $\alpha=1$.

Using the Bhattacharyya divergence and $\alpha$, we calculate the number of
qubits required as:

$n=\alpha\times\lceil D_{B}(P||Q)\rceil=1\times\lceil 0.01\rceil=1.$

This means we need one qubit to encode this DNA sequence into a quantum state.

Finally, we obtain the quantum state using Amplitude Encoding. For this
example, we can encode the state $\ket{\psi}$ as:

$\ket{\psi}=\sqrt{P(\textbf{T})}\ket{\textbf{T}}+\sqrt{1-P(\textbf{T})}\ket{\neg\textbf{T}}=\sqrt{0.3}\ket{\textbf{T}}+\sqrt{0.7}\ket{\neg\textbf{T}},$

where $\ket{\neg\textbf{T}}$ denotes a superposition of the other three bases
(A, C, and G), and $\neg$ is the logical NOT operator.
So, the NZ23 algorithm takes a DNA sequence and a reference sequence as input,
calculates the probability distributions of each base, computes the
Bhattacharyya divergence between the two probability distributions, and uses
amplitude encoding to encode the DNA sequence into a quantum state. The number
of qubits required for encoding is determined by a hyperparameter $\alpha$.

###  VI.3 Information Geometry Methods

Computational information geometry is the amalgamation of Differential
Geometry and Information Theory that studies the properties of probability
distributions, generalised entropy measures, and their relationships to
Statistics, Probability Theory, Information, Machine Learning, Deep Learning,
and Big Data Frank . Given a manifold $\mathscr{M}\left(X,g\right)\in
C^{\gamma}$ that is smooth and potentially infinitely differentiable, we would
like to explicate an information metric, $g_{ij}$, to define the concept of
distance between probability distributions; a common information distance
measure is the Fischer Information Metric: For a continuous random variable
$X$ with parameterised probability distribution $p_{\boldsymbol{\theta}}(x)$:

$g_{ij}(\boldsymbol{\theta})=\int_{X}p_{\boldsymbol{\theta}}(x)\nabla_{\boldsymbol{\theta}_{i}}p_{\boldsymbol{\theta}}(x)\nabla_{\boldsymbol{\theta}_{j}}p_{\boldsymbol{\theta}}(x)\;dx.$
(9)

Thereafter, an entropy measure is defined to measure the dissimilarity and
discrepancy between probability distributions; most commonly, this is the
Kullback-Liebler or Jensen-Shannon divergences: Given two continuous
probability distributions $p(x)$ and q(x),

$\displaystyle D_{KL}(p(x)||q(x))=$
$\displaystyle\;\int_{\mathscr{M}}p(x)\log\left[\frac{p(x)}{q(x)}\right]\;dx,$
(10.1) $\displaystyle D_{JS}(p(x)||q(x))=$
$\displaystyle\;\frac{D_{KL}(p(x)||m(x))+D_{KL}(q(x)||m(x))}{2},$ (10.2)

where $m(x)=\frac{p(x)+q(x)}{2}$. Below, we provide the Algorithm 11 for
classical-to-quantum encoding using information geometry.

Algorithm 11 QuantIG$(\mathcal{D},\mathcal{D}_{\text{ref}})$

input a DNA sequence $\mathcal{D}$ and a reference DNA sequence
$\mathcal{D}_{\text{ref}}$ of the same length
$|\mathcal{D}|=|\mathcal{D}_{\text{ref}}|=N$

for each base
$b_{i}\in\mathcal{D},b_{i}^{\text{ref}}\in\mathcal{D}_{\text{ref}}$ do

calculate the probability of occurrence of the bases  $\displaystyle
p(b_{i})=$ $\displaystyle\;\frac{\text{Number of occurrences
of}\;b_{i}}{N},\quad
b_{i}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$
$\displaystyle q(b_{i}^{\text{ref}})=$ $\displaystyle\;\frac{\text{Number of
occurrences of}\;b_{i}^{\text{ref}}}{N},\quad
b_{i}^{\text{ref}}\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}$

calculate an information metric, $g$, between the probability distributions
$p$ and $q$

construct a Riemannian manifold $\mathscr{M}(X,g)$ for the probability
distributions

perform state mapping from the manifold $\mathscr{M}$ to a Hilbert space
$\mathcal{H}$ that creates a basis:
$\ket{x}:\mathscr{M}\longrightarrow\mathcal{H}$

calculate the linear operator  $\mathscr{L}\ket{x}=\sqrt{p(x)}\ket{x}$

calculate the metric operator
$\mathscr{G}\ket{x}=g(x,x)\ket{x}\bra{x}+\sum_{x\neq y}g(x,y)\ket{x}\bra{y}$

calculate the quantum states
$\ket{\psi}=\mathscr{L}^{-1/2}\mathscr{G}\mathscr{L}^{-1/2}\ket{0}$

end for

return encoded states $\ket{\psi}$

The QuantIG algorithm takes a DNA sequence and a reference sequence as inputs,
calculates the probability of occurrence of each base and constructs a
Riemannian manifold for the probability distributions. It then maps the state
from the manifold to Hilbert space and calculates the quantum states using
linear and metric operators. The resulting encoded states can be used for
various quantum information processing tasks like similarity search and
classification. The manifold can be constructed as follows:

  1. 1.

Defining the Probability Space: Pick a non-varying sample space $\Omega$, or a
subset $\omega\subseteq\Omega$, that is bounded and smooth, over the
probability distributions.

  2. 2.

Defining the Tangent Space: Consider small perturbations of the probability
distributions while preserving the normalisation constants.

  3. 3.

Metric Construction: This is accomplished by defining a suitable distance
measurement, depending on the application, that satisfies the properties of
being smooth and continuous, positive-definite, and having a symmetric
bilinear form, for the probability distributions. Given the probability
distributions $P$ and $Q$, with associated tangent vectors $X$ at tangent
space $T_{P}$, and $Y$ at tangent space $T_{Q}$ respectively, and metric $g$,
the commonly used metrics are:

    1. 3.1.

Fischer-Rao Metric: $g_{P}(X,Y)\overset{\Delta}{=}\frac{1}{4}\int\frac{d\log
P}{dx}\frac{d\log Q}{dx}\;dx$.

    2. 3.2.

Wasserstein / Earth Mover’s Distance / Optimal Transport: Measures the amount
of “work” required to transform one probability distribution into the other:
$g_{\mathcal{P}}(P,Q)\overset{\Delta}{=}\inf\left\\{\int||x-y||^{\mathcal{P}}\;d\gamma(x,y)\right\\}^{1/\mathcal{P}}$,
where $\mathcal{P}$ is a control parameter that regulates the smoothness of
the distance, and $\gamma(x,y)$ is a joint probability distribution function
on the product space $x\times y$ that has $P$ and $Q$ are marginal probability
distributions.

    3. 3.3.

Hellinger Distance:
$g(P,Q)\overset{\Delta}{=}\frac{1}{\sqrt{2}}\int\left[\sqrt{P(x)}-\sqrt{Q(x)}\right]^{2}\;dx$.

We note the caveat that the process described above is for continuous
probability distributions. In DNA sequencing, discrete probability
distributions are encountered. Thus, we approximate a continuous manifold as a
discrete manifold using piecewise linear approximations.
For example, consider a small DNA sequence of length $10$: ATCGATCGAT. Let the
reference sequence be ATCGTTAGCT. Using the Algorithm 11, we first calculate
the probability distributions for the sequence and the reference:

$\displaystyle p(\textbf{A})=$ $\displaystyle\;0.3,\quad\quad
q(\textbf{A})=0.4,$ $\displaystyle p(\textbf{T})=$
$\displaystyle\;0.4,\quad\quad q(\textbf{T})=0.2,$ $\displaystyle
p(\textbf{C})=$ $\displaystyle\;0.2,\quad\quad q(\textbf{C})=0.2,$
$\displaystyle p(\textbf{G})=$ $\displaystyle\;0.1,\quad\quad
q(\textbf{G})=0.2.$

Using these probabilities, we construct a discrete manifold for the
distributions and perform state mapping to obtain a basis in a Hilbert space.
We then calculate the linear and metric operators, then use their values to
get our encoded states. This is achieved as follows: The discrete probability
distributions are

$\displaystyle P=$
$\displaystyle\;\left\\{p(\textbf{A}),p(\textbf{T}),p(\textbf{C}),p(\textbf{G})\right\\}=\left\\{0.3,0.4,0.2,0.1\right\\},$
$\displaystyle Q=$
$\displaystyle\;\left\\{q(\textbf{A}),q(\textbf{T}),q(\textbf{C}),q(\textbf{G})\right\\}=\left\\{0.4,0.2,0.2,0.2\right\\}.$

Associated with the probability distributions, we define the manifold
$\mathcal{M}$ with tangent vectors

$X=\left(dx,dy,dz,dw\right),\quad\quad
Y=\left(dx^{\prime},dy^{\prime},dz^{\prime},dw^{\prime}\right),$

where $d\varphi$ are infinitesimal perturbations for
$\varphi\in\left\\{x,x^{\prime},y,y^{\prime},z,z^{\prime},w,w^{\prime}\right\\}$.
We define a potential tangent space for each tangent vector as

$\displaystyle T_{P}=$
$\displaystyle\;\left\\{\left(dx,dy,dz,dw\right)|dx+dy+dz+dw=0\right\\},$
$\displaystyle T_{Q}=$
$\displaystyle\;\left\\{\left(dx^{\prime},dy^{\prime},dz^{\prime},dw^{\prime}\right)|dx^{\prime}+dy^{\prime}+dz^{\prime}+dw^{\prime}=0\right\\}.$

Lastly, we compute the Fischer-Rao metric as follows:

$\displaystyle g_{P}(X,Y)=$
$\displaystyle\;\sum_{i\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}}\frac{1}{p(i)}\times\frac{dp(i)}{dx}\times\frac{dq(i)}{dx}$
$\displaystyle=$
$\displaystyle\;\sum_{i,j,k\in\left\\{\textbf{A},\textbf{T},\textbf{C},\textbf{G}\right\\}}\frac{1}{p(i)}\left\\{\delta_{ij}dx_{i}dx_{j}+\frac{1}{p(j)}\left[\delta_{ij}dx_{i}dx_{j}-p(i)\right]\right\\}\left\\{\delta_{ik}dx_{i}dx_{k}+\frac{1}{q(k)}\left[\delta_{ik}dx_{i}dx_{k}-q(i)\right]\right\\},$

where $\delta_{ij},\delta_{ik}$ are Kronecker delta functions. Simplifying and
substituting the probability values, we obtain

$\displaystyle g_{P}(X,Y)=$
$\displaystyle\;\left(\frac{1}{0.3}\right)\left(\frac{1}{0.4}\right)dx^{2}+\left(\frac{1}{0.4}\right)\left(\frac{1}{0.2}\right)dy^{2}+\left(\frac{1}{0.2}\right)\left(\frac{1}{0.2}\right)dz^{2}+\left(\frac{1}{0.1}\right)\left(\frac{1}{0.2}\right)dw^{2}$
$\displaystyle\;+\frac{2\left[\left(0.3\right)\left(0.4\right)+\left(0.2\right)\left(0.1\right)-2\left(0.3\right)\left(0.2\right)\right]}{\left(0.3\right)\left(0.4\right)\left(0.2\right)\left(0.2\right)}dydz$
$\displaystyle=$
$\displaystyle\;\frac{25}{3}\;dx^{2}+\frac{25}{2}\;dy^{2}+25\;dz^{2}+50\;dw^{2}+\frac{25}{3}\;dydz.$

##  VII Energy-Based Methods for Testing Encoded Sequences

The Sherrington-Kirkpatrick Model with an External Field, more commonly known
as the Boltzmann machine, introduced by Hinton and Sejnowski boltzmann1 , is a
type of neural network architecture that uses a randomised approach to
learning in what is termed stochastic learning. This is commonly used for
unsupervised ML tasks, such as pattern recognition, dimensionality reduction,
and data generation boltzmann3 . Of particular importance is pattern
recognition since DNA sequences exhibit recurring patterns, and it would prove
advantageous to take skillfully make use of this feature. Building upon the
ideas of the Boltzmann (or Gibbs) distribution from Statistical Mechanics
boltzmann2 , which has the form

$p(E_{i})=\frac{1}{Z}\times\exp\left(-\frac{E_{i}}{k_{B}T}\right),\quad\quad
Z=\sum_{j=1}^{n}\exp\left(-\frac{E_{j}}{k_{B}T}\right),$ (11)

where, in physical terms, $p$ is the probability, $E$ denotes the energy of
the $i^{\text{th}}$ particle; $k_{B}\approx 1.3806\times 10^{-23}\;\text{J/K}$
is the Boltzmann constant, $T$ is the temperature, $j$ is a running dummy
index, and $Z$ is known as the partition function, the Figure 12 shows this
distribution for various parameter values. Of particular importance in ML is
sampling, videlicet drawing information about the population based upon a
sample.

Figure 12: Graph of the Boltzmann distribution for various parameter values.

Geometrically, the Boltzmann machine consists of interconnected nodes / units
called visible and hidden units representing input and output variables as
illustrated in Figure 13. The connections between nodes are weighted and
determine the probability of a certain unit state given the state of its
neighbouring units. The visible units represent input data, whereas the Hidden
units represent latent variables or features of the data.
The machine is trained using Markov Chain Monte Carlo (MCMC) methods that
simulate the Boltzmann distribution and allow the machine to find the optimal
values for the weights that minimise the system’s energy, representing the
cost function of the ML system. This is achieved by sampling the Boltzmann
distribution by constructing a Markov Chain with the desired distribution as
its stationary distribution. Some standard MCMC techniques are: The
Metropolis-Hastings algorithm, Gibbs Sampling, and Hamiltonian Monte Carlo
boltzmann4 . The usage of MCMC is driven by the probability distribution being
too difficult to sample from in the first place.

Figure 13: Architecture of a fully connected Boltzmann machine with $3$
visible units and $5$ hidden units.

Two common architectural configurations of Boltzmann machines are

  1. 1.

Restricted Boltzmann Machine: These are simplified versions of the Boltzmann
machine, where the visible and hidden layers are connected in a bipartite
graph. Both models, the Boltzmann machine and the restricted Boltzmann
machine, use the same energy function to compute the joint probability of the
visible and hidden nodes / layers (Eq. 11).

  2. 2.

Deep Belief Networks: These are a type of generative ML model consisting of
multiple restricted Boltzmann machines (RBMs) stacked on top of each other.
The hidden layer activation of one RBM serves as the visible layer activation
of the next RBM to facilitate hierarchical representations of the data. They
are mathematically analogous to the standard Boltzmann machine; however, they
have two additional steps: Pre-training, whereby the weights and biases are
initialised in the stack, and fine-tuning, whereby the backpropagation
algorithm is used to optimise the weights in the stack.

On the other hand, we have seen recent success with Quantum Boltzmann Machines
(QBMs) boltzmann5 , a type of quantum neural network (QNN) that has been
proposed as a potential way to use the power of QC for ML tasks. They are
inspired by classical Boltzmann machines. In a QBM, the binary inputs are
replaced with qubits connected by a network of quantum gates, which are used
to implement the probabilistic updates that drive the learning process.
Using Boltzmann machines for classical-to-quantum data encoding, especially in
DNA sequencing, is justifiable because the Boltzmann machine can learn pattern
recognition and other structures in the input DNA sequence. Secondly, the
Boltzmann machine can learn in an unstructured manner without requiring
explicit labelling of nitrogenous bases and thus proffers a promising approach
to leveraging both classical and quantum computing simultaneously. QBMs are
used to model the joint probability distribution of quantum data, such as the
state of a quantum system or the outcomes of quantum measurements. By learning
this distribution, they can be used for various QML tasks, such as quantum
tomography, quantum generative modelling, and quantum data compression.
Below, we provide the Algorithm 12 for testing a classical-to-quantum encoded
DNA via the Boltzmann machine.

Algorithm 12 Qoltz$(\mathcal{D})$

input a DNA sequence $\mathcal{D}$

initialise the quantum circuit with $n,\ell,m\in\mathbb{N},0\leq\alpha\leq 1$,
for the number of qubits, number of layers in the Boltzmann machine, number of
steps in the optimisation algorithm, and the learning rate respectively with
weights $\mathbf{W}$ and biases $\boldsymbol{\mathcal{B}}$

for each nitrogenous base $b$ in the DNA sequence $\mathcal{D}$ do

apply bin_encode$(b)$ to encode the bases as binary numbers

calculate the number of segments, $N$, to split the DNA sequence into, amongst
$K$ varieties

while $\text{card}(\mathcal{D})\neq 0$ do
$N=\left\\{\begin{matrix}\frac{\text{card}(\mathcal{D})}{K},\quad\text{N is
even}\\\ \left\lfloor\frac{\text{card}(\mathcal{D})-1}{K}\right\rfloor,\quad
b_{\text{not
sequenced}}=\left[\text{card}(\mathcal{D})-1\right]\;\left(\text{mod}\;K\right),\quad\text{N
is odd}\end{matrix}\right.$

end while

for Each nitrogenous base $b$ in $N$ do

apply quant_encode$(s)$ to map
$0\longrightarrow\ket{0},1\longrightarrow\ket{1}$ to obtain the corresponding
quantum states of each segment $\ket{\psi}$

repeat

split the encoded states into training and validation sets

sample a mini-batch of encoded states

calculate the energy for each quantum state in the mini-batch  $\displaystyle
E(\ket{\psi})=$
$\displaystyle\;\sum_{\mathcal{L}=1}^{\ell}\sum_{\mathcal{N}=1}^{n}\left[w_{0}(\mathcal{L},\mathcal{N})\ket{\psi_{\mathcal{N}}}\otimes\ket{\psi_{\mathcal{N}+1}}+w_{1}(\mathcal{L},\mathcal{N})\ket{\psi_{\mathcal{N}}}\otimes\ket{\psi_{\mathcal{N}+1}}\right.$
$\displaystyle\left.+w_{2}(\mathcal{L},\mathcal{N})\ket{\psi_{\mathcal{N}}}\otimes\ket{\psi_{\mathcal{N}+1}}\right]-\sum_{\mathcal{N}=1}^{n}\mathcal{B}_{\mathcal{N}}\ket{\psi_{\mathcal{N}}}$

calculate the partition function  $Z=\sum_{\text{all
states}}\exp(-\ket{\psi})$

calculate the cost function, say
$J=-\frac{1}{\text{card}(\mathcal{D})}\sum_{\text{all
states}}\log\left[\frac{1}{Z}\times\exp(-E(\psi))\right]$

Algorithm 13 Qoltz$(\mathcal{D})$ \- Part $2$

apply an update rule for the weights for each state, say  $w\longleftarrow
w-\alpha\nabla_{w}J(W,\ket{\psi})$

until $J\longrightarrow 0$

end for

end for

return encoded states $\ket{\psi}$

In this Algorithm 12 above, we have used the negative log-likelihood cost
function; however, this can be adjusted to any cost function, such as MSE. In
addition, we have used the SGD update rule; however, this can be changed to
AdaGrad or ADAM.
For example, let us consider the DNA sequence AAGT; we will use the Qoltz
algorithm (12) to encode this DNA sequence into quantum states. First, we must
initialise the quantum circuit with the desired number of qubits, layers,
steps, and learning rate. We can set $n=4$, $\ell=2$, $m=100$, and
$\alpha=0.01$. We also need to initialise the weights and biases, but we will
assume they are already initialised for simplicity. Next, we will encode each
nitrogenous base in the DNA sequence as binary numbers using the bin_encode
function. The encoding for each base is as follows: A $\rightarrow 00$, C
$\rightarrow 01$, G $\rightarrow 10$, T $\rightarrow 11$.
Thus, the encoding for the DNA sequence AAGT is $00000111$; Next, we need to
split the encoded string into segments to train and validate the model on
different parts of the sequence; this provides more flexibility to learn
patterns and features specific to each segment and avoids overfitting any part
of the DNA sequence.
We want to split the string into $K=2$ varieties; the string length is $8$,
divisible by $2$. Therefore, we can split the string into two equal segments:
$0000$ and $0111$. We can map each segment to a quantum state using the
quant_encode function; in other terms, we use two qubits to encode each base,
then, we can encode the first segment as
$\ket{\psi_{1}}=\ket{00}\otimes\ket{00}$ and the second segment as
$\ket{\psi_{2}}=\ket{10}\otimes\ket{11}$.
We can now use the quantum states as input to the quantum Boltzmann machine
algorithm (12) to learn the underlying distribution of the DNA sequence. The
algorithm will use the quantum states as input to a quantum circuit with $n$
qubits, $\ell$ layers, and $m$ optimization steps. The algorithm will then use
an update rule to adjust the weights and biases of the quantum circuit to
minimise the cost function $J$. The resulting encoded states can be returned
as the algorithm’s output and tested using the same algorithm.

##  VIII The Dataset

The dataset used in this work is called human_nontata_promoters gresova ;
promoters generally are regions of DNA located upstream of a gene and serve as
binding sites for RNA polymerase, an enzyme responsible for transcribing the
gene into mRNA. The TATA box is a specific DNA sequence commonly found in the
promoter region of genes and is essential for transcription initiation.
Therefore, human_nontata_promoters refers to information related to promoter
regions of human genes that do not contain the TATA box sequence. This data
may include information about the location, function, and regulation of non-
TATA promoters and their interactions with transcription factors and other
regulatory elements. Understanding the characteristics of non-TATA promoters
is essential for understanding the complexity of gene regulation in humans and
identifying potential targets for therapeutic interventions.
Our data consists of genomic intervals of length $251$. These intervals are
located in the human genome’s non–TATA promoter regions. The dataset has two
classes: positive and negative. These classes identify whether a given genomic
interval contains an active promoter region (positive) or inactive (negative).
The dataset has a total of $36\;131$ sequences. Of these, $27\;097$ sequences
are used for training, and $9\;034$ are used for testing. The training set is
further divided into two classes, negative and positive. The negative class
contains $12\;355$ sequences, while the positive class contains $14\;742$
sequences. The testing set is also divided into two classes, negative and
positive. The negative class contains $4\;119$ sequences, while the positive
class contains $4\;915$ sequences.
There are five columns in this dataset (id, region, start, end, strand), and
each one has different information about the genomic intervals. Here is an
examination of each column:

  1. 1.

id: This column contains a unique identifier for each genomic interval. This
identifier is typically used to keep track of the individual sequences in the
dataset.

  2. 2.

region: This column specifies the genomic region where the interval is
located. In this case, the dataset includes only non-TATA promoter regions of
the human genome.

  3. 3.

start: This column specifies the starting position of the genomic interval on
the reference genome. The position is measured in base pairs (bp), the unit of
length commonly used in genomics.

  4. 4.

end: This column specifies the ending position of the genomic interval on the
reference genome. Like the start column, this position is also measured in
base pairs.

  5. 5.

strand: This column specifies the orientation of the genomic interval to the
reference genome. There are two possible orientations: forward $(+)$ or
reverse $(-)$. The orientation of the interval is important because it
determines the order of the nucleotides in the sequence.

Combining the information in these five columns makes uniquely identifying and
locating each genomic interval in the dataset possible.
This dataset is designed for a binary classification task to predict whether a
given genomic sequence belongs to the “positive” or “negative” class. Using
separate training and testing datasets for each class can help ensure that the
resulting model can generalise well to new data.
To illustrate the distribution of sequences in the training and testing
datasets, we used a bar chart. Figure 14 shows the number of sequences in each
class for the training and testing datasets. As can be seen from the figure,
the training dataset contains more sequences than the testing dataset, and the
number of positive sequences is higher than the number of negative sequences.
This class imbalance can be challenging for some machine learning algorithms,
and various techniques can be used to address it.

Figure 14: Training and testing data distributions.

To encode this type of data using quantum techniques, we first need to use the
id, region, start, and end information to retrieve the genomic sequence using
a genome assembly file or a genomic database. Once we have the sequence, we
can encode it using quantum circuits, where a qubit represents each nucleotide
base. By encoding the genomic sequence into qubits, we can exploit the quantum
properties of entanglement and superposition to perform certain computations
much faster than classical algorithms.
Several quantum machine learning models can be applied to this dataset, such
as quantum support vector machines, quantum neural networks, and quantum
Boltzmann machines. These models can classify genomic sequences into positive
or negative classes based on their underlying features. By using quantum
techniques, we can potentially achieve faster and more accurate classification
of genomic sequences, leading to significant advancements in personalised
medicine and drug discovery.

##  IX Conclusion and Future Work

In this research, we have introduced novel algorithms that utilise various
fields and advanced techniques from the field of QC to perform classical-to-
quantum data encoding in the Bioinformatics domain. Our study provides an
overview of existing classical-to-quantum encoding schemes and showcases how
to use them in this field; For example, we demonstrate how the Amplitude
Encoding method uses rotation gates to map classical data, in the form of
vectors representing DNA sequences, to quantum states. Additionally, we have
illustrated the use of Pauli Feature Map Encoding, which employs the
ZZFeatureMap tool from Qiskit to obtain a statevector for the DNA sequence,
and we employed the IQPEmbedding method from Pennylane to encode classical
data into quantum states. Our results show that the resulting quantum states
can be represented as vectors of complex numbers using IBM’s QasmSimulator. We
successfully demonstrated that data encoding could be applied to genomic data
by leveraging these techniques.
The novelty of this paper was the introduction of new lossless compression
algorithms, namely Quantum-influenced Huffman Coding (QuantHuff) and Quantum-
influenced Burrows-Wheeler Transform (QBWT), which have been demonstrated to
be effective using Python and Qiskit. We also introduced a wavelet-based
encoding algorithm, CosineEncoding, that uses a two-dimensional Discrete
Cosine Transform and quantum Fourier transform to map the magnitude of each
coefficient to an $n$-qubit register, generating the encoded quantum states.
We have also proposed the usage of information entropy using SEncode to encode
the DNA sequences to quantum states based on the lowest entropy by proposing
two algorithms, NZ22 and NZ23, that utilised reference data, and a third
variety the used information geometry in the form of algorithm QuantIG. These
algorithms offer various insights into the potential of quantum computing in
Bioinformatics.
A point of contention that arises is that the algorithms for predictions,
classifications, and comparisons are yet to be tested for their effectiveness.
In so doing, we proposed one algorithm, Qoltz, based on energy methods and the
Boltzmann machine to test the encoded data. Lastly, we discuss a potential
dataset as a sandbox environment for testing against real-world scenarios.
Furthermore, in Table 5 in the appendix, we comprehensively compare the
proposed algorithms’ advantages and disadvantages.
To further validate our results, we plan to investigate the performance of our
proposed algorithms on larger datasets and compare them with existing methods,
besides testing our algorithms on real quantum hardware, in follow-up studies
and future iterations. Additionally, we will explore the potential of quantum
computing for other Bioinformatics tasks, such as protein folding prediction
and drug discovery.
Moreover, we acknowledge the limitations and challenges of our proposed
methods, such as the impact of noise on encoding and algorithm scalability.
Additional research is needed to address these issues, and we hope to
contribute to this ongoing effort. Altogether, this study offers a promising
avenue for developing QC applications in Bioinformatics.

##  X Acknowledgements

Firstly, the authors would like to extend their sincere gratitude and
appreciation to the Quantumformalism.com community by the Zaiku Group for
supporting us in undertaking this research project. Secondly, to Dr. Vesselin
Gueorguiev, Dr. Dimitri Papaioannou, and Max Arnott for their insightful
comments and astute suggestions with regard to the structure and content of
this paper.

##  XI Code

All codes for the graphs and algorithms in the paper are available at:
https://github.com/quantumformalism/NISQ-C2QDE-GENOMICS.

## References

  * (1)

##  XII References

* (2) Sanger, F., Nicklen, S., and Coulson, A. R. “DNA Sequencing with Chain-termination Inhibitors”. Proceedings of the National Academy of Sciences of the United States of America, 74 (12). Washington, United States of America, pp. 5463-5467 (1977).
* (3) Heather, J. M., and Chain, B. “The Sequence of Sequencers: The History of Sequencing DNA”. Elsevier: Genomics, 107 (1). Amsterdam, The Netherlands, pp. 1-8 (2016).
* (4) Riesenfeld, C. S., Schloss, P. D., and Handelsman, J. “Metagenomics: Genomic Analysis of Microbial Communities”. Annual Reviews: Annual Review of Genetics, 38 (1). California, United States of America, pp. 525-552 (2004).
* (5) Macosko, E.Z., Basu, A., Satija, R., Nemesh, J., Shekhar, K., Goldman, M., Tirosh, I., Bialas, A. R., Kamitaki, N., Martersteck, E.M., Trombetta, J. J., Weitz, D. A., Sanes, J. R., Shalek, A. K., Regev, A., and McCarroll, S. A. “Highly Parallel Genome-wide Expression Profiling of Individual Cells using Nanoliter Droplets”. Cell Press: Cell, 161 (5). Cambridge, United States of America, pp. 1202-1214 (2015).
* (6) Metzker, M. L. “Sequencing Technologies – The Next Generation”. Nature: Nature Reviews Genetics, 11 (1). New York, United States of America, pp. 31-46 (2009).
* (7) Li, R., Zhu, H., Ruan, J., Qian, W., Fang, X., Shi, Z., Li, Y., Li, S., Shan, G., Kristiansen, K., Li, S., Yang, H., Wang, J., and Wang, J. “De Novo Assembly of Human Genomes with Massively Parallel Short Read Sequencing”. Cold Spring Harbor Laboratory Press: Genome Research, 20 (2). New York, United States of America, pp. 265-272 (2009).
* (8) Krauthammer, M., Kong, Y., Ha, B. H., Evans, P., Bacchiocchi, A., McCusker, J. P., Cheng, E., Davis, M. J., Goh, G., Choi, M., Ariyan, S., Narayan, D., Dutton-Regester, K., Capatana, A., Holman, E. C., Bosenberg, M., Sznol, M., Kluger, H. M., Brash, D. E., Stern, D. F., Materin, M. A., Lo, R. S., Mane, S., Ma, S., Kidd, K. K., Hayward, N. K., Lifton, R. P., Schlessinger, J., Boggon, T. J., and Halaban, R. “Exome Sequencing Identifies Recurrent Somatic $RAC1$ Mutations in Melanoma”. Nature: Nature Genetics, 44 (9). New York, United States of America, pp. 1006-1014 (2012).
* (9) Green, R. E., Malaspinas, A. S., Krause, J., Briggs, A. W., Johnson, P. L., Uhler, C., Meyer, M., Good, J. M., Maricic, T., Stenzel, U., Prüfer, K., Siebauer, M., Burbano, H. A., Ronan, M., Rothberg, J. M., Egholm, M., Rudan, P., Brajković D., Kućan, Z., Gus̆ić, I., Wikström, M., Laakkonen, L., Kelso, J., Slatkin, M., and Pääbo, S. “A Complete Neandertal Mitochondrial Genome Sequence Determined by High-Throughput Sequencing”. Cell Press: Cell, 134 (3). Cambridge, United States of America, pp. 416-426 (2008).
* (10) Feynman, R. P. “Simulating Physics with Computers”. Springer: International Journal of Theoretical Physics, 21 (6/7), Berlin, Germany, pp. 467-488 (1982).
* (11) Maxam, A. M., and Gilbert W. “A New Method for Sequencing DNA”. Proceedings of the National Academy of Sciences of the United States of America, 74 (2). Washington, United States of America, pp. 560-564 (1977).
* (12) Kathuria, K., Ratan. A., McConnell, M., and Bekiranov, S. “Implementation of a Hamming Distance–like Genomic Quantum Classifier using Inner Products on ibmqx2 and $\text{ibmq}\\_16\\_\text{melbourne}$”. Springer: Quantum Machine Intelligence, 2 (1). New York, United States of America, pp. 1-26 (2020).
* (13) Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinksky, V. V., Kiktenko, E. O., and Federov, A. K. “Genome Assembly Using Quantum and Quantum–Inspired Annealing”. Nature, 11 (1). New York, United States of America (2021).
* (14) Sarkar, A., Al-Ars, Z., and Bertels, K. “QuASeR: Quantum Accelerated De Novo DNA Sequence Reconstruction.” PLoS One, 16, (4). Cambridge, United Kingdom (2021).
* (15) Nałȩcz-Charkiewicz, K., and Nowak, R. M. “Algorithm for DNA Sequence Assembly by Quantum Annealing”. Springer: BMC Bioinformatics, 23 (122), New York, United States of America (2022).
* (16) Preskill, J. “Quantum Computing in the NISQ Era and Beyond”. Quantum, 2, Vienna, Austria, pp. 79-99 (2018).
* (17) Sierra-Sosa, D., Pal, S., and Telahun, M. “Data Rotation and its Influence on Quantum Encoding”. Springer: Quantum Information Processing, 22 (89). New York, United States of America (2023).
* (18) Bhattacharyya, A. “On a Measure of Divergence Between Two Statistical Populations Defined by their Probability Distributions”. Bulletin of the Calcutta Mathematical Society, 35, Calcutta, India, pp. 99-109 (1943).
* (19) Bhattacharyya, A. “On a Measure of Divergence Between Two Multinomial Populations”. Sankhyā: The Indian Journal of Statistics, 7 (4), Kolkata, India, pp. 401-406 (1946).
* (20) Sayood, K. “Introduction to Data Compression”. Elsevier: Morgan Kaufmann Publishers, 4th Ed., Massachusetts, United States of America (2012).
* (21) Huffman, D. “A Method for the Construction of Minimum-Redundancy Codes”. Proceedings of the IRE, 40 (9), United States of America, pp. 1098-1101 (1952).
* (22) Steffens, D. L., Sutter, S. L., and Roemer, S. C. “An Alternate Universal Forward Primer for Improved Automated DNA Sequencing of M13.” BioTechniques: The International Journal of Life Science Methods, 15 (4), London, United Kingdom, pp. 580-582 (1993).
* (23) Burrows, M., and Wheeler D. J. “A Block-sorting Lossless Data Compression Algorithm”. SRC Research Report, 124, California, United States of America (1994).
* (24) Li, H., and Durbin, R. “Fast and Accurate Short Read Alignment with Burrows-Wheeler Transform”. Oxford University Press: Bioinformatics, 25 (14), Oxford, United Kingdom, pp. 1754-1760 (2009).
* (25) Kimura, K., and Koiki, A. “Analysis of genomic rearrangements by using the Burrows-Wheeler transform of ssort-read Data”. Joint 26th Genome Informatics Workshop and 14th International Conference on Bioinformatics: BMC Bioinformatics, 16 (suppl. 18), Tokyo, Japan (2015).
* (26) Adjeroh, D., Zhang, Y., Mukherjee, A., Powell, M., and Bell, T. C. “DNA sequence compression using the Burrows-Wheeler Transform”. Proceedings of the IEEE Computer Society Bioinfrmatics Conference, California, United States of America (2002).
* (27) Pokrzywa, R., and Polanski, A. “BWtrs: A Tool for Searching for Tandem Repeats in DNA Sequences Sased on the Burrows-Wheeler Transform”. Elsevier: Genomics, 96 (5), Amsterdam, The Netherlands, pp. 316-321 (2010).
* (28) Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. “A Learning Algorithm for Boltzmann Machines”. John Wiley & Sons: Cognitive Science, 9 (1), New York, United States of America, pp. 147-169 (1985).
* (29) Geoffrey, H., and Salakhutdinov, R. “A Better Way to Pretrain Deep Boltzmann Machines.” Advances in Neural Information Processing (NIPS / NeurIPS) 31, 3, California, United States of America, pp. 1-9 (2017).
* (30) Tuckerman, M. E. “Statistical Mechanics: Theory and Molecular Simulation”. Oxford University Press, United States of America (2010).
* (31) Gilks, W. R. (ed.), Richardson, S. (ed), and Spiegelhalter, D. (ed). “Markov Chain Monte Carlo in Practice”. Chapman & Hall / CRC Interdisciplinary Statistics, 1st Ed., Florida, United States of America (1996).
* (32) Amin, M. H., Andriyash, E., Rolfe, J., Kulchytskyy, B., and Melko R., “Quantum Boltzmann Machine”. American Physical Society: Physical Review X 021050, 8 (2), Maryland, United States of America, pp. 1-11 (2018).
* (33) Nielsen, F. (ed.). “Geometric Theory of Information”. Springer, New York, United States of America (2014).
* (34) https://quantum-computing.ibm.com/
* (35) https://pennylane.ai/
* (36) Gresova, Katarina, et al. “Genomic Benchmarks: A Collection of Datasets for Genomic Sequence Classification”. Cold Spring Harbor Laboratory: bioRxiv, 22 (2022),

## Appendix: Advantages and disadvantages of the quantum encoding algorithms

Table 5: Advantages and disadvantages of our quantum encoding algorithms Algorithm |  Advantages |  Disadvantages
---|---|---
Amplitude Encoding (1) |  \- Can handle high-dimensional data, as high-dimensional vectors can represent DNA sequences.
\- Provides flexibility in choosing rotation angles based on the input data. |  \- Requires normalisation of input data.
\- Sensitivity to input data, as small changes in the DNA sequence can result
in large changes in the output.
\- The encoding is not reversible, so decoding the state may be complex.
Pauli Feature Map Encoding (3) |  \- Can handle high-dimensional classical data points.
\- Can be customised based on the application. |  \- Requires hardware that can handle controlled Z gates and nonlinear functions.
QuantHuff (17) |  \- Provides a compression technique that assigns variable-length binary codes to each symbol in a given set of symbols.
\- Can reduce the amount of memory required to store the data. |  \- Requires classical operations to construct a Huffman tree and assign binary codes.
QBWT (5) |  \- Can be used for long DNA sequences. |  \- Requires hardware that can handle unitary transformations.
Cosine Encoding(6) |  \- Relatively simple to implement compared to other quantum encoding methods. |  \- Requires many qubits, making it difficult to scale to larger images.
\- May require a high degree of precision.
SEncode (7) |  \- Can encode long DNA sequences using relatively few qubits.
\- Using a unitary operator to map each quantum state to a computational basis state ensures that the encoding is reversible. |  \- The performance may be sensitive to the choice of segment size and the number of segments.
\- It may require significant resources, including qubits and classical
computational power.
---|---|---
NZ22 (8) |  \- It considers the probability distributions of both the input and reference DNA sequences, which may lead to more accurate encoding compared to algorithms that only consider one sequence.
\- The number of qubits required for encoding is determined based on the KL divergence, which measures the difference between the probability distributions. This may lead to more efficient encoding than the other algorithms using a fixed number of qubits. |  \- The mapping of each base to an $n$-qubit register may result in many qubits required for longer sequences, which may lead to scalability issues.
\- The calculation of the KL divergence can be computationally intensive,
especially for longer sequences, which may increase the time required for
encoding.
NZ23 (10) |  \- It is based on the Bhattacharyya divergence, a robust similarity measure between probability distributions.
\- The number of qubits required for encoding the state is determined based on the similarity between the input and reference sequences. This can lead to more efficient encoding than other methods using a fixed number of qubits. |  \- It does not consider the specific features of the DNA sequence, such as the presence of repeats or structural variations, which can affect the accuracy of the encoding.
\- The adjustable hyperparameter $\alpha$ needs to be tuned for optimal
performance, which may require trial and error.
QuantIG (11) |  \- Using a Riemannian manifold to map probability distributions to a Hilbert space allows for efficient and accurate quantum operations on the probability distributions.
\- It considers the distance between the two probability distributions using an information metric, which can provide more accurate results than other algorithms considering only probability distributions. |  \- Using a Riemannian manifold and state mapping may require more computational resources than simpler algorithms.
\- Using a metric operator on the Hilbert space may require significant
mathematical expertise, limiting accessibility.
\- The accuracy and efficiency may depend on the choice of information metric
and other parameters, which could require further experimentation and
optimisation.
---|---|---
Qoltz (12) |  \- The quantum approach may offer faster processing times and handle larger datasets.
\- The ability to perform quantum operations on the encoded states could lead to new insights and discoveries in DNA research. |  \- The effectiveness is not yet established compared to classical algorithms, and comparing their performance may not be easy.
\- The optimisation process may be computationally intensive and require
significant resources and time.