Quantum algorithm for position weight matrix matching

• URL: http://arxiv.org/abs/2303.03569v1
• Date: Tue, 7 Mar 2023 00:34:16 GMT
• Title: Quantum algorithm for position weight matrix matching
• Authors: Koichi Miyamoto, Naoki Yamamoto, Yasubumi Sakakibara
• Abstract summary: We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching. The two proposed algorithms, the naive method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence.
• Score: 0.9404723842159504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence length $n$, the sequence motif length $m$ and the number of the PWMs $K$ as $\widetilde{O}\left(m\sqrt{Kn}\right)$, which means speedup over existing classical algorithms with respect to $n$ and $K$. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect to $m$ in some situation. As a drawback, these algorithms use quantum random access memories and their initialization takes $O(n)$ time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.

Related papers

• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
  We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
  arXiv  Detail & Related papers  (2024-09-06T03:32:02Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Preparation of matrix product states with log-depth quantum circuits [0.3277163122167433]
  We consider the preparation of matrix product states (MPS) on quantum devices via quantum circuits of local gates. We first prove that faithfully preparing translation-invariant normal MPS of $N$ sites requires a circuit depth $T=Omega(log N)$. We then introduce an algorithm based on the renormalization-group transformation to prepare normal MPS with an error $epsilon$ in depth $T=O(log (N/epsilon))$, which is optimal.
  arXiv  Detail & Related papers  (2023-07-04T13:05:29Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• 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)
• Quantum Algorithm for Anomaly Detection of Sequences [13.087762988229068]
  We propose a quantum algorithm for anomaly detection using Piecewise Aggregate in the Amplitude Domain (called ADPAAD) Our quantum algorithm can achieve speedups on the number of subsequences and the length of subsequences over its classical counterpart.
  arXiv  Detail & Related papers  (2022-09-18T16:14:16Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
  Dihedral Coset Problem (DCP) in $Z_N$ has been extensively studied in quantum computing and post-quantum cryptography. Ettinger-Hoyer algorithm is known to solve the DCP in $O(log(N))$ queries. We introduce the first algorithm to improve in the linear queries regime over the Ettinger-Hoyer algorithm.
  arXiv  Detail & Related papers  (2022-06-29T05:30:54Z)
• Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
  We propose an adaptive algorithm for interval estimation of amplitudes. The proposed algorithm uses a similar number of quantum queries to achieve the same level of precision. We rigorously prove that the number of oracle queries achieves $O(1/epsilon)$, i.e., a quadratic speedup over classical Monte Carlo sampling.
  arXiv  Detail & Related papers  (2022-06-16T21:11:15Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.