Compare Similarities Between DNA Sequences Using Permutation-Invariant Quantum Kernel

• URL: http://arxiv.org/abs/2503.05465v1
• Date: Fri, 07 Mar 2025 14:35:38 GMT
• Title: Compare Similarities Between DNA Sequences Using Permutation-Invariant Quantum Kernel
• Authors: Chenyu Shi, Gabriele Leoni, Mauro Petrillo, Antonio Puertas Gallardo, Hao Wang,
• Abstract summary: We propose a permutation-invariant variational quantum kernel method specifically designed for DNA comparison.<n>We show that our novel encoding method and parameterized layers used in the quantum kernel model can effectively capture the symmetric characteristics of the pairwise DNA sequence comparison task.
• Score: 3.8926796690238694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computing the similarity between two DNA sequences is of vital importance in bioscience. However, traditional computational methods can be resource-intensive due to the enormous sequence length encountered in practice. Recently, applied quantum algorithms have been anticipated to provide potential advantages over classical approaches. In this paper, we propose a permutation-invariant variational quantum kernel method specifically designed for DNA comparison. To represent the four nucleotide bases in DNA sequences with quantum states, we introduce a novel, theoretically motivated encoding scheme: the four distinct bases are encoded using the states of symmetric, informationally complete, positive operator-valued measures (SIC-POVMs). This encoding ensures mutual equality: each pair of symbols is equidistant on the Bloch sphere. Also, since permutation invariance is inherent to common DNA similarity measures such as Levenshtein distance, we realize it by using a specially designed parameterized quantum layer. We show that our novel encoding method and parameterized layers used in the quantum kernel model can effectively capture the symmetric characteristics of the pairwise DNA sequence comparison task. We validate our model through numerical experiments, which yield promising results on length-$8$ DNA sequences.

Related papers

• Model Decides How to Tokenize: Adaptive DNA Sequence Tokenization with MxDNA [44.630039477717624]
  MxDNA is a novel framework where the model autonomously learns an effective DNA tokenization strategy through gradient decent. We show that MxDNA learns unique tokenization strategy distinct to those of previous methods and captures genomic functionalities at a token level during self-supervised pretraining.
  arXiv  Detail & Related papers  (2024-12-18T10:55:43Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum gate algorithm for reference-guided DNA sequence alignment [0.0]
  We present a novel quantum algorithm for reference-guided DNA sequence alignment modeled with gate-based quantum computing. The algorithm is scalable, can be integrated into existing classical DNA sequencing systems and is intentionally structured to limit computational errors.
  arXiv  Detail & Related papers  (2023-08-08T18:41:24Z)
• Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform [0.0]
  We present a transparent algorithm for implementing the qubit quantum Schur transform. We study the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients. It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework.
  arXiv  Detail & Related papers  (2023-05-06T15:19:52Z)
• A biological sequence comparison algorithm using quantum computers [0.0]
  We present a method to display and analyze the similarity between two genome sequences on a quantum computer. Inspired by human perception of vision and pixel representation of images on quantum computers, we leverage these techniques to implement a pairwise sequence analysis.
  arXiv  Detail & Related papers  (2023-03-23T18:45:56Z)
• Determining probability density functions with adiabatic quantum computing [0.0]
  We present a method for fitting one-dimensional probability distributions as a practical example of how analog and gate-based computation can be used together. In particular, we propose a strategy for encoding data within an adiabatic evolution model, which accomodates the fitting of strictly monotonic functions.
  arXiv  Detail & Related papers  (2023-03-20T18:00:00Z)
• Gaussian conversion protocol for heralded generation of qunaught states [66.81715281131143]
  bosonic codes map qubit-type quantum information onto the larger bosonic Hilbert space. We convert between two instances of these codes GKP qunaught states and four-foldsymmetric binomial states corresponding to a zero-logical encoded qubit. We obtain GKP qunaught states with a fidelity of over 98% and a probability of approximately 3.14%.
  arXiv  Detail & Related papers  (2023-01-24T14:17:07Z)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Gradient-descent quantum process tomography by learning Kraus operators [63.69764116066747]
  We perform quantum process tomography (QPT) for both discrete- and continuous-variable quantum systems. We use a constrained gradient-descent (GD) approach on the so-called Stiefel manifold during optimization to obtain the Kraus operators. The GD-QPT matches the performance of both compressed-sensing (CS) and projected least-squares (PLS) QPT in benchmarks with two-qubit random processes.
  arXiv  Detail & Related papers  (2022-08-01T12:48:48Z)
• Simulating quantum circuits using tree tensor networks [0.0]
  We develop and analyze a method for simulating quantum circuits on classical computers. Our algorithm first determines a suitable, fixed tree structure adapted to the expected entanglement generated by the quantum circuit. We theoretically analyze the applicability of the method as well as its computational cost and memory requirements.
  arXiv  Detail & Related papers  (2022-06-02T11:57:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.