Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model

• URL: http://arxiv.org/abs/2112.13005v3
• Date: Mon, 6 Feb 2023 14:13:19 GMT
• Title: Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model
• Authors: Massimo Equi, Arianne Meijer-van de Griend, Veli M\"akinen
• Abstract summary: We show how to convert bit-parallelism of quadratic time solvable problems into quantum algorithms that attain speed-ups with factor $n$. We first show that the famous $O(n2/w)$ time bit-parallel algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic + operations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor $w$, where $w$ is the computer word size. For example, edit distance of two strings of length $n$ can be solved in $O(n^2/w)$ time. In a reasonable classical model of computation, one can assume $w=\Theta(\log n)$. There are conditional lower bounds for such problems stating that speed-ups with factor $n^\epsilon$ for any $\epsilon>0$ would lead to breakthroughs in complexity theory. However, these conditional lower bounds do not cover quantum models of computing. Indeed, Boroujeni et al. (J. ACM, 2021) showed that edit distance can be approximated within a factor $3$ in sub-quadratic time $O(n^{1.81})$ using quantum computing. They also showed that, in their chosen model of quantum computing, the approximation factor cannot be improved using sub-quadractic time. To break through the aforementioned classical conditional lower bounds and this latest quantum lower bound, we enrich the model of computation with a quantum random access memory (QRAM), obtaining what we call the word QRAM model. Under this model, we show how to convert the bit-parallelism of quadratic time solvable problems into quantum algorithms that attain speed-ups with factor $n$. The technique we use is simple and general enough to apply to many bit-parallel algorithms that use Boolean logics and bit-shifts. To apply it to edit distance, we first show that the famous $O(n^2/w)$ time bit-parallel algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic + operations. As a direct consequence of applying our technique to this variant, we obtain linear time edit distance algorithm under the word QRAM model for constant alphabet. We give further results on a restricted variant of the word QRAM model to give more insights to the limits of the model.

Related papers

• 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)
• Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
  We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
  arXiv  Detail & Related papers  (2024-05-16T16:46:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
  We present a novel quantum high-dimensional linear regression algorithm based on the classical LARS (Least Angle Regression) pathwise algorithm. Our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. We prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm is robust to errors.
  arXiv  Detail & Related papers  (2023-12-21T18:57:54Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor $w$, where $w$ is the computer word size. We show that a simple bit-parallel algorithm on such restricted family of graphs can indeed be converted into a realistic quantum algorithm.
  arXiv  Detail & Related papers  (2023-02-06T15:14:34Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• 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)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• What limits the simulation of quantum computers? [5.22339562024796]
  We demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.
  arXiv  Detail & Related papers  (2020-02-18T17:00:39Z)

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.